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