Subject: Re: [Cfrg] AES-based PRF - comment please

From: Ran Canetti <[email-masked]>
Date: Mon, 24 Mar 2003 00:45:56 -0500

Uri,

Few remarks:

1. I think that there is some terminology confusion here with respect to the
meaning of the name "pseudorandom function" (PRF). In the cryptographic
theory, a PRF is an abstraction (i.e., a primitive) with specific 
mathematical properties. Within IKE there is a construct (used for key
derivation) that is called "PRF"; the reason for the name was that in 
the mind of the protocol designers this construct was to be modeled as 
a PRF in a security proof of IKE. However, there is of course no necessity 
to model the IKE-PRF construct as a PRF. Indeed, what you seem to suggest 
is that we can perhaps do otherwise.

2. In crypto-theory, a PRF is guaranteed to provide security only when its
key is SECRET and RANDOM (ie, uniformly distributed). 
If the key is either not secret or not random then all bets are off - no
security whatsoever is guaranteed. 

3. The security requirements from block-ciphers are typically aligned with
the requirements from PRFs (or rather PRPs (pseudorandom permulations)).
That is, security is required and analyzed only for the case where the key
is SECRET and RANDOM. Nothing is required when the key is either not secret
or not random.

4. You seem to want to construct a key-derivation function that can take 
a bunch of inputs of variable length (some of them are secret, some public, 
some random, some not) and somehow generate out of these a sequence of
pseudorandom bits, which is as long as necessary. your general methodology
is as follows:
I. Using some hash function H, "hash down" the input material into a value 
v that is of the right size for a PRF F. (You essentially make no distinction
between the S input and the N input to your construct.)
This corresponds to your steps 1-4.
II. Run F in OFB with key v and input 0*, to generate as many output bits as
necessary. This corresponds to your step 5.

Your hope is that H is good enough so that v will be sufficiently
"pseudorandom", even if the input is neither completely random nor
completely secret. 

Furthermore, you are using AES both for H and for F. 

5. While using AES for F is sound, my impression is that using AES as the 
(essentially keyless) hash function H is rather risky and definitely not 
well analyzed. This is not to say that it's necessarily a bad idea; rather, 
I'd say that this requires much more justification and analysis - both in 
terms of general cryptographic modeling and in terms of AES specifically.
Certainly, this property that you need from H does not follow from 
collision resistance. 

(Ofcourse, the "easy way out" would be to model AES as a random oracle. 
Then the analysis is completely trivialized and everything becomes perfectly
secure on paper. But this is no real analysis - we know that AES is NOT
a random oracle and we need an analysis based on realistic
assumptions on/ modeling of AES.)

Hope this makes sense.

Ran

> From [email-masked] Sun Mar 23 03:58:26 2003
> 
> Folks,
> 
> Here's a proposed PRF based on AES block cipher. Its purpose is
> to allow variable length input and output for AES, including
> keying material. It can be useful for AES-only protocol suites
> in IKEv2. It is based directly on Rijndael submission paper,
> where they describe how to use Rijndael as Hash and as PRF.
> 
> Ted Ts'o asked me to post it here, which is my pleasure to do.
> I look for comments, improvements and criticism.
> 
> Thank you!
> 
> Regards,
> Uri.
> 
> P.S. IKEv2 will use AES as block cipher, and g^xy as S. But it
> would be nice if the construct holds for generic block cipher
> and generic secret S.
> 
> --------------020208050107040706040902
> Content-Type: text/plain;
>  name="aes-prf.txt"
> Content-Disposition: inline;
>  filename="aes-prf.txt"
> Content-Transfer-Encoding: 7bit
> 
> PROPOSAL: AES-BASED PSEUDO RANDOM FUNCTION FOR IKEv2.
> 
> PRF(S, N)
> 
> The goal is to produce requested amount of pseudo
> random bits, using AES (or other block cipher) and 
> variable-length input for both parameters: the secret
> one (e.g. DH output) and the one publicly known (e.g.
> concatenation of nonces). Should work with variable
> key length, preferably support different block sizes.
> Preferably, the construct is provably secure.
> 
> The following idea is implementing recommendation from
> Rijndael Submission Paper to NIST, in particular - for
> using AES as Pseudo Random Function. It is assumed that
> AES is the block cipher that will be used, but the 
> construct is generic enough to accomodate other 
> block ciphers with no weak keys.
> 
> 
> 
> ALGORITHM:  PRF(S, N)
> 
> S is secret, N may be known. No assumption on the quality 
> of randomness is made for either parameter. No limitation 
> on size of S, N. 
> 
> Outputs pseudo-random stream of bits in  cipher blocksize
> chunks (128-bit for AES). Bu default - outputs the number
> of bits equal to blocksize. Optionally the amount of
> output bits can be specified.
> 
> Block cipher is assumed, with key-buffer for key, and
> data-buffer for plaintext. AES is a natural choice.
> 
> Algorithm:
>   
>    1. Fill the key-buffer with S. If S is shorter than
>       the key-buffer, pad the key buffer with zeroes.
>       
>    2. If any bits of S are left after step (1), place
>       them in the data-buffer. Append parameter N to
>       the data-buffer. Pad the data-buffer with zeroes
>       if necessary, to make it multiple of cipher block
>       size, and at least as long as key-buffer.
> 
>    3. Encrypt as many blocks of data-buffer as necessary
>       to fill key-buffer. 
> 
>    4. Take the output of (3) and fill the key-buffer.
>       Continue (3) and (4) for the reminder of the 
>       data-buffer.
> 
>    5. At this point the encryption engine is ready to produce
>       Pseudo-Random stream.  Now run the encryption engine in
>       OFB mode (starting with input buffer filled with zeroes)
>       using the full block size, until the desired amount of 
>       output bits is produced.
> 
> 
> RATIONALE.
> 
> a. Encryption engine is keyed with secret parameter because
> all the theory of block cipher security is based on the
> assumption that it is the key which is unknown to the 
> attacker. No analysis exists (as far as I know) for the 
> case when the key is known, but the plaintext and/or 
> ciphertext aren't.
> 
> b. Changing the key at step (4) mitigates the Related Keys
> attack.
> 
> c. OFB mode in step (5) allows producing [practically] any
> amount of output bits, much larger than the cipher block 
> size.
> 
> 
> 
> SECURITY PROPERTIES.
> 
> A block cipher being a Pseudo Random Permutation, if the
> S parameter is secret, the following hold true:
> 
>    - output of (3) is pseudo-random.
>    - output of (5) is pseudo-random.
> 
> 
> 
> CONSIDERATIONS.
> 
> Security of this PRF is based on three assumptions: (a) block
> cipher used is not broken, (b) the secret parameter is unknown
> to the attacker, and (c) there is no property of the key space
> that makes a class of keys weak. 
> 
> If a weak secret - such as a short passwod - is used for parameter
> S, then it is possible to break this algorithm by dictionary
> attack. Note that this vulnerability exists in HMAC as well,
> and is unavoidable (unless one uses protocols such as PAK, 
> EKE/SPEKE, etc).
> 
> 
> DESIGN ALTERNATIVE.
> 
> Instead of zeroizing the data-buffer in the step (5),
> one can leave it as is, effectively filled with the
> new key. Cryptographic property of this is one-way-ness,
> as it is impossible to invert E{K}K not knowing the key. 
> Whether this is a desired property, is left for the
> discussion.
> 
> --------------020208050107040706040902--
> 
> _______________________________________________
> Cfrg mailing list
> [email-masked]
> https://www1.ietf.org/mailman/listinfo/cfrg
> 
_______________________________________________
Cfrg mailing list
[email-masked]
https://www1.ietf.org/mailman/listinfo/cfrg

---

From: Uri Blumenthal <[email-masked]>
Date: Mon, 24 Mar 2003 18:32:32 -0500

Ran Canetti wrote:
> Uri,
> 
> Few remarks:
> 
> 1. I think that there is some terminology confusion here with respect
 > to the meaning of the name "pseudorandom function" (PRF).

Yes, it seems so.

 > In the cryptographic

OK. You're certainly correct on all te counts here.

I'm considering two choices. One is to leave this suggestion as is,
possibly tweak it a bit. Another possibility - to modify it to make
it "really" provable, but the concern here is to lose performance.

What would your preference/recommendation be?

> 2. In crypto-theory, a PRF is guaranteed to provide security only when
 > its key is SECRET and RANDOM (ie, uniformly distributed).

Yes. In my mind the word "random" is stuck in the same bin as
"random number generator". "Uniformly distributed" is what it
is. Thanks for bringing this up!

> If the key is either not secret or not random then all bets are
 > off - no security whatsoever is guaranteed.

I thought that the "degree" of non-randomness - i.e. fixing only
a certain part of the key - reduced the workload of adversary,
i.e. lowered the security guarantees ("resistance"), but didn't
invalidate the whole thing?

> is SECRET and RANDOM. Nothing is required when the key is either not secret

I see.

> This corresponds to your steps 1-4.

Yes. I'd like to discuss with you why no distinction between S and N
is needed here.

> "pseudorandom", even if the input is neither completely random nor

Yes, assuming the input contains "enough" of secret and the secret
part is distributed uniformly "enough".

> Certainly, this property that you need from H does not follow from 

I understand. Thanks.

> assumptions on/ modeling of AES.)

I'd like to discuss this off-line. OK?

> Hope this makes sense.

It makes a lot of sense!

---

From: [email-masked] (David Wagner)
Date: 24 Mar 2003 23:24:01 GMT

>invalidate the whole thing?

No.  Ran is right.

If you fix a few bits of the key to a PRP, all bets are off
(unless you make extra assumptions beyond just that it's a PRP).
See my counterexample posted on the IPSec mailing list.
_______________________________________________
Cfrg mailing list
[email-masked]
https://www1.ietf.org/mailman/listinfo/cfrg

---

From: David Hopwood <[email-masked]>
Date: Mon, 24 Mar 2003 10:42:19 +0000

-----BEGIN PGP SIGNED MESSAGE-----

> (unless you make extra assumptions beyond just that it's a PRP).

In general, if you fix k bits then the bound on the success probability of
an attack is degraded by a factor of 2^k. (This is not the same as reducing
the workload.)

The intuition behind this is that there is a 2^-k probability of an
attacker who assumes that the k bits are fixed, having that assumption
satisfied by chance for the unmodified PRP. Therefore the success probability
cannot be multiplied by more than 2^k. Actually the same argument applies for
any keyed algorithm.

Of course for sufficiently large k, this is effectively the same thing as
"all bets are off". For k < 8, say, it is probably harmless. Anyway, this
argument does not in any way justify using non-secret or non-random keys,
unless you know that they are only "slightly" non-random.

- -- 
David Hopwood <[email-masked]>

Home page & PGP public key: http://www.users.zetnet.co.uk/hopwood/
RSA 2048-bit; fingerprint 71 8E A6 23 0E D3 4C E5  0F 69 8C D4 FA 66 15 01
Nothing in this message is intended to be legally binding. If I revoke a
public key but refuse to specify why, it is because the private key has been
seized under the Regulation of Investigatory Powers Act; see www.fipr.org/rip

---

From: Uri Blumenthal <[email-masked]>
Date: Tue, 25 Mar 2003 13:26:48 -0500

> an attack is degraded by a factor of 2^k. (This is not the same as reducing

Well, this makes perfect sense. And it's precisely what I expected to 
see (as opposite to "no matter what all bets are off").

> cannot be multiplied by more than 2^k. Actually the same argument applies for

Great! Thanks!

> unless you know that they are only "slightly" non-random.

In pratice - but not in theory, right? Because the theory deals with
the degradation - which is quantifiable? So if only 8 out of 128 key
bits are random - it still means degradation by 2^120, not "all bets
are off"?

Thanks!

Regards,
Uri.

---

From: Scott Fluhrer <[email-masked]>
Date: Tue, 25 Mar 2003 13:47:18 -0800

Here is a counter-proposal for an AES-based PRF:

Definitions:

b is the size of the block of the underlying block cipher.  We'll assume 
it's a multiple of 8.
k is the size of the key of the underlying block cipher.
|| is bitstring concatenation.
^ is bitwise exclusive or.
E_k(X) is the block encryption, using the underlying block cipher, with the 
key k, of the block X.
E*_k(X) is the output of the underlying block cipher in OFB mode, with the 
key k, and the initial block X.  Specifically,
    E*_k(X) = E_k(X) || E_k(E_k(X)) || E_k(E_k(E_k(X))) || ...
    Note that, if only b bits are required from E*_k(X), the output is 
identical to E_k(X).
S is the secret key of the PRF.  It MUST be at least k bits long, and less 
than 2^32 bits long.
N is the (possibly) public parameter to the PRF.  It MUST be at most 
2^{b/2} bits long.

To compute PRF(S, N), you follow the following steps:

1. Assign:
     K = The first k bits of S.
     K2 = The remaining bits of S
     M = Length(K2) || K2 || N
        where Length(K2) is the length of K2 in bits, expressed as a 32 bit 
quantity in Network order.
        M will be looked upon as a concatenation of n blocks, M[1], ..., 
M[n], where M[1],...,M[n-1] are b bits long, and M[n] is between 1 and b 
bits long.

2 Derive 3 k-bit keys (K1, K2 and K3) from the key K, as follows:
       K1 = E*_k(0x0101...01)
       K2 = E*_k(0x0202...02)
       K3 = E*_k(0x0303...03)

3. Define F[0] = 0x00000000000000000000000000000000

4. For each block M[i], where i = 1 ... n-1:
      XOR M[i] with F[i-1], then encrypt the result with Key K1, yielding F[i].
      (that is, F[i] = E_K1( M[i] ^ F[i-1] )

5. For block M[n]:

      (a) If the blocksize of M[n] is b bits:
         XOR M[n] with F[n-1] and Key K2, then generate OFB mode output 
with Key K2, yielding X.
         (that is, X = E*_K2( M[n] ^ F[n-1] )

      (b) If the blocksize of M[n] is less than b bits:
          (i) Pad M[n] with a single "1" bit, followed by the number of "0" 
bits (possibly none) required to increase M[n]'s blocksize to b bits.
          (ii) XOR M[n] with F[n-1] and Key K3, then generate OFB mode 
output with Key K3, yielding X.
             (that is, X = E*_K3( M[n] ^ F[n-1] )

6. Return the OFB output, with a zero starting block, of the key X, namely 
E*_X(0x00...00)
    This step is identical to step 5 of Uri's proposal.

Similarities to Uri's proposal:

In both cases, we run a MAC-like construction with S and N to generate a 
key, and then run the key in OFB mode to generate the output.  However, I 
replaced Uri's MAC-like construction with a generalization of XCBC-MAC.

Advantages of this proposal over Uri's:

1. This reduces the number of times the implementation needs to run the AES 
key scheduling to 4 times (only once if you compute based on the same S 
value multiple times, and you precompute the key schedules for K1, K2, K3).

2. If you use AES-128 as the block cipher, then steps 2 through 5 is 
precisely the XCBC MAC found in the draft-ietf-ipsec-ciph-aes-xcbc-mac-03 
(except we don't truncate the output to 96 bits, and assuming I didn't 
introduce a typo somewhere)  This means that an implementation that already 
implements XCBC can reuse that implementation here, rather than creating a 
separate control structure.

3. It also fixes the weaknesses:
     PRF(A, B) = PRF(A, B||0) (where 0 is a single 0 bit, and assuming that 
appending the 0 bit didn't cause the PRF to encrypt another block).
     PRF(A || B, C) = PRF(A, B || C) (when the length of A >= k)
     These weaknesses might not have mattered in the IKE environment, but 
we might as well clean them up anyway.

Disadvantages of this proposal (that I know about):

1. I have yet to do any sort of formal security review.  The review for the 
k=b case should be straightforward, the k>b case appears to be considerably 
trickier.  Should we insist that k=b (especially given that it's not 
obvious whether AES-256 gives you more security than AES-128 within this 
construction)?

2. For a fixed S, PRF(S, N) can take on only 2^{b} values.  Hence, a 
particular S should be used no more than 2^{b/2} times.

3. I did generalize XCBC to handle both the k>b case, and the case where 
the length of S is greater than k -- do either of these modifications 
invalidate the security proofs for XCBC?  I don't think so, but that should 
be checked.  Or, is there a standard (i.e. already proven) way of 
generalizing XCBC that we can take advantage of?

--
scott

---

From: [email-masked] (David Wagner)
Date: 26 Mar 2003 06:06:48 GMT

>Here is a counter-proposal for an AES-based PRF:

I'm worried there may be some confusion here.

Your counter-proposal looks like a perfectly fine pseudorandom function.
However, I don't think it's a good replacement for SHA1-HMAC in IKE,
i.e., it's not as great an instantiation of IKE's "PRF".

At this point, I can almost hear you saying "Huh??".  What's going on here
is some confusing terminology, as Hugo mentioned earlier.  IKE's "PRF"
really should be more than just any old pseudorandom function; idealy,
it should also have some random oracle like properties.

How is IKE's "PRF" used?  If F is your instantiation of IKE's "PRF",
then IKE will compute F(g^xy, N) where g^xy is the result of a Diffie
Hellman exchange and N is some (possibly public) nonce.  What security
assumptions do we need for this to be secure?  It turns out that *either*
of the following two pairs of assumptions suffice.
   (a) If F is a pseudorandom function and DDH is hard,
       then IKE will be secure.
          and also:
   (b) If F is a random oracle and plain DH is hard,
       then IKE will be secure.
Recall that plain DH is the problem of computing g^xy from (g,g^x,g^y),
while DDH is the problem of distinguishing g^xy from g^z given
(g,g^x,g^y).  A pseudorandom function requires that its key be uniformly
distributed, or at least indistinguishable from uniform.  If F is a
generic pseudorandom function, then we're going to require that DDH
be hard (which will imply, under suitable side conditions, that g^xy
is indistinguishable from uniform); plain DH won't suffice.  However,
if F also some random oracle like properties, then all we need is that
plain DH be hard.

When we use F = SHA1-HMAC, this gives us some nice properties.  Recall
that DDH is a mildly questionable assumption; also, the random oracle
model is mildly questionable as well.  However, the above property
of IKE will ensure that if *either* DDH is hard *or* F behaves like a
random oracle, then IKE will be secure.  This is a really nice property:
it gives IKE a belt-and-suspenders kind of security.  (I'm assuming that
plain DH is hard and that F is a pseudorandom function; these assumptions
are probably much more realistic.)

With all that background, now I can say why your counter-proposal is
not quite as nice as SHA1-HMAC.  It's not as nice, because it seems
unlikely that your counter-proposal behaves like a random oracle.
In particular, property (b) from above has little hope of being true.
We lose the belt-and-suspenders strength.

For this reason, what we'd really like is a function F that's
  (1) hardware-friendly (i.e., uses only AES);
  (2) almost certainly a pseudorandom function
      (i.e., we can prove F is a PRF if AES is a PRP); and,
  (3) stands some chance of behaving like a random oracle
      (e.g., we can prove F behaves like a random oracle if AES
       is modelled as an ideal cipher).
This seems quite challenging to achieve.  And, even if we can achieve it,
its security still might not be quite as attractive as SHA1: I have less
confidence that AES can be safely modelled as an ideal cipher than that
SHA1 can be safely modelled as a random oracle, because I don't have
a great deal of confidence that AES's key schedule is super-strong.
And yet, there are good reasons to want an AES-only "PRF" for IKE,
so I don't really know what to do about this conundrum.
_______________________________________________
Cfrg mailing list
[email-masked]
https://www1.ietf.org/mailman/listinfo/cfrg

---

From: John Viega <[email-masked]>
Date: Wed, 26 Mar 2003 07:50:18 -0500

> so I don't really know what to do about this conundrum.

Earlier I mentioned that PKCS#5 would certainly fit the requirements 
above, and would have real general-purpose flexibility.  If it's too 
complex for people's tastes, one could also use HMAC with Davies-Meyer 
or Matyas-Myer-Oseas as the hash function, or wait 1.5 years for the 
MDC2 patent to expire.

I don't see an issue if you're willing to live with AES modeled as an 
ideal cipher.  I think the real hard problem is coming up with a 
construction that only needs to assume that AES is a PRP.

John

---

From: John Viega <[email-masked]>
Date: Wed, 26 Mar 2003 07:47:33 -0500

John

---

From: "David A. Mcgrew" <[email-masked]>
Date: Wed, 26 Mar 2003 10:31:29 -0800

Scott,

using xcbc the way that you did in your construction seems like a good idea; it
has the right properties prf-wise.

As David Wagner mentioned, we may want a random oracle rather than a prf for
ike.  But an efficient keyed prf with variable input length would have some
other nice uses.  In particular, I'm thinking that if counter mode had the
variable-input-length capability, then there would never be a need to debate the
format of the counter.   It would be easier to just use a prf that could accept
all of the inputs one might want to provide.  Also, it would be usable in
situations where it cannot easily be used at present.  For example, in some
protocol there may be a 160-bit nonce, such as an ipv6 address concatenated with
a 32-bit sequence number.

There would be some security degradation relative to vanilla-flavored ofb or ctr
if the number of invocations of the prf was close to 2^64 (for aes), but perhaps
that effect is manageable by just limiting the number of invocations.

David

> -----Original Message-----
> From: [email-masked] [mailto:[email-masked]]On Behalf Of Scott
> Fluhrer
> Sent: Tuesday, March 25, 2003 1:47 PM
> To: [email-masked]
> Cc: Uri Blumenthal
> Subject: Re: [Cfrg] AES-based PRF - comment please
>
>

---

From: Uri Blumenthal <[email-masked]>
Date: Wed, 26 Mar 2003 17:24:29 -0500

So as far as I see, the advantage of Scott's proposal is using
an "officially blessed" XCBC. The disadvantage - being "just"
a PRF.  The solution seems to still use a two-part construct,
first part *crypto-hashing* the input, and the second part
actually producing pseudo random output. Only this way
we can get to the "belt-and-suspenders" level (IMHO).

The following two questions is for everybody, especially for
D. Wagner.

1. If a Secure Hash function is build of AES block cipher,
    will you accept it as Random Oracle (i.e. would you
    extend to it your "mildly questionable" status you
    grant SHA)?

2. If for security proofs of AES-based crypto-hash, one
    uses black-box assumption, would this be OK with you?
    [Being PRP is insufficient, being ideal cipher is too
    strong.]

3. [I lied: I had a third question :-] To randomize OFB
    starting point I want to take two bytes of DH output
    to use as offset counter. Any problem with that?

Thanks!

---

From: [email-masked] (David Wagner)
Date: 26 Mar 2003 22:23:28 GMT

>    extend to it your "mildly questionable" status you

If we have a proof that your F behaves like a random oracle
(or is good for IKE when only plain DH, but not DDH, holds),
assuming AES can be modelled as an ideal cipher, then my answer
would be: Yes.

This is all modulo my remarks about being more uncomfortable
about modelling AES as an ideal cipher than I am modelling
SHA1 as a random oracle.  But it seems to be the best we have
any hope of doing, so maybe we shouldn't put too much weight
on my discomfort.

>    [Being PRP is insufficient, being ideal cipher is too

What's the black-box assumption?  Is it different from the
ideal cipher model?  I'm not familiar with this distinction.

>    to use as offset counter. Any problem with that?

Depends what properties you want from it.  If DDH holds, then
those two bytes should be pseudorandom and computationally
independent of everything else.  If only plain DH holds, then
there are few guarantees one can make about those two bytes.
_______________________________________________
Cfrg mailing list
[email-masked]
https://www1.ietf.org/mailman/listinfo/cfrg

---

From: Uri Blumenthal <[email-masked]>
Date: Wed, 26 Mar 2003 18:28:17 -0500

> assuming AES can be modelled as an ideal cipher, then my answer

Is there a proof that SHA-1 behaves like a random oracle?

I thought is is assumed about pretty much any secure hash with
provable collision resistance guarantees, especially when there
is a reason to believe it's also a PRF?

Ideal cipher assumption would be too strong - hopefully
black-box assumption is sufficient.

> any hope of doing, so maybe we shouldn't put too much weight

(:-)

> ideal cipher model?  I'm not familiar with this distinction.

Black-box assumption is a weaker requirement than ideal cipher.
Here you treat your block cipher as a black box - you cannot
"pick inside" the cipher engine. You give key, input and
get output (encrypt and decrypt).

But unlike ideal cipher, you make no assumption about the key.
As I understand, in an "ideal cipher"

> there are few guarantees one can make about those two bytes.

This is not for proof, just for practicality. To avoid
precomputation attack, I want to offset the starting
point of OFB. It would make sense to use something
that hasn't come through the "hashing engine" yet.
So I'd need some unknown, preferably unpredictable
and maybe somewhat random bytes. Two LSBytes from
g^ir seem like a good choice? Any other place...?

---

From: [email-masked] (David Wagner)
Date: 26 Mar 2003 23:14:17 GMT

>Is there a proof that SHA-1 behaves like a random oracle?

You're kidding, right?  No, there's no proof; it's not something
that can be proven.

This is pretty basic stuff.  Would it be helpful for me to refer
you back to the original Bellare and Rogaway paper on random oracles,
or to other work in the literature on the random oracle model?
It sounds like it might help to clear up confusion about things like,
"What is the random oracle model?  What does a proof in the random
oracle model look like?  What does it imply about the security of
a concrete construct?".  Those questions have been pretty well treated
in the cryptography literature, so I'm reluctant to write a lengthy
tutorial on the topic here.

If you already know all this, I apologize.

>As I understand, in an "ideal cipher"

I understood each of those words, but I can't figure out what precisely
you meant by that paragraph.
_______________________________________________
Cfrg mailing list
[email-masked]
https://www1.ietf.org/mailman/listinfo/cfrg

---

From: Greg Rose <[email-masked]>
Date: Thu, 27 Mar 2003 13:23:47 +1100

>You're kidding, right?  No, there's no proof; it's not something

Actually, wasn't there a paper at Crypto either last year or the one 
before, that I didn't understand, that proved that no simple algorithm 
*could* be a random oracle?

Anyway, SHA-1 might be good, but it pretty certainly isn't one.

Greg.

Greg Rose                                       INTERNET: [email-masked]
Qualcomm Australia          VOICE:  +61-2-9817 4188   FAX: +61-2-9817 5199
Level 3, 230 Victoria Road,                http://people.qualcomm.com/ggr/
Gladesville NSW 2111    232B EC8F 44C6 C853 D68F  E107 E6BF CD2F 1081 A37C

---

From: [email-masked] (David Wagner)
Date: 27 Mar 2003 02:50:37 GMT

>*could* be a random oracle?

It doesn't make sense to say that SHA1 is a random oracle; they're just
two entirely different kinds of beasts.  If we're among friends, we
could talk informally about whether SHA1 "behaves like a random oracle",
but this terminology is arguably sloppy.  (I plead guilty.)

To convey what I'm really trying to get at when I write sentences like
this, maybe I'd better back up a little bit.

Aww, heck.  I was too lazy to write a tutorial on the random oracle
model, but I can see if I don't explain a little, my posts here won't
make any sense.  I suppose I might as well bite the bullet and write a
little summary.  :-)  So, here goes.

Let's do a thought experiment.  Suppose we take a protocol that uses
SHA1 somehow, idealize the protocol by replacing the hash function with
a random oracle, and prove that the resulting idealized version is secure
in the random oracle model.  What can we say about the original protocol?

As it happens, the answer is: absolutely nothing.  It's entirely possible
that the original protocol could be insecure when used with SHA1, despite
the proof of security in the random oracle model for the idealization.
There are examples of protocols that are insecure when used with SHA1 but
can be proven secure in the random oracle model.  Intuitively speaking,
this troubling scenario could happen if the original protocol "interacted
badly" with SHA1.

(Indeed, I believe it's possible that the original protocol would be
insecure *no matter what hash function you used*, which says that even
if SHA1 were as good as any hash function could ever be, the original
protocol might be insecure.  This is even more mysterious.)

So why bother with the random oracle model in the first place?  Ahh,
now we've got our finger on the source of the controversy.  Some people
might tell you that, because of the existence of such a counterexample,
the random oracle model has little value.  I prefer, instead, to think
that the random oracle model has great value, but it must be used with
caution -- we daren't confuse it with an ironclad guarantee of security.

What a proof of security in the random oracle model tells you is that
the protocol is secure against generic attacks; any successful attack
probably must somehow exploit something about the structure of SHA1.
When you consider how many protocols have turned out to be insecure
against generic attacks, that's an awfully useful thing to know, IMHO.

By the way, whenever you hear the word "proof" in the context of the
random oracle model, you should be aware that the word can be a little bit
deceiving.  Don't expect anything provable about your original protocol.
When you hear the phrase "proof of security in the random oracle", think
"an argument that it's plausible to believe that the protocol is secure".

Are proofs in reduction-based cryptography any better?  (By
reduction-based crypto, I mean the complexity-theoretic stuff that uses
concrete reductions, with no random oracles.)  I claim "yes", but I have
to be a little careful in justifying this answer.  It's true that when
you hear about a "proof of security" in the context of reduction-based
analysis, typically there is some computational assumption, like
that factoring is hard.  In some sense the word "proof" can still be
deceptive in the reduction-based setting, since there's still this
unproven assumption.  However, it is arguably a little less deceptive,
because at least we have a well-specified assumption.  In contrast, the
random oracle model is not an assumption.  It is a modelling process,
but there is no precise assumption we can point to that is either true
or false and that we can try to gain confidence in.

For more, read my article with Bruce in Cryptogram:
  http://www.counterpane.com/crypto-gram-0301.html#7
Then, read my letter, Phil Rogaway's letter (Sections 2.2,2.3), and John
Black's letter to NIST about RMAC:
  http://csrc.nist.gov/CryptoToolkit/modes/comments/
Now you know some of the background of the random oracle controversy.
I hope it helped.  Also, I hope I didn't make any mistakes!
_______________________________________________
Cfrg mailing list
[email-masked]
https://www1.ietf.org/mailman/listinfo/cfrg

---

From: Bodo Moeller <[email-masked]>
Date: Thu, 27 Mar 2003 13:58:43 +0100

> protocol might be insecure.  This is even more mysterious.)

Papers on this "mysterious" effect are the following:

@InProceedings{Canetti_et_al:1998,
  author = 	 {Canetti, Ran and Goldreich, Oded and Halevi, Shai},
  title = 	 {The Random Oracle Methodology, Revisited},
  booktitle = 	 {30th {ACM} Symposium on Theory of Computing ({STOC})},
  pages =	 {209--218},
  year =	 1998,
}

@Misc{Canetti_et_al:2000,
  author = 	 {Canetti, Ran and Goldreich, Oded and Halevi, Shai},
  title = 	 {The Random Oracle Methodology, Revisited},
  howpublished = {E-print cs.CR/0010019},
  year =	 2000,
  note =         {Available from \url{http://arXiv.org/abs/cs/0010019}}
}

@Misc{Goldwasser/Taumann:2003,
  author = 	 {Goldwasser, Shafi and Taumann, Yael},
  title = 	 {On the (In)security of the {F}iat-{S}hamir Paradigm},
  howpublished = {Cryptology ePrint Archive Report 2003/034},
  year =	 2003,
  note =         {Available from \url{http://eprint.iacr.org/}}
}

It should be noted that all such counterexamples make statements about
*asymptotic* security: they assume that a fixed description of the
hash function is used across all security parameters and exploit
anomalies in this setting.  But to me, the random oracle methodology
is something that you can resort to if you want to *avoid* asymptotic
security considerations.  Please read on:

> because at least we have a well-specified assumption.

One the other hand, such reduction-based proofs make only asymptotic
statements, since the underlying assumptions (such as intractability
of factoring) are asymptotic.  Roughly, the security result says that
for any given adversary, there is a security parameter such that the
cryptographic scheme is secure.  But in practice, we have to pick
some specific security parameter and want the system to be secure
against all adversaries.  Unfortunately, while factoring may be hard,
factoring 2048-bit integers (or integers of any other fixed size) is a
O(1)  problem, so proofs in the reduction-based approach don't really
tell us anything about deployable systems.

Of course, such proofs can still be considered valuable heuristic
results -- we hope that the concrete choice of the security parameter
will be large enough such that the asymptotic result has a close
correspondence to reality.

>                                                        In contrast, the

Either methodology has its inherent problems.  Just as no specific
choice of a hash function can be a "random oracle", no specific choice
of a security parameter can be "asymptotic".  If we do not have
information-theoretic security, we cannot prove anything about the
security of deployable systems unless we cheat *some* way.  If we want
results that are not merely asymptotic, we can resort to random
oracles as an idealization of what is really going on; if we want
results that do not involve random oracles, we can resort to systems
with an unbounded security parameter as an idealization of what is
really going on.  In any case, what we do could be denounced as
playing shell games with quantifieres.  A more positive view is to
acknowledge that in both cases we end up relying on heuristical
considerations, and that we cannot get far if we are not willing to do
so.

-- 
Bodo Möller <[email-masked]>
PGP http://www.informatik.tu-darmstadt.de/TI/Mitarbeiter/moeller/0x36d2c658.html
* TU Darmstadt, Theoretische Informatik, Alexanderstr. 10, D-64283 Darmstadt
* Tel. +49-6151-16-6628, Fax +49-6151-16-6036
_______________________________________________
Cfrg mailing list
[email-masked]
https://www1.ietf.org/mailman/listinfo/cfrg

---

From: "Anton Stiglic" <[email-masked]>
Date: Thu, 27 Mar 2003 12:00:14 -0500

----- Original Message -----
From: "Bodo Moeller" <[email-masked]>
> [...]
> > [...]
> of factoring) are asymptotic.

I see two types of "reduction-based" cryptographic proofs.
In one case you use asymptotic analysis, in the other you use concrete
security analysis.  The example that David gave, with factoring, fits
in the asymptotic case, in which case I agree with Bodo that this is
no better than working in the random oracle model for example.
But I think (?) that David might have been thinking about the concrete
security analysis case, which usually provides for a better proof in my
point
of view.
Here I'm thinking about the concrete security proofs for HMAC,
CBC-MAC, etc., which assume very specific things about the underlying
primitives (for example that the compression function an iterated hash
function, or a block cipher, acts as a good finite input-length PRF).
For example, I prefer to only need to assume that the compression function
of SHA1 acts as a good good PRF, then to assume that SHA1 used in
some way acts as a random oracle.

It's true that at the end we are always assuming something, unless
we have some information-theoretic proof (unconditional security).
But you need to be careful here as well, even some proclaimed
"unconditionally secure" scheme can sometimes assume something
(for example, some unconditionally secure multiparty computation
schemes assume a secure channel and other stuff...).

--Anton
--Anton

---

From: Uri Blumenthal <[email-masked]>
Date: Thu, 27 Mar 2003 11:56:39 -0500

>>> If we have a proof that your F behaves like a random oracle
                  **********************************************

>>> assuming AES can be modelled as an ideal cipher, then my answer

so I asked

>> Is there a proof that SHA-1 behaves like a random oracle?

and you say

 > No, there's no proof; it's not something that can be proven.
 > You're kidding, right?

So why do you want a proof that another secure hash (AES-based)
behaves like a random oracle?

As for kidding, I'm just trying to get "equal treatment" for SHA
and AES-based crypto hash - assuming that proofs are brought
regarding colision resistance and non-invertibility of
AES-based hash. [Note: AES key sxpansion design includes
resistance to attacks when the cipher is used as a compression
function of a hash.]

Regarding references to the original papers - I wouldn't
mind. I'd also gratefully accept a Postscript version of
any paper you think might be bneficial for me to read on
the subject (or PDF version :-). [Probably I know some
of what's in there, but certainly don't know all of
it, and would like to learn more.]

> ideal cipher model?  I'm not familiar with this distinction.

As far as I know, black box model of block ciphers dates back to
Shannon [Communication Theory of Secrecy Systems, Bell Systems
Technical Journal, 28(4):656-715, 1949]...

In essence it means: treat the block cipher as a black box - you
know nothing of its internals (and have no access to them, so
you cannot mount an attack which is specific to the internal
structure of this cipher).

IMHO it differs from the ideal cipher model in the following:
ideal cipher assumes that if your N-bit key has only K bits
of randomness, your cipher is still K-bit secure. Black
box doesn't make this assumption.

Also, I was given an excellent paper (Black, Rogaway, Shrimpton)
that offers security proofs for various crypto hash constructs
based on AES. I will gladly share it with you if you'd like.

Regards,
Uri.

P.S. Thanks to all those who commented and is commenting on the
proposed construct. I'm utilizing the comments and am modifying
it to make it both better and secure.

---

From: Bodo Moeller <[email-masked]>
Date: Thu, 27 Mar 2003 18:49:37 +0100

> security analysis.
[...]
> function, or a block cipher, acts as a good finite input-length PRF).

Good that you mention this.  This reduction-based concrete-security
approach is a style of proof that I prefer, but I don't quite agree
that in such proofs you assume very specific things about the
underlying primitives in the way that asymptotic analysis does.
Saying that a function "acts as a good PRF" rather makes assumptions
about the adversary -- namely that the adversary cannot well
distinguish the function from a random one.

To justify such assumptions (after all, what we really want is a
security result that applies to all adversaries that one could
encounter), one might sometimes use asymptotic security
considerations, or a random oracle assumption.  The high-level view of
the reduction-based concrete-security approach keeps the problems of
these methodologies out of view, but does not really avoid them.

> we have some information-theoretic proof (unconditional security).

Even information-theoretic proofs such as the one for the Vernam
encryption scheme do not really apply to deployed systems.  They will
typically assume that some key  K  is perfectly random, whereas in
actual implementations, there will usually be some bias.  However
miniscule it may be, this means that ciphertexts will reveal at least
a tiny amount of information on the corresponding plaintexts.
Typically the bias will be small enough so that it does not really
matter at all, and no-one will know the details about the bias that
would be necessary to exploit it; but we should keep in mind that
perfect information-theoretical security remains a mathematical utopia
an epsilon away.

---

From: [email-masked] (David Wagner)
Date: 27 Mar 2003 18:08:58 GMT

>distinguish the function from a random one.

Hmm.  Well, I guess that's not how I interpret such statements.  When I
say "AES-XCBC-MAC makes a good PRF", I really mean that there is *no*
attack.  This is different from assuming that if there is an attack, my
specific enemies can't find it.  Thus, saying "AES-XCBC-MAC is a good
PRF" is (to me) not making assumptions about my adversary's state of
knowledge; for me, it is making assumptions about an inherent property
of AES-XCBC-MAC.  Those assumptions might be either true or false,
but at least they are specific.  That's one viewpoint, anyway.

It is true that anytime I use computational cryptosystems (rather
than information-theoretic cryptosystem), I will have to make some
assumptions about the resources available to my adversary.  For instance,
I might assume that my adversary will not spend more than $1 billion to
break my system.  Fortunately, I believe these assumptions can be made
very plausible.  For instance, if we use modern 128-bit block ciphers,
we end up with assumptions like that the adversary can't do 2^100 steps
of computation -- a very believable assumption.

>actual implementations, there will usually be some bias.

Yes, it's true.  Good point.

But I guess the partial good news is that this is a different sort of
assumption.  It is an assumption that our mathematical model faithfully
models the real world.  That has a slightly different character from
the assumption that AES is a PRP with such-and-such parameters or that
factoring is this hard for 1024-bit RSA composites.  Anytime you use
mathematics, you have to check whether your mathematical model is accurate
-- that's unavoidable -- but the complexity-theoretic assumptions are
something else.

In short, computational-theoretic cryptosystems have to make two
assumptions (the complexity-theoretic assumption *and* the modelling
assumption), while information-theoretic cryptosystems have to make one
assumption (the modelling assumption).  This does seem like a potential
advantage for information-theoretic cryptography, even if "proofs of
information-theoretic security" aren't an absolutely iron-clad guarantee
of security for your deployed cryptosystem.
_______________________________________________
Cfrg mailing list
[email-masked]
https://www1.ietf.org/mailman/listinfo/cfrg

---

From: [email-masked] (David Wagner)
Date: 27 Mar 2003 17:58:57 GMT

>of factoring) are asymptotic.

I wasn't trying to distinguish between asymptotic vs. not.  However,
I'd count both "concrete security" results and "asymptotic" results
within the category of reduction-based proofs.  I certain agree that
concrete security results tend to be much more useful in practice
than asymptotic results.  So, maybe I should amend my statement to
say that reduction-based concrete security is my preferred paradigm,
when applicable.
_______________________________________________
Cfrg mailing list
[email-masked]
https://www1.ietf.org/mailman/listinfo/cfrg

---

From: [email-masked] (David Wagner)
Date: 27 Mar 2003 18:54:36 GMT

Uri Blumenthal  wrote:
>David Wagner wrote:
>>>> If we have a proof that your F behaves like a random oracle,
>>>> [then I'll accept the claim that it behaves as a random oracle]
[and later]
> > No, there's no proof [that SHA-1 behaves like a random oracle]
>
>[...] I'm just trying to get "equal treatment" for SHA
>and AES-based crypto hash - [...]

Yes, it sounds horribly unfair, doesn't it?  But it's not.

After years of scrutiny, noone has found any troubling anomalies
in SHA.  This gives us some reason to believe that SHA1 `behaves
like a random oracle'.  So I'd be willing to accept this ``assumption''.

But we can't say the same thing about, say, 3DES-XCBC-MAC.
We don't have years of cryptanalysis on 3DES-XCBC-MAC.  There
is corresponding argument we can make to justify such an ``assumption''
about 3DES-XCBC-MAC.

P.S. When I say that `function F behaves like a random oracle',
strictly speaking, I am being awfully sloppy with words.  What I
mean by this turn of expression is something like the following:
if you give me a proof of security for IKE in the random oracle model
when IKE's hash was replaced by a random oracle, then I'll be willing
to believe that this is evidence for the security of IKE in real life
when IKE's hash is instantiated by F.

Note that I don't take anything on blind faith.  To justify the
latter belief about IKE, I want to have some evidence that F behaves,
in some intuitive sense, "like a random function" as much as possible.
Thus, SHA1 would fit the bill, because cryptanalysts have tried
really hard to find any anomaly that indicates it is not behaving
like a random function, and they've all failed.  However, 3DES-XCBC-MAC
would not fit the bill, because we can't make such a statement.  If
we wanted to use 3DES-XCBC-MAC as our F, we'd better have some other
way to justify our faith in it, and the natural way is to ask for a
proof that 3DES-XCBC-MAC "behaves like a random oracle" under some
appropriate model or some plausible assumptions.
_______________________________________________
Cfrg mailing list
[email-masked]
https://www1.ietf.org/mailman/listinfo/cfrg

---

From: Uri Blumenthal <[email-masked]>
Date: Thu, 27 Mar 2003 15:34:14 -0500

>>>No, there's no proof [that SHA-1 behaves like a random oracle]

Actually, I'd like the full quote here:

"You're kidding, right?  No, there's no proof; it's
  not something that can be proven."

So asking for a *proof* that something behaves like a random
oracle (as you do below) does sound "horribly unfair". Because
in essence you're saying that you're not going to accept AES
no matter what, since it hasn't been under scrutiny for as
many years as SHA-1 has been.

> like a random oracle'.  So I'd be willing to accept this ``assumption''.

OK. That part I understand and accept.

> is corresponding argument we can make to justify such an ``assumption''

A reasonable (to me) justification (for the sake of the argument and
for this example) would be:

If both

(a) there's no known attack on the underlying primitive (3DES), and
(b) XCBC-MAC is not vulnerable to generic attack (when the underlying
     primitive is modelled as black box cipher [or stronger - as ideal
     cipher],

then one can assume that 3DES-XCBC-MAC "behaves like a random oracle".

If at least one of the above fails - then of course the conclusion
doesn't hold.

So for 3DES-XCBC-MAC (where 3DES, if memory serves, falls a victim
to related-key attack), the conclusion doesn't hold. For AES though,
which withstand this and other attacks, the conclusion may hold.

> when IKE's hash is instantiated by F.

Sure. I remember your "either random oracle and DH, or PRF and DDH".

> in some intuitive sense, "like a random function" as much as possible.

Yes, this is understandable. And if (a) the construct can be proven
under reasonable assumptions - such as black box cipher model, and
(b) the cipher itself shows resistance to all known attacks - I'd
say it's a reasonable evidence.

> would not fit the bill, because we can't make such a statement. 

However, in AES cryptanalysis have been trying really hard to find
any anomaly, and couldn't so far. (As far as I know, the best
result - Related Key Attack - didn't progress beyond 9th
round.)

 > If we wanted to use 3DES-XCBC-MAC as our F, we'd better have some other

How should I correlate the last statement with your previous
"it's not something that can be proven", and with the paper
mentioned by Greg that *proves* that there can be no such
proof?

---

From: [email-masked] (David Wagner)
Date: 27 Mar 2003 20:21:44 GMT

Uri Blumenthal  wrote:
>> is [no] corresponding argument we can make to justify such an ``assumption''
>> about 3DES-XCBC-MAC.
>

Yes, I agree.

(Well, in (a), we must be more precise about what we mean by
"attack".  In this case, it's not enough that 3DES be secure as
a PRP; it must `behave like an ideal cipher'.)

>to related-key attack), the conclusion doesn't hold.

Right.  3DES doesn't `behave like an ideal cipher'.
(That's one of the reasons why I picked this example.

>For AES though,

Right.

If we're willing to assume (a) for AES, then all that remains
is to prove (b) for AES.  Do you see why I asked for proof?

>result - Related Key Attack - didn't progress beyond 9th

I believe most cryptanalysis focus on whether AES is a PRP.  I think the
question of whether AES `behaves like an ideal cipher' has gotten less
scrutiny.  And when AES has been scrutinized against related-key attacks,
related-key attacks have been found to be slightly more powerful than
non-related-key attacks (for instance, in our FSE paper, related-key
attacks penetrate one round further than non-related-key attacks).
That's why I'm mildly skeptical about the latter assumption.

But I agree.  Given the need for an AES-based cryptosystem, I can see
why we'd be willing to live with a lower degree of confidence in the
"assumption" that AES `behaves like an ideal cipher'.  It seems plausible
to believe this "assumption".
_______________________________________________
Cfrg mailing list
[email-masked]
https://www1.ietf.org/mailman/listinfo/cfrg

---

From: Uri Blumenthal <[email-masked]>
Date: Thu, 27 Mar 2003 16:43:44 -0500

> a PRP; it must `behave like an ideal cipher'.)

Yes. PRP doesn't take into account key schedule weaknesses. Right?

> (That's one of the reasons why I picked this example.

:-) I know.

>> For AES though, which withstand this and other attacks,
 >> the conclusion may hold.
> 
> Right.
> 

Sure. But only now I'm getting the understanding of exactly *what*
you want to see proven.

> scrutiny. 

True. Though the designers of AES explicitly mentioned that their
key expansion was created with Related Key Attack in mind.

 > And when AES has been scrutinized against related-key attacks,

Yes, I remember this paper - you were one of the authors.
But even this attack (which was the best of the existing
ones) couldn't penetrate the whole cipher, right? So the
cipher shows tight but secure design (without a lot of
margin, I admit)?

> That's why I'm mildly skeptical about the latter assumption.

I understand.

> "assumption" that AES `behaves like an ideal cipher'.  It seems
 > plausible to believe this "assumption".

And I'm putting together a better construct - the one that has
proofs attached to it (with AES modelled as black box, and
obtaining collision resistance guarantees and non-invertibility
guarantees - the last one because block cipher itself unlike
hash may be inverted, so we need to ensure the created hash
construct can't be inverted).

Thanks!

Regards,
Uri.

---

From: David Hopwood <[email-masked]>
Date: Fri, 28 Mar 2003 11:40:26 +0000

-----BEGIN PGP SIGNED MESSAGE-----

[...]
> 2 Derive 3 k-bit keys (K1, K2 and K3) from the key K, as follows:

[ITYM  E*_K(...)]

If the entropy of S is not uniformly distributed, then any provable security
properties in the standard model are lost. In the extreme case, consider what
happens if K is known or chosen (which can possible even if S has high entropy
overall); then K1..3 are also known. OTOH, if we analyse E as an ideal cipher
then this seems to still be OK. I'm not sure to what extent it is possible to
reduce reliance on the ideal cipher model for a block-cipher-based PRF, while
allowing keys that are not entirely random.

(Note that many protocols do provide key inputs that are not entirely random to
things that they call "PRFs". David Wagner described the situation for IKE; I'd
just like to point out that in that case the key is actually an *encoding* of
g^xy, with some zero high-order bits.)

[...]
>     This step is identical to step 5 of Uri's proposal.

If E*_k(X) used CTR mode with starting nonce X, then computing large outputs
would be parallelisable and random-access. This shouldn't affect security, and
steps 2..5 are still a generalisation of XCBC-MAC (I think; this should be
checked).

Either the order of bits within bytes should be specified (big-endian), or
S and N should be restricted to byte strings. I would recommend the latter.

- --

---

From: Scott Fluhrer <[email-masked]>
Date: Thu, 27 Mar 2003 16:35:17 -0800

At 03:40 AM 3/28/2003, David Hopwood wrote:
>properties in the standard model are lost.

Yes, I realized that after I posted it (and David Wagner also essentially 
made the same point).

>In the extreme case, consider what
>-----BEGIN PGP SIGNATURE-----
>Version: 2.6.3i
>Charset: noconv
>
>iQEVAwUBPoBYIDkCAxeYt5gVAQG6KggAu9R2R9Kcm9rVXU+yPT/JmmqXzEmv6VUI
>uu+OoaMVHxAbNBO/gGmuQx0Bb8Hnp7utKwy8nJ20bLW4F0IFsYixStyiVEGkH1bn
>6V/+ATMHyWQVMnB75a12eSN8WNa6Y2RzE7YZpmfArTcHfXP0hY92n4ip47y87hp7
>yFwEGP02jLr8seHMttWOPhQFtgnPOXOOv9cQaJhnanYTBdfDJfIeCMHinQYcLKLu
>aRMIUyk7S59wW7SqFGKSeVZRkEasgACj+1XJfDjvFsm8bk7U+mEHbmUM8rm5DiSL
>lzcXW/Q7WBDaYBc8mjMf9kGkSpoT0JpX78aP8Vd2BV54V4UoAPH47g==
>=w51s
>-----END PGP SIGNATURE-----

---

From: Don Davis <[email-masked]>
Date: Thu, 27 Mar 2003 15:31:53 -0500

David Wagner wrote:
> in SHA.  ... SHA1 would fit the bill, because cryptanalysts have
> tried really hard to find any anomaly that indicates it is not
> behaving like a random function, and they've all failed.  

unfortunately, SHA1 probably hasn't gotten all of the
scrutiny its predecessors got, but for an interesting
reason.

in '96, Bart Preneel mentioned an interesting tidbit about
SHA1's prospects for survival.  Even though SHA is closely
related to MD5, Dobbertin was not _allowed_ to extend his
MD5 attack to SHA, because Dobbertin works for the German
government's Security Service, and so is forbidden by law
to undermine US federal crypto standards.  Since Dobbertin
is by far the strongest worker in the field of hash-function
inversions (RIPE-MD, MD4, MD5), SHA1 probably won't suffer
MD5's fate, even if SHA1 deserves to die.

has someone else has come along to fill dobbertin's shoes?

finally, i'll mention that before SHA1 came along, a hash
function's lifetime (spec to crack) was about 6 years.

					- don davis, boston

-

---

From: Bodo Moeller <[email-masked]>
Date: Fri, 28 Mar 2003 18:17:53 +0100

> but at least they are specific.  That's one viewpoint, anyway.

I think in the end we mean the same thing.  My point is that such
statements cannot express "very specific things" about the underlying
primitives as long as the machine model that adversaries are assumed
to run in is left unspecified.  (There are well-known natural
equivalences between different machine models, but these equivalences
again are only asymptotic, there is no canonical class of equivalent
models if you don't go into asymptotics.)

The intended meaning of a statement such as "AES-XCBC-MAC is a good
PRF" is that none of the adversaries to be considered can attack
it with more than certain success prospects.  So what are the

> of computation -- a very believable assumption.

But the formal details are left open (one "step of computation" in
some machine formalization might require many many steps in another
one).  So, if you look at what formal assumptions are conveyed by a
statement like "AES-XCBC-MAC is a good PRF", you have assumptions
about what adversaries cannot achieve, but nothing specific about
AES-XCBC-MAC taken for itself.

In principle you could fill the void and define a specific machine
model for the adversary.  Then, with respect to this particular model
(and some quantitive bounds saying when a PRF can be considered
"good"), the statement "AES-XCBC-MAC is a good PRF" would be a
specific statement that is either true or false.  But the statement is
not inherently true or false -- for some models, it will be true, for
others it will be false (and certainly one may hope that the models in
which it is false are contrived while for realistic ones it is true).

> the assumption that AES is a PRP with such-and-such parameters [...]

Absolutely.  I had not intended to imply that there is a direct
connection between these concerns about information-theoretic security
and the concerns about computational security.  I just had wanted to
comment, as a side note, on the remark that "we are always assuming
something, unless we have some information-theoretic proof" -- in
fact, even if we have an information-theoretic security proof, we have
to assume something.  While it is a different kind of something, it is
still something.

---

From: [email-masked] (David Wagner)
Date: 28 Mar 2003 18:19:10 GMT

Bodo Moeller  wrote:
>to run in is left unspecified.

Oh.  see what you mean.  You're right.  I overlooked this.
Thanks for correcting me.

Darn, interpreting these theoretical results is so tricky...
_______________________________________________
Cfrg mailing list
[email-masked]
https://www1.ietf.org/mailman/listinfo/cfrg