.. DO NOT EDIT.
.. THIS FILE WAS AUTOMATICALLY GENERATED BY SPHINX-GALLERY.
.. TO MAKE CHANGES, EDIT THE SOURCE PYTHON FILE:
.. "api/gallery/crypto/hashing/plot_01_birthday_attack.py"
.. LINE NUMBERS ARE GIVEN BELOW.

.. only:: html

    .. note::
        :class: sphx-glr-download-link-note

        :ref:`Go to the end <sphx_glr_download_api_gallery_crypto_hashing_plot_01_birthday_attack.py>`
        to download the full example code or to run this example in your browser via JupyterLite.

.. rst-class:: sphx-glr-example-title

.. _sphx_glr_api_gallery_crypto_hashing_plot_01_birthday_attack.py:


The birthday attack on hash functions (Yuval 1979)
==================================================

In a room of 23 people, two probably share a birthday. Yuval turned this
into an attack: to find *any* two messages with the same n-bit hash takes
about 2**(n/2) trials, not the 2**n needed to match one given hash. A
signer tricked into signing one of a colliding pair has signed both.

What to look for
----------------

Collision searches on truncated SHA-256 succeed after about sqrt(2**n)
trials. This square root is why hashes have 256-bit outputs: to give
128-bit collision resistance.

The history behind this experiment: :doc:`/history/crypto_breakthroughs`.
See :doc:`/exercises/crypto` for a worked solution to the exercise.

.. GENERATED FROM PYTHON SOURCE LINES 22-24

Find a collision on 24 bits
---------------------------

.. GENERATED FROM PYTHON SOURCE LINES 24-34

.. code-block:: Python

    import matplotlib.pyplot as plt
    import numpy as np

    import blockchainkit as bk

    result = bk.crypto.find_collision(24, prefix=b"contract v")
    assert bk.crypto.truncated_hash(result.first, 24) == bk.crypto.truncated_hash(result.second, 24)
    print(result.first, result.second, "collide after", result.trials, "trials")
    print("Matching one given 24-bit hash would take about", 2**24, "trials")





.. rst-class:: sphx-glr-script-out

 .. code-block:: none

    b'contract v\x00\x00\x00\x00\x00\x00\x07\x0b' b'contract v\x00\x00\x00\x00\x00\x00\x11\x87' collide after 4488 trials
    Matching one given 24-bit hash would take about 16777216 trials




.. GENERATED FROM PYTHON SOURCE LINES 35-37

Collision cost follows the square root
--------------------------------------

.. GENERATED FROM PYTHON SOURCE LINES 37-53

.. code-block:: Python

    sizes = list(range(8, 33, 2))
    mean_trials = []
    for bits in sizes:
        trials = [bk.crypto.find_collision(bits, prefix=bytes([seed])).trials for seed in range(12)]
        mean_trials.append(np.mean(trials))
    sizes_arr = np.array(sizes)
    fig, ax = plt.subplots(figsize=(7, 4))
    ax.semilogy(sizes, mean_trials, "o", label="measured (mean of 12)")
    ax.semilogy(
        sizes_arr, np.sqrt(np.pi / 2 * 2.0**sizes_arr), "-", color="black", label="sqrt(pi/2 * 2**n)"
    )
    ax.semilogy(sizes_arr, 2.0**sizes_arr, ":", color="#b45309", label="second preimage: 2**n")
    ax.set(xlabel="hash bits n", ylabel="trials", title="Collisions cost the square root")
    ax.legend()
    fig.tight_layout()




.. image-sg:: /api/gallery/crypto/hashing/images/sphx_glr_plot_01_birthday_attack_001.png
   :alt: Collisions cost the square root
   :srcset: /api/gallery/crypto/hashing/images/sphx_glr_plot_01_birthday_attack_001.png
   :class: sphx-glr-single-img





.. GENERATED FROM PYTHON SOURCE LINES 54-59

Exercise
--------
The expected number of trials is about sqrt(pi/2 * 2**n). At a billion
hashes per second, how long does a collision on a 64-bit hash take? On a
128-bit hash? Why did MD5 (128 bits) fall, but not only because of this?


.. rst-class:: sphx-glr-timing

   **Total running time of the script:** (0 minutes 3.140 seconds)


.. _sphx_glr_download_api_gallery_crypto_hashing_plot_01_birthday_attack.py:

.. only:: html

  .. container:: sphx-glr-footer sphx-glr-footer-example

    .. container:: lite-badge

      .. image:: images/jupyterlite_badge_logo.svg
        :target: ../../../../lite/lab/index.html?path=api/gallery/crypto/hashing/plot_01_birthday_attack.ipynb
        :alt: Launch JupyterLite
        :width: 150 px

    .. container:: sphx-glr-download sphx-glr-download-jupyter

      :download:`Download Jupyter notebook: plot_01_birthday_attack.ipynb <plot_01_birthday_attack.ipynb>`

    .. container:: sphx-glr-download sphx-glr-download-python

      :download:`Download Python source code: plot_01_birthday_attack.py <plot_01_birthday_attack.py>`

    .. container:: sphx-glr-download sphx-glr-download-zip

      :download:`Download zipped: plot_01_birthday_attack.zip <plot_01_birthday_attack.zip>`


.. only:: html

 .. rst-class:: sphx-glr-signature

    `Gallery generated by Sphinx-Gallery <https://sphinx-gallery.github.io>`_