1 # MD4 (RFC 1320, R. Rivest, "The MD4 Message-Digest Algorithm", 1992): a 2 # 128-bit digest of 64-byte blocks, three rounds of sixteen steps each (the 3 # step order, shifts and constants of section 3.4, unrolled by 4 # gen/rounds.py). Little-endian words; the length in bits is padded in 5 # little-endian. MD4 is broken (collisions are found by hand): it is here 6 # to read what already uses it (NTLM, rsync's older protocols). 7 # 8 # The hash, as the crypto package's hash interface takes it: 9 # ~Hs.HsMdState, ~64n, ~16n, ~HsMd4.init(), ~HsMd4.update, 10 # ~HsMd4.final, ~HsMd4.digest 11 import Base 12 import bend-osdev-bytes@0.1.0.0/bytes.bend as B 13 import ./hashes.bend as Hs 14 15 # the round functions F (round 1), G (round 2) and H (round 3) 16 def hs.md4.f(+x: U32, y: U32, z: U32) -> U32: 17 U32.or(U32.and(x, y), U32.and(U32.not(x), z)) 18 19 def hs.md4.g(+x: U32, +y: U32, +z: U32) -> U32: 20 U32.or(U32.or(U32.and(x, y), U32.and(x, z)), U32.and(y, z)) 21 22 def hs.md4.h(x: U32, y: U32, z: U32) -> U32: 23 U32.xor(U32.xor(x, y), z) 24 25 # one step: (a + f + X[k] + K) <<< s 26 def hs.md4.step(a: U32, f: U32, x: U32, k: U32, +s: Nat) -> U32: 27 Hs.hs.rotl(U32.add(U32.add(a, f), U32.add(x, k)), s) 28 29 # BEGIN GENERATED by gen/rounds.py: md4 30 def hs.md4.rounds(x: Hs.HsW16, cv: Hs.HsW4) -> Hs.HsW4: 31 match x cv: 32 case Hs.HsW16{+x0, +x1, +x2, +x3, +x4, +x5, +x6, +x7, +x8, +x9, +x10, +x11, +x12, +x13, +x14, +x15} Hs.HsW4{+a0, +b0, +c0, +d0}: 33 # round 1 34 +v1 = hs.md4.step(a0, hs.md4.f(b0, c0, d0), x0, 0, 3n) 35 +v2 = hs.md4.step(d0, hs.md4.f(v1, b0, c0), x1, 0, 7n) 36 +v3 = hs.md4.step(c0, hs.md4.f(v2, v1, b0), x2, 0, 11n) 37 +v4 = hs.md4.step(b0, hs.md4.f(v3, v2, v1), x3, 0, 19n) 38 +v5 = hs.md4.step(v1, hs.md4.f(v4, v3, v2), x4, 0, 3n) 39 +v6 = hs.md4.step(v2, hs.md4.f(v5, v4, v3), x5, 0, 7n) 40 +v7 = hs.md4.step(v3, hs.md4.f(v6, v5, v4), x6, 0, 11n) 41 +v8 = hs.md4.step(v4, hs.md4.f(v7, v6, v5), x7, 0, 19n) 42 +v9 = hs.md4.step(v5, hs.md4.f(v8, v7, v6), x8, 0, 3n) 43 +v10 = hs.md4.step(v6, hs.md4.f(v9, v8, v7), x9, 0, 7n) 44 +v11 = hs.md4.step(v7, hs.md4.f(v10, v9, v8), x10, 0, 11n) 45 +v12 = hs.md4.step(v8, hs.md4.f(v11, v10, v9), x11, 0, 19n) 46 +v13 = hs.md4.step(v9, hs.md4.f(v12, v11, v10), x12, 0, 3n) 47 +v14 = hs.md4.step(v10, hs.md4.f(v13, v12, v11), x13, 0, 7n) 48 +v15 = hs.md4.step(v11, hs.md4.f(v14, v13, v12), x14, 0, 11n) 49 +v16 = hs.md4.step(v12, hs.md4.f(v15, v14, v13), x15, 0, 19n) 50 # round 2 51 +v17 = hs.md4.step(v13, hs.md4.g(v16, v15, v14), x0, 1518500249, 3n) 52 +v18 = hs.md4.step(v14, hs.md4.g(v17, v16, v15), x4, 1518500249, 5n) 53 +v19 = hs.md4.step(v15, hs.md4.g(v18, v17, v16), x8, 1518500249, 9n) 54 +v20 = hs.md4.step(v16, hs.md4.g(v19, v18, v17), x12, 1518500249, 13n) 55 +v21 = hs.md4.step(v17, hs.md4.g(v20, v19, v18), x1, 1518500249, 3n) 56 +v22 = hs.md4.step(v18, hs.md4.g(v21, v20, v19), x5, 1518500249, 5n) 57 +v23 = hs.md4.step(v19, hs.md4.g(v22, v21, v20), x9, 1518500249, 9n) 58 +v24 = hs.md4.step(v20, hs.md4.g(v23, v22, v21), x13, 1518500249, 13n) 59 +v25 = hs.md4.step(v21, hs.md4.g(v24, v23, v22), x2, 1518500249, 3n) 60 +v26 = hs.md4.step(v22, hs.md4.g(v25, v24, v23), x6, 1518500249, 5n) 61 +v27 = hs.md4.step(v23, hs.md4.g(v26, v25, v24), x10, 1518500249, 9n) 62 +v28 = hs.md4.step(v24, hs.md4.g(v27, v26, v25), x14, 1518500249, 13n) 63 +v29 = hs.md4.step(v25, hs.md4.g(v28, v27, v26), x3, 1518500249, 3n) 64 +v30 = hs.md4.step(v26, hs.md4.g(v29, v28, v27), x7, 1518500249, 5n) 65 +v31 = hs.md4.step(v27, hs.md4.g(v30, v29, v28), x11, 1518500249, 9n) 66 +v32 = hs.md4.step(v28, hs.md4.g(v31, v30, v29), x15, 1518500249, 13n) 67 # round 3 68 +v33 = hs.md4.step(v29, hs.md4.h(v32, v31, v30), x0, 1859775393, 3n) 69 +v34 = hs.md4.step(v30, hs.md4.h(v33, v32, v31), x8, 1859775393, 9n) 70 +v35 = hs.md4.step(v31, hs.md4.h(v34, v33, v32), x4, 1859775393, 11n) 71 +v36 = hs.md4.step(v32, hs.md4.h(v35, v34, v33), x12, 1859775393, 15n) 72 +v37 = hs.md4.step(v33, hs.md4.h(v36, v35, v34), x2, 1859775393, 3n) 73 +v38 = hs.md4.step(v34, hs.md4.h(v37, v36, v35), x10, 1859775393, 9n) 74 +v39 = hs.md4.step(v35, hs.md4.h(v38, v37, v36), x6, 1859775393, 11n) 75 +v40 = hs.md4.step(v36, hs.md4.h(v39, v38, v37), x14, 1859775393, 15n) 76 +v41 = hs.md4.step(v37, hs.md4.h(v40, v39, v38), x1, 1859775393, 3n) 77 +v42 = hs.md4.step(v38, hs.md4.h(v41, v40, v39), x9, 1859775393, 9n) 78 +v43 = hs.md4.step(v39, hs.md4.h(v42, v41, v40), x5, 1859775393, 11n) 79 +v44 = hs.md4.step(v40, hs.md4.h(v43, v42, v41), x13, 1859775393, 15n) 80 +v45 = hs.md4.step(v41, hs.md4.h(v44, v43, v42), x3, 1859775393, 3n) 81 +v46 = hs.md4.step(v42, hs.md4.h(v45, v44, v43), x11, 1859775393, 9n) 82 +v47 = hs.md4.step(v43, hs.md4.h(v46, v45, v44), x7, 1859775393, 11n) 83 +v48 = hs.md4.step(v44, hs.md4.h(v47, v46, v45), x15, 1859775393, 15n) 84 Hs.HsW4{U32.add(a0, v45), U32.add(b0, v48), U32.add(c0, v47), U32.add(d0, v46)} 85 # END GENERATED: md4 86 87 # The chaining value before any block (section 3.3) 88 def HsMd4.iv() -> Hs.HsW4: 89 Hs.HsW4{1732584193, 4023233417, 2562383102, 271733878} 90 91 # One 64-byte block (a list of another length is read as zero words: the 92 # engine passes only whole blocks) 93 def HsMd4.compress(cv: Hs.HsW4, blk: List<&2, U32>) -> Hs.HsW4: 94 hs.md4.rounds(Hs.hs.block.le(blk), cv) 95 96 def HsMd4.init() -> Hs.HsMdState: 97 Hs.HsMd.start(~Hs.HsW4, HsMd4.iv()) 98 99 def HsMd4.update(s: Hs.HsMdState, o: B.Octets) -> Hs.HsMdState: 100 Hs.HsMd.update(~Hs.HsW4, ~HsMd4.compress, ~63, s, o) 101 102 # the digest of the bytes so far: the padding and the length, then the four 103 # words little-endian 104 def HsMd4.final(s: Hs.HsMdState) -> B.Octets: 105 Hs.HsMd.final_md(~Hs.HsW4, ~HsMd4.compress, ~63, ~Hs.hs.len.le, ~Hs.HsW4.le, s) 106 107 # The digest in one call 108 def HsMd4.digest(o: B.Octets) -> B.Octets: 109 HsMd4.final(HsMd4.update(HsMd4.init(), o))