Read MD2

MD2 is a hash function proposed by Ranald Rivest in 1989. This paper mainly introduces the basic principle of MD2 algorithm. Although MD2 is not safe now, as a hash function with relatively simple structure, it is necessary to learn it.

Algorithm process

The following article will briefly describe the basic flow of MD2 algorithm

Byte Padding (Append Padding)

This byte filling scheme is not quite the same as MD5 and SHA1 I have written before. If you are interested, please refer to the introduction I have written about MD5 or SHA1.

MD4 is filled according to the following rules. Assuming that the data length is M, 16 – (M mod 16) bytes of data need to be filled, and the content is 16 – (M mod 16). The following figure is the schematic diagram of filling a whole packet:

Append Checksum

The checksum is computed as follows:

For i = 0 to 15 do:
    Set C[i] to 0.
end /* of loop on i */

Set L to 0.

/* Process each 16-word block. */
For i = 0 to N/16-1 do
   /* Checksum block i. */
   For j = 0 to 15 do
        Set c to M[i*16+j].
        Set C[j] to S[c xor L].
        Set L to C[j].
    end /* of loop on j */
end /* of loop on i */
Copy the code

Initialize MD Buffer

This is an easy initialization, just initialize a 48-byte array of zeros.

Process Message in 16-byte Blocks

This is also the core process of the algorithm, here directly paste the algorithm in the RFC:

For i = 0 to N'/16-1 do
    /* Copy block i into X. */
    For j = 0 to 15 do
        Set X[16+j] to M[i*16+j].
        Set X[32+j] to (X[16+j] xor X[j]).
    end /* of loop on j */

    Set t to 0.

    /* Do 18 rounds. */
    For j = 0 to 17 do
        /* Round j. */
        For k = 0 to 47 do
           Set t and X[k] to (X[k] xor S[t]).
        end /* of loop on k */

        Set t to (t+j) modulo 256.
    end /* of loop on j */
end /* of loop on i */
Copy the code

This process is similar to calculating a checksum, as shown below:

The output

This step is relatively simple, and the output of the MD Buffer is the final result.

Algorithm implementation

use std::iter::repeat;

static S_BOX: [u8; 256] = [
    0x29.0x2E.0x43.0xC9.0xA2.0xD8.0x7C.0x01.0x3D.0x36.0x54.0xA1.0xEC.0xF0.0x06.0x13.0x62.0xA7.0x05.0xF3.0xC0.0xC7.0x73.0x8C.0x98.0x93.0x2B.0xD9.0xBC.0x4C.0x82.0xCA.0x1E.0x9B.0x57.0x3C.0xFD.0xD4.0xE0.0x16.0x67.0x42.0x6F.0x18.0x8A.0x17.0xE5.0x12.0xBE.0x4E.0xC4.0xD6.0xDA.0x9E.0xDE.0x49.0xA0.0xFB.0xF5.0x8E.0xBB.0x2F.0xEE.0x7A.0xA9.0x68.0x79.0x91.0x15.0xB2.0x07.0x3F.0x94.0xC2.0x10.0x89.0x0B.0x22.0x5F.0x21.0x80.0x7F.0x5D.0x9A.0x5A.0x90.0x32.0x27.0x35.0x3E.0xCC.0xE7.0xBF.0xF7.0x97.0x03.0xFF.0x19.0x30.0xB3.0x48.0xA5.0xB5.0xD1.0xD7.0x5E.0x92.0x2A.0xAC.0x56.0xAA.0xC6.0x4F.0xB8.0x38.0xD2.0x96.0xA4.0x7D.0xB6.0x76.0xFC.0x6B.0xE2.0x9C.0x74.0x04.0xF1.0x45.0x9D.0x70.0x59.0x64.0x71.0x87.0x20.0x86.0x5B.0xCF.0x65.0xE6.0x2D.0xA8.0x02.0x1B.0x60.0x25.0xAD.0xAE.0xB0.0xB9.0xF6.0x1C.0x46.0x61.0x69.0x34.0x40.0x7E.0x0F.0x55.0x47.0xA3.0x23.0xDD.0x51.0xAF.0x3A.0xC3.0x5C.0xF9.0xCE.0xBA.0xC5.0xEA.0x26.0x2C.0x53.0x0D.0x6E.0x85.0x28.0x84.0x09.0xD3.0xDF.0xCD.0xF4.0x41.0x81.0x4D.0x52.0x6A.0xDC.0x37.0xC8.0x6C.0xC1.0xAB.0xFA.0x24.0xE1.0x7B.0x08.0x0C.0xBD.0xB1.0x4A.0x78.0x88.0x95.0x8B.0xE3.0x63.0xE8.0x6D.0xE9.0xCB.0xD5.0xFE.0x3B.0x00.0x1D.0x39.0xF2.0xEF.0xB7.0x0E.0x66.0x58.0xD0.0xE4.0xA6.0x77.0x72.0xF8.0xEB.0x75.0x4B.0x0A.0x31.0x44.0x50.0xB4.0x8F.0xED.0x1F.0x1A.0xDB.0x99.0x8D.0x33.0x9F.0x11.0x83.0x14,];pub struct MD2 {}

impl MD2 {
    fn padding(message: &[u8]) -> Vec<u8> {
        let mut result = message.to_vec();
        let padding_length = 16 - message.len() % 16;
        result.extend(repeat(padding_length as u8).take(padding_length));
        return result;
    }

    fn checksum(message: &[u8]) -> [u8; 16] {
        let mut checksum = [0u8; 16];
        let mut last = 0u8;

        for chuck in message.chunks(16) {
            for (m, c) in chuck.iter().zip(checksum.iter_mut()) {
                *c ^= S_BOX[(*m ^ last) as usize]; last = *c; }}return checksum;
    }

    fn compress(state: &[u8], message: &[u8]) -> [u8; 16] {
        let mut x = [0u8; 48];

        for i in 0.16 {
            x[i] = state[i];
            x[i + 16] = message[i]
        }

        for (i, byte) in message.iter().enumerate() {
            x[32 + i] = *byte ^ x[i];
        }

        let mut t = 0u8;
        for i in 0.18 {
            for j in 0..x.len() {
                x[j] ^= S_BOX[t as usize];
                t = x[j];
            }
            t = t.wrapping_add(i);
        }

        let mut result = [0u8; 16];
        for i in 0.16 {
            result[i] = x[i];
        }

        return result;
    }

    fn hash(message: &[u8]) -> String {
        let mut message = MD2::padding(message);

        let csum = MD2::checksum(&message);

        message.extend(csum.to_vec());

        let hash = message.chunks(16).fold([0u8; 16], |state, chunk| MD2::compress(&state, chunk));

        return hash.iter().fold(String::new(), |a, &b| format!("{}{:02x}", a, b)); }}#[cfg(test)]
mod test {
    use crate::md2::MD2;

    #[test]
    fn test() {
        println!("md2([empty string]) = {}", MD2::hash("".as_bytes()));
        println!("md2([The quick brown fox jumps over the lazy dog]) = {}", MD2::hash("The quick brown fox jumps over the lazy dog".as_bytes())); }}Copy the code

The resources

  • rfc1319
  • MD2 (hash function) – Wikipedia
  • The MD2 Hash Function is Not One-Way