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

[Scott Fluhrer <sfluhrer@cisco.com>]

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

_______________________________________________
Cfrg mailing list
Cfrg@ietf.org
https://www1.ietf.org/mailman/listinfo/cfrg