Activation protocol for tracking devices

Jerry Leichter leichter at lrw.com
Mon Mar 2 18:11:24 EST 2009


On Mar 2, 2009, at 12:56 PM, Santiago Aguiar wrote:

> Hi,
>
> Jerry Leichter wrote:
>> Not specifically, but you can simply take the first 64 bits from a  
>> larger cryptographically secure hash function.
> OK, I didn't know if it was right to do just that. We were thinking  
> to use that hash in an HMAC so the TCU and SO can know that they  
> were originated from someone who knows Kc and to protect it's  
> integrity (see below).
All the bits in a cryptographically secure hash function are "equally  
good".  So, yes, you can construct a shorter hash by simply discarding  
bits from a longer one.

I would suggest that if you're going to build an HMAC, that you shrink  
the result as the very last step:  Do the internal calculations using  
the full hash function.  I don't see an obvious attack from doing it  
the other way, but  it just seems riskier.

>> With a hash, you need to be a bit fancier since, in and of itself,  
>> the hash has no secret information.  This can be done, but it would  
>> be trickier; I'd go with the block cipher.
> Best if we can avoid trickier things!. I was thinking of a hash so  
> maybe we could reuse the ones we were using on other parts of the  
> protocol (since probably asking to include support for a larger set  
> of primitives on all devices would be resisted); but we can, of  
> course, just require that the TCU generates a random challenge and  
> leave the mechanism to be defined by each implementation.
>
>> Note that there are published algorithms - even part of FIPS  
>> standards - that do exactly what you need:  Take a single random  
>> seed and safely stretch it into a large number of random values.   
>> The ones in the standards - and perhaps most of the ones out there  
>> - are old and probably not up to contemporary standards.
> Will take a look at them, thanks.
Look around for "deterministic random number generators" or something  
like that.  I'm sure you know this, but do *not* attempt to use a  
generator designed for statistical purposes - those have good  
"randomness" properties but are not secure against deliberate attack.

>> You're trying to produce a keyed hash function (or MAC) from a non- 
>> keyed hash function.  Just pre-pending the secret key is not  
>> necessarily secure.  I'd suggest using HMAC (with Kt the key, of  
>> course).
> Yes, I was aware of this, the H should be an HMAC. AFAIK it  
> shouldn't be a problem, just some extra cycles and doing it the  
> right way, right?
Yes.

>>> From that point, Kc is stored in SO and TCU, and every message  
>>> interchanged between the SO and TCU goes signed with Kc (for this  
>>> we need a H with max. 64 bits output...).
>> Signed?  How?  I don't understand the 64-bit limitation.  I'm not  
>> sure a 64-bit signing key is sufficient these days.
> The 64 bits limitation is because the protocol only has 1 slot to  
> include *some* auth information, and it's a 64 bits field (yes, it  
> has been defined without knowing what exactly will go there ;)). The  
> protocol was defined by a working group and trying to changing it  
> can be... complicated... unless we have obvious arguments to show  
> that it's insufficient.
>
> By signed I meant doing a HMAC(Kc, body of message (with auth field  
> in 0, sic)). Would it be OK in this case to truncate the output of  
> ie. a HMAC-SHA1 to 64 bits? My crypto/math is not good enough to  
> understand how hard would be in this case to modify a msg to reuse a  
> previous signature.
OK, there is a distinction between a signature and a MAC (Message  
Authentication Code).  The significant difference is that it's  
possible to prove to a third party that someone signed something  
without actually having the ability to sign things yourself.  (Think  
RSA signatures:  The public key is all you need to prove that  
something was signed with the corresponding private key; but it's  
insufficient to sign anything.)  A MAC is sufficient for your purpose.

It's fine to truncate the output of a MAC computation.  In fact, there  
good reasons for doing so in some situations, independent of the  
available space:  By discarding information, it makes certain attacks  
harder.  You'll see people immediately jump in with "but the birthday  
paradox says you lose half your bits", which is true for a hash, but  
*not* for a MAC, where the attacker doesn't have access to the key.

> Thanks for your comments Jerry!
You're welcome.  I hope they're helpful, but don't rely on them too  
much - my quick response on a mailing list isn't a serious security  
analysis of the protocol and implementation.
                                                         -- Jerry

---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at metzdowd.com



More information about the cryptography mailing list