Subject: [Ietf-krb-wg] better pseudo-random

From: Simon Josefsson <[email-masked]>
Date: Wed, 25 Mar 2009 00:44:00 +0100

The things that I believe are sub-optimal in RFC 3961's "pseudo-random":

1) It truncates the hash output before (essentially) MACing it.

   I believe this makes security proofs more inelegant since it has to
   assume things about the hash function which isn't normally assumed.

2) The output size is fixed.  In practical applications (for example
   krb5starttls-bootstrap), you often need the ability to generate
   arbitrary length outputs.

3) It isn't what is implemented ;)

Addressing 3) for the des3 and aes case would be useful.  Addressing 1)
and 2) for the des3/aes case is not useful as far as I can see.

I would support a document that retroactively says that the
pseudo-random function for aes/des3 is mit-aes-prf.  [Unless someone has
implemented the RFC 3961 pseudo-random function -- then we have bigger
problems.]

For future AEAD enctypes I hope we can address 1) by specifying a
pseudo-random that doesn't involve truncation.  In other words, use the
simplified profile but provide a better pseudo-random.

One way to work towards addressing 2) would be, in 3961bis, specify a
pseudo-random2 function that generates arbitrary amount of output.  It
would do the same as RFC 4402 for all existing enctypes.  RFC 4402 could
be updated to say that the pseudo-random2 function is used instead, and
referencing RFC 3961bis.  Then future AEAD enctypes could specify
another pseudo-random2 function if they so wanted, and the
GSS_Pseudo_random would work.

I'm not saying doing the work to address 2) is motivated at this point.

/Simon
_______________________________________________
ietf-krb-wg mailing list
[email-masked]
https://lists.anl.gov/mailman/listinfo/ietf-krb-wg

---

From: Sam Hartman <[email-masked]>
Date: Tue, 24 Mar 2009 20:51:01 -0400

>>>>> "Simon" == Simon Josefsson <[email-masked]> writes:

    Simon> The things that I believe are sub-optimal in RFC 3961's
    Simon> "pseudo-random": 1) It truncates the hash output before
    Simon> (essentially) MACing it.

    Simon>    I believe this makes security proofs more inelegant
    Simon> since it has to assume things about the hash function which
    Simon> isn't normally assumed.
What do you need to assume?

    Simon> 2) The output size is fixed.  In practical applications
    Simon> (for example krb5starttls-bootstrap), you often need the
    Simon> ability to generate arbitrary length outputs.

I think this is typical of PRF constructions.
I do think that turning your PRF into a PRFplus is something libraries should do a better job of
and I'd support standardizing on a single prfplus construction.
_______________________________________________
ietf-krb-wg mailing list
[email-masked]
https://lists.anl.gov/mailman/listinfo/ietf-krb-wg

---

From: Simon Josefsson <[email-masked]>
Date: Wed, 25 Mar 2009 09:55:29 +0100

> What do you need to assume?

I believe you need to assume that the hash output size is related to the
intended strength of the hash function.  I.e., the assumption that a n
bit hash provides roughly n/2 strength against collision resistance.
Otherwise you don't exclude the hash functions I mentioned earlier: a
hash function with output size 128+160 that outputs 128 0-bits and then
the SHA-1 of the input.

As far as I understand, the normal assumption on hash functions in
security proofs is that it is computationally infeasible to compute
collisions.  That assumption alone isn't sufficient here.  It is
computationally infeasible to find a collision in the 128+160 hash
(assuming you believe it is computationally infeasible to find a
collision in SHA-1).

I'd be happy to learn if the cryptographic community has come up with a
way to deal with hash truncation in security proofs.  Alternatively, if
there is a modified definition of "collision resistance" that people
think is a reasonable assumption on modern hash functions, and that
would rule out the hash function I mentioned.

The SHA-3 competition says the hash function should be collision
resistance, and further that it should provide n/2 strength against
collisions for a n-bit hash.  That is a good requirement for a new
design, since we usually consider a hash function broken if it fails to
meet this.  But that doesn't mean it is a reasonable assumption to make
in a security proof if we can do with lesser assumptions.

> and I'd support standardizing on a single prfplus construction.

That's what the pseudo-random2 function I talked about would do.

I note that RFC 4402 and FAST defines similar but subtly different
PRF+'s.  This seems bad to me.  The reason this happens is that there is
no canonical pseudo-random2-like function defined in RFC 3961 that other
documents can reference.

/Simon

---

From: Nicolas Williams <[email-masked]>
Date: Wed, 25 Mar 2009 12:02:58 -0500

> bit hash provides roughly n/2 strength against collision resistance.

That assumption pervades in this space.  We've all been trained to think
"a hash with 160 output bits provides 2^80 work factor strength against
brute force collision searches."

> hash function with output size 128+160 that outputs 128 0-bits and then

But that's a pretty good assumption.  A hash function that has structure
in its output is not a hash function that we want to use.

Every hash function that we have, from MD4 to SHA-512, satisfies this
assumption modulo cryptanalytic breaks (i.e., MD4, MD5, and SHA-1
provide less than n/2 collision resistance, but they were certainly
designed to provide n/2 collision resistance).

I'm perfectly happy with this assumption.

> collisions.  That assumption alone isn't sufficient here.  It is

Well, it's one assumption (there's also first and second pre-image
resistance).

> [...]

I can't think of a hash function in recent decades, including the SHA-3
competition, that did not meet this assumption (ignoring subsequent
successful cryptanalysis).

> no canonical pseudo-random2-like function defined in RFC 3961 that other

I agree.