Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

I would like to generate a 256-bit hash on a microcontroller that has a 128-bit (only) AES engine. How can I construct a 256-bit hash function from a 128-bit cipher?

share|improve this question

migrated from stackoverflow.com Sep 9 '11 at 19:30

This question came from our site for professional and enthusiast programmers.

1  
I do not think this is easy. I am not sure a "known" approach even exists. See en.wikipedia.org/wiki/… –  Nemo Sep 9 '11 at 17:18
3  
Pad it with 0s? That way you at least don't pretend to have higher security than 128 bit. –  CodesInChaos Sep 9 '11 at 17:40
    
I had to do this years back for something inconsequential. I'm sure that what I came up with is crappy. Thankfully, what I though was inconsequential back then remains inconsequential today, but that is notoriously hard to predict in advance. Other times that has not been the case. –  Marsh Ray Sep 11 '11 at 15:22
1  
Do you need a MAC, or a hash function? It makes a significant difference. –  D.W. Sep 13 '11 at 7:06
    
@D.W. I do actually need a MAC, but I'm interested in the answer to the stated question. I may ask another question about implementing MACs on constrained devices. –  joeforker Sep 13 '11 at 16:43

5 Answers 5

HMAC is a specific construction which aims at providing a message authentication code. HMAC is defined over a hash function, something which AES is not.

So if your question is really about having HMAC, not just any MAC, and using an AES primitive, then your question becomes: how can we build a hash function out of a block cipher ? This is not an easy question, especially if the block cipher uses blocks which are smaller than the intended hash function output size. You could investigate ECHO, a former SHA-3 candidate, which received a reasonably fair share of analysis by many cryptographers, who found no actual problem in it. ECHO is built upon some constitutive parts of AES, and can benefit from most hardware accelerators for AES.

On the other hand, if you just want a MAC (not specifically HMAC), and have an available AES primitive, then I recommend CBC-MAC (just don't use the exact same key to encrypt data !). This will yield a 128-bit MAC. A 256-bit MAC is a weird requirement, since 128 bits ought to be enough to provide adequate security (if 128 bits are not enough, then the attacker is way more powerful than the whole of Mankind, including all governments, agencies, private corporations and mafias -- and at that point you probably have more trouble than a possibly weak MAC: for all practical purposes, the attacker is God).

One could imagine defining a 256-bit block cipher with a Feistel network where the confusion function is an AES instance, with enough rounds and distinct round keys -- like what the DEAL block cipher did with DES, during the AES competition. Then CBC-MAC on that block cipher would yield a 256-bit MAC. But custom building of block ciphers or other cryptographic primitives is not recommended at all since it is hard to get right, and you cannot test for the security of the result.

share|improve this answer
    
Doesn't the birthday paradox mean a 128-bit hash only provides 64 bits of security when looking for collisions? –  joeforker Sep 10 '11 at 13:20
1  
@joeforker: For a hash function, yes. Your original question was about HMAC (i.e. a MAC), and the inclusion of a secret key there means you would need 2^64 choosen-plaintexts to get a good chance for a collision, which is quite less easy to do than running the hash function for yourself. –  Paŭlo Ebermann Sep 10 '11 at 16:11
    
@joeforker Do you really anticipate generating on the order of 2^64 messages anyway? That's a lot of messages. As in, if you generated 1 million messages a second, it would still take you half a million years. –  Nick Johnson Sep 12 '11 at 7:07
    
Thanks for the useful advice on key lengths and the inapplicability of the birthday paradox. I probably will use CBC-MAC or CMAC (for variable-length messages according to Wikipedia) for my application. –  joeforker Sep 12 '11 at 13:44
    
@joeforker - wait a minute. A MAC is a different beast than a hash function. Which do you need? The question asks about for a hash function. However, if you actually need a MAC, not a hash function, then that changes the answer considerably. –  D.W. Sep 13 '11 at 7:06

Are you sure you need an HMAC (Hash based MAC)? CBC-MAC is probably a better construction for a keyed message authentication code using a block cipher. To get 256-bits, use two separate keys and compute 2 different MACs and concatenate them together.

If your AES engine is really a Rijndael implementation (which means it would support larger block sizes), just use Rijndael with a 256 bit block size in a CBC-MAC construction.

share|improve this answer

If you need HMAC in order to be compatible with an existing use of it (to speak to SSL, for example) then you cannot do this with AES: HMAC for SSL will use a specific underlying hash function (like SHA1 or MD5, typically).

If you really want HMAC out of AES, you'll have to first make a crypto hash function out of AES, as Thomas said.

If you have Rijndael (which is the algorithm that AES was made from), you can get a block-size of 256 bits easily enough if it's available on your engine. Then use a construction like Merkle-Damgaard to get a hash function.

If you only have 128-bit AES, you'll need to use a double-wide construction like MDC-2. MDC-2 isn't so well-tested, but it has at least a collision proof in the ideal-cipher model.

share|improve this answer

This paper: Building Hash Functions from Block Ciphers, Their Security and Implementation Properties may be useful. In particular, section 3.4 deals with "Double-Block-Length Compression Functions" which may be what you need.

share|improve this answer
1  
Welcome to Cryptography Stack Exchange. Could you add a sketch of the scheme to the answer, to make it more complete? –  Paŭlo Ebermann Sep 10 '11 at 11:26
    
The schemes mentioned in that paper all assumes the ideal cipher model, but I'm not sure the ideal cipher model is a great model of AES, given the existence of theoretical weaknesses (e.g., related-key attacks) on the AES key schedule. Personally, I would feel more comfortable using something like SHA256, given the choice. –  D.W. Sep 11 '11 at 21:49

It looks like you've changed your question. Anyway, as to the new question (about how to build a 256-bit hash function out of 128-bit AES), the simple answer is: you don't. Don't do that. There's no really good, well-vetted way to build a 256-bit cryptographic hash function out of AES. Instead, if you need a 256-bit hash function, you should be using a dedicated hash construction, such as SHA256.

I would question whether you truly need a 256-bit cryptographic hash function. Are you sure this is needed? My suspicion is that it is not.

share|improve this answer
1  
You feel that 'Hirose - Some Plausible Constructions of Double-Block-Length Hash Functions' iacr.org/archive/fse2006/40470213/40470213.pdf is insufficiently vetted? –  Marsh Ray Sep 11 '11 at 15:19
1  
@Marsh, I would feel more comfortable with a standard hash function (e.g., SHA256), than that scheme. For instance, that scheme assumes the ideal cipher model, but I'm not sure the ideal cipher model is a great model of AES, given the existence of theoretical weaknesses (e.g., related-key attacks) on the AES key schedule. –  D.W. Sep 11 '11 at 21:47

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.