.. DO NOT EDIT.
.. THIS FILE WAS AUTOMATICALLY GENERATED BY SPHINX-GALLERY.
.. TO MAKE CHANGES, EDIT THE SOURCE PYTHON FILE:
.. "api/gallery/crypto/hashing/plot_02_merkle_damgard.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_02_merkle_damgard.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_02_merkle_damgard.py:


The Merkle-Damgard construction and length extension (1989)
===========================================================

Merkle and Damgard independently showed how to build a hash for messages of
any length from a fixed-size compression function: pad the message, append
its length, and chain the blocks through the function. SHA-256 is built
this way. The digest *is* the final chaining state, which has a famous
consequence.

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

blockchainkit's step-by-step SHA-256 matches the standard library. Then an
attacker who sees only H(key || message) computes a valid
H(key || message || padding || suffix) without the key: the
length-extension attack that breaks naive secret-prefix MACs.

The history behind this experiment: :doc:`/history/crypto_breakthroughs`.

.. GENERATED FROM PYTHON SOURCE LINES 23-25

Hashing as a chain of compressions
----------------------------------

.. GENERATED FROM PYTHON SOURCE LINES 25-40

.. code-block:: Python

    import hashlib

    import matplotlib.pyplot as plt

    import blockchainkit as bk

    message = b"x" * 150
    padded = message + bk.crypto.sha256_padding(len(message))
    states = [bk.crypto.SHA256_IV]
    for start in range(0, len(padded), 64):
        states.append(bk.crypto.sha256_compress(states[-1], padded[start : start + 64]))
    digest = b"".join(word.to_bytes(4, "big") for word in states[-1])
    assert digest == hashlib.sha256(message).digest() == bk.crypto.merkle_damgard_sha256(message)
    print(len(message), "bytes ->", len(padded) // 64, "blocks")





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

 .. code-block:: none

    150 bytes -> 3 blocks




.. GENERATED FROM PYTHON SOURCE LINES 41-43

Extend a hash without knowing the secret
----------------------------------------

.. GENERATED FROM PYTHON SOURCE LINES 43-51

.. code-block:: Python

    secret = b"server-side key!"  # The attacker never sees this...
    order = b"user=alice&amount=10"
    tag = bk.crypto.naive_mac(secret, order)  # ...only the order and its tag.
    glue, forged_tag = bk.crypto.length_extension(tag, len(secret) + len(order), b"&amount=1000000")
    forged_order = order + glue + b"&amount=1000000"
    assert bk.crypto.naive_mac(secret, forged_order) == forged_tag
    print("Forged order accepted:", forged_order[-16:])





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

 .. code-block:: none

    Forged order accepted: b' &amount=1000000'




.. GENERATED FROM PYTHON SOURCE LINES 52-54

The chaining state through the blocks
-------------------------------------

.. GENERATED FROM PYTHON SOURCE LINES 54-65

.. code-block:: Python

    fig, ax = plt.subplots(figsize=(8, 3.5))
    for word in range(8):
        ax.plot(range(len(states)), [s[word] / 2**32 for s in states], "o-", alpha=0.7)
    ax.set(
        xlabel="blocks compressed",
        ylabel="state word / 2**32",
        title="Eight 32-bit words carry everything forward",
    )
    ax.set_xticks(range(len(states)))
    fig.tight_layout()




.. image-sg:: /api/gallery/crypto/hashing/images/sphx_glr_plot_02_merkle_damgard_001.png
   :alt: Eight 32-bit words carry everything forward
   :srcset: /api/gallery/crypto/hashing/images/sphx_glr_plot_02_merkle_damgard_001.png
   :class: sphx-glr-single-img





.. GENERATED FROM PYTHON SOURCE LINES 66-71

Exercise
--------
The forged message contains the padding bytes "glue". Print them and
explain where the 0x80 byte and the trailing length come from. Why does
hashing twice, H(H(m)), as Bitcoin does, also stop length extension?


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

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


.. _sphx_glr_download_api_gallery_crypto_hashing_plot_02_merkle_damgard.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_02_merkle_damgard.ipynb
        :alt: Launch JupyterLite
        :width: 150 px

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

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

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

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

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

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


.. only:: html

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

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