The suffix-free-prefix-free hash function construction and its indifferentiability security analysis

Nasour Bagheri, Praveen Gauravaram, Lars R. Knudsen, Erik Zenner

    Research output: Contribution to journalJournal articleResearchpeer-review

    359 Downloads (Pure)

    Abstract

    In this paper, we observe that in the seminal work on indifferentiability analysis of iterated hash functions by Coron et al. and in subsequent works, the initial value $$(IV)$$ of hash functions is fixed. In addition, these indifferentiability results do not depend on the Merkle–Damgård (MD) strengthening in the padding functionality of the hash functions. We propose a generic $$n$$-bit-iterated hash function framework based on an $$n$$-bit compression function called suffix-free-prefix-free (SFPF) that works for arbitrary $$IV$$s and does not possess MD strengthening. We formally prove that SFPF is indifferentiable from a random oracle (RO) when the compression function is viewed as a fixed input-length random oracle (FIL-RO). We show that some hash function constructions proposed in the literature fit in the SFPF framework while others that do not fit in this framework are not indifferentiable from a RO. We also show that the SFPF hash function framework with the provision of MD strengthening generalizes any $$n$$-bit-iterated hash function based on an $$n$$-bit compression function and with an $$n$$-bit chaining value that is proven indifferentiable from a RO.
    Original languageEnglish
    JournalInternational Journal of Information Security
    Volume11
    Issue number6
    Pages (from-to)419-434
    ISSN1615-5262
    DOIs
    Publication statusPublished - 2012

    Cite this

    @article{292dc828984340c49397a6428f766f18,
    title = "The suffix-free-prefix-free hash function construction and its indifferentiability security analysis",
    abstract = "In this paper, we observe that in the seminal work on indifferentiability analysis of iterated hash functions by Coron et al. and in subsequent works, the initial value $$(IV)$$ of hash functions is fixed. In addition, these indifferentiability results do not depend on the Merkle–Damg{\aa}rd (MD) strengthening in the padding functionality of the hash functions. We propose a generic $$n$$-bit-iterated hash function framework based on an $$n$$-bit compression function called suffix-free-prefix-free (SFPF) that works for arbitrary $$IV$$s and does not possess MD strengthening. We formally prove that SFPF is indifferentiable from a random oracle (RO) when the compression function is viewed as a fixed input-length random oracle (FIL-RO). We show that some hash function constructions proposed in the literature fit in the SFPF framework while others that do not fit in this framework are not indifferentiable from a RO. We also show that the SFPF hash function framework with the provision of MD strengthening generalizes any $$n$$-bit-iterated hash function based on an $$n$$-bit compression function and with an $$n$$-bit chaining value that is proven indifferentiable from a RO.",
    author = "Nasour Bagheri and Praveen Gauravaram and Knudsen, {Lars R.} and Erik Zenner",
    year = "2012",
    doi = "10.1007/s10207-012-0175-4",
    language = "English",
    volume = "11",
    pages = "419--434",
    journal = "International Journal of Information Security",
    issn = "1615-5262",
    publisher = "Springer",
    number = "6",

    }

    The suffix-free-prefix-free hash function construction and its indifferentiability security analysis. / Bagheri, Nasour; Gauravaram, Praveen; Knudsen, Lars R.; Zenner, Erik.

    In: International Journal of Information Security, Vol. 11, No. 6, 2012, p. 419-434.

    Research output: Contribution to journalJournal articleResearchpeer-review

    TY - JOUR

    T1 - The suffix-free-prefix-free hash function construction and its indifferentiability security analysis

    AU - Bagheri, Nasour

    AU - Gauravaram, Praveen

    AU - Knudsen, Lars R.

    AU - Zenner, Erik

    PY - 2012

    Y1 - 2012

    N2 - In this paper, we observe that in the seminal work on indifferentiability analysis of iterated hash functions by Coron et al. and in subsequent works, the initial value $$(IV)$$ of hash functions is fixed. In addition, these indifferentiability results do not depend on the Merkle–Damgård (MD) strengthening in the padding functionality of the hash functions. We propose a generic $$n$$-bit-iterated hash function framework based on an $$n$$-bit compression function called suffix-free-prefix-free (SFPF) that works for arbitrary $$IV$$s and does not possess MD strengthening. We formally prove that SFPF is indifferentiable from a random oracle (RO) when the compression function is viewed as a fixed input-length random oracle (FIL-RO). We show that some hash function constructions proposed in the literature fit in the SFPF framework while others that do not fit in this framework are not indifferentiable from a RO. We also show that the SFPF hash function framework with the provision of MD strengthening generalizes any $$n$$-bit-iterated hash function based on an $$n$$-bit compression function and with an $$n$$-bit chaining value that is proven indifferentiable from a RO.

    AB - In this paper, we observe that in the seminal work on indifferentiability analysis of iterated hash functions by Coron et al. and in subsequent works, the initial value $$(IV)$$ of hash functions is fixed. In addition, these indifferentiability results do not depend on the Merkle–Damgård (MD) strengthening in the padding functionality of the hash functions. We propose a generic $$n$$-bit-iterated hash function framework based on an $$n$$-bit compression function called suffix-free-prefix-free (SFPF) that works for arbitrary $$IV$$s and does not possess MD strengthening. We formally prove that SFPF is indifferentiable from a random oracle (RO) when the compression function is viewed as a fixed input-length random oracle (FIL-RO). We show that some hash function constructions proposed in the literature fit in the SFPF framework while others that do not fit in this framework are not indifferentiable from a RO. We also show that the SFPF hash function framework with the provision of MD strengthening generalizes any $$n$$-bit-iterated hash function based on an $$n$$-bit compression function and with an $$n$$-bit chaining value that is proven indifferentiable from a RO.

    U2 - 10.1007/s10207-012-0175-4

    DO - 10.1007/s10207-012-0175-4

    M3 - Journal article

    VL - 11

    SP - 419

    EP - 434

    JO - International Journal of Information Security

    JF - International Journal of Information Security

    SN - 1615-5262

    IS - 6

    ER -