CODEWITHSUNDEEP
javaalgorithmmd5implementation
Matt
Matt

Reputation: 7249

Implementing MD5, append bit 1 and 0s

So i am not sure if I'm doing this correctly. I am going by the pseudo code here: http://en.wikipedia.org/wiki/MD5

It says:

//Pre-processing:
append "1" bit to message
append "0" bits until message length in bits ≡ 448 (mod 512)
append length to message

In java, would i be able to convert the message to a byte array. Then get the number of bits by getting the string length * 8. Then do something like 448 - ((#bits+1) mod 512) to get the number of 0 bits to append to.

Then copy that byte array to another array, but pad the first bytes with 0s and then a 1.

Example:

String is 746 bits I would then do 448 - ((746+1) mod 512) = 213

So i would need to pad the string with 213 "0" bits and then 1 "1" bit.

So then my array would be something like

byteArr[0] = 0x00
byteArr[1] = 0x00
...
byteArr[27] = 000001(Rest of message bits)
byteArr[n] = Rest of the bytes from message

How can i find out where the 1 goes though? Basically how can i find out if it's going to create a short if i append the 1 bit.

Is there an easier way or some other way to do this?

Upvotes: 2

Views: 2588

Answers (5)

emboss
emboss

Reputation: 39660

If you implement crypto algorithms you should make it a good habit taking the official specs as blueprint for your implementation. As great as Wikipedia is, I still wouldn't rely on it for implementing security-critical algorithms. Of course it's fine, though, to use it in addition to the official specification. So I'd start with RFC 1321 and would only get "inspiration" from other sources.

RFC 1321 even contains an implementation in C, you could check that out, too. About the padding step, they say

3.1 Step 1. Append Padding Bits

The message is "padded" (extended) so that its length (in bits) is congruent to 448, modulo 512. That is, the message is extended so that it is just 64 bits shy of being a multiple of 512 bits long. Padding is always performed, even if the length of the message is already congruent to 448, modulo 512.

Padding is performed as follows: a single "1" bit is appended to the message, and then "0" bits are appended so that the length in bits of the padded message becomes congruent to 448, modulo 512. In all, at least one bit and at most 512 bits are appended.

This means you have to append the 1 first, then pad with the remaining zeroes, not the other way round. The remainder of bits to pad (including the "1") will always be a multiple of 8, since your input was bytes whose bit length is also a multiple of 8. So let's say you had to pad 128 bits. This means a 1 plus 127 0 bits. In total, that is 16 (16*8=128) bytes of padding, where the first bytes highest bit is set to 1, i.e. the first byte will become 0x80, the rest is 0x00. So this means you can simplify this padding step to

  • n = total number of bytes to pad = remainder in bits divided by 8
  • append 0x80 to your message
  • append n-1 times 0x00 to the message

Upvotes: 0

Daniel Martin
Daniel Martin

Reputation: 23558

As someone else caught, "append" means added to the end. So really what you want to have is a byte of 0x80 after the message followed by a bunch of 0 bytes until the number of bytes total is 8 less than a multiple of 64.

Upvotes: 1

Ali
Ali

Reputation: 12684

What you are talking about is salting a hash.

This is how I do it.

public static byte[] getSecure8ByteSalt(){
    SecureRandom random = null;
    try {
        random = SecureRandom.getInstance("SHA1PRNG");
        byte [] bSalt =  new byte[8];
        random.nextBytes(bSalt);
        return bSalt;
    } catch (NoSuchAlgorithmException e) {
        log.error(e.getMessage(),e);
    }
    return new byte[]{
         (byte)0xA9, (byte)0x9B, (byte)0xC8, (byte)0x32,
         (byte)0x56, (byte)0x34, (byte)0xE3, (byte)0x03
     };
}

The method that calls for the salt is called hash:

private void hash(String passwd, int hashType){
    byte[] bSalt = new byte[8];
    try {
        if(this.salt == null){
            bSalt = getSecure8ByteSalt();
        }
        else{ 
            bSalt = base64ToByte(salt);
        }
    } catch (IOException e1) {
        log.error(e1.getMessage(),e1);
        return;
    }


    byte[] bDigest=null;
    try {
        bDigest = getHash(ITERATION_NUMBER,passwd,bSalt,hashType);
    } catch (NoSuchAlgorithmException e) {
        log.error(e.getMessage(),e);
    }

    String sDigest = byteToBase64(bDigest);
    if(this.salt == null)
        setSalt(byteToBase64(bSalt));
setPasswordHash(sDigest);
}

Byte to base 64 method:

public static byte[] base64ToByte(String data) throws IOException {
    BASE64Decoder decoder = new BASE64Decoder();
    return decoder.decodeBuffer(data);
}

public static String byteToBase64(byte[] data){
       BASE64Encoder endecoder = new BASE64Encoder();
       return endecoder.encode(data);
}

the getHash method:

    private byte[] getHash(int iterationNb, String password, byte[] salt, int hashType) throws NoSuchAlgorithmException {
       MessageDigest digest = MessageDigest.getInstance(HASH_TYPE[hashType]);
       digest.reset();
       digest.update(salt);
       byte[] input = null;
        try {
            input = digest.digest(password.getBytes("UTF-8"));
        } catch (UnsupportedEncodingException e) {
            log.error(e.getMessage(),e);
        }
       for (int i = 0; i < iterationNb; i++) {
           digest.reset();
           input = digest.digest(input);
       }
       return input;
   }

Upvotes: -2

Matten
Matten

Reputation: 17603

The bits must be appended to the end of the message, not the beginning. After padding the message to 448 bits mod 512, you have to append the length of the message (without the padded bits). But as long as this isn't an exercise, you should use the algorithm JB Nizet mentioned.

Upvotes: 2

JB Nizet
JB Nizet

Reputation: 692073

There is a much easier way to do it: just use the MD5 algorithm already implemented for you by the Java SE API.

Side note: a String in Java contains chars, not bytes. Don't use the term "string" to refer to a binary message. Use the term byte array.

Upvotes: 0

Related Questions