Authentication
in [Cryptography]
|
Prev: Announcing a new Chaocipher-related paper: Deciphering Exhibit #1 from John F. Byrne's "Silent Years"
Next: [M-R test] Formula for p(k,t)
From: Mok-Kong Shen on 13 Aug 2010 14:00 Scott Contini wrote: > Mok-Kong Shen wrote: > > I am disappointed in myself for replying to you again > about this. > >> >> S[0] = IV; >> >> for (i=0; i<n; i++) >> { C[i] = E(K,S[i]^P[i]); >> S[i+1] = E(K,S[i]^P[i]^C[i]); >> } >> >> S[n] = authentication. >> > > > (i) If you flip a bit in the IV and flip the same bit > in the plaintext, you get the same MAC. > > (ii) If you have message M with MAC T, and message > M' with MAC T', then you can construct a new message > with MAC T'. That new message consists of first the > message M (and its IV) followed by message M', except > changing P'[0]. The new value for P'[0] is > T xor IV' xor P'[0]. This assures that the value > of C'[i] when processing the first word of the combined > message are > C'[i] = E(K,S'[i]^P'[i]) = E(K, T ^ [T xor IV' xor P'[0]]) > = E(K, IV' xor P'[0]]) > which is the same as the first word that is processed > for M'. Likewise, the same is true for the computation > of S'[i+1]. > > I refuse to be drawn into this more. If you can't see > the problem now, then you shouldn't be designing algorithms > like this. These are basic attacks. Thank you enomously for very clearly showing me where the problems with the scheme I originally posted are. I must also say that it was a sheer luck that I somehow instinctively came up with a (subsequently posted) modification that, if I don't err, happens to avoid both problems. (For in the first case S[0] is now E(K,IV), so that the effect of change of IV is unknown to the attacker. In the second case the authentication stuff being sent is now E(K,S[n]), so that S[n], which would be needed for the combined message processing, is likewise unknown to him.) Currently I am considering a possibility of avoiding to use two encryptions for processing one block, i.e. using some presumably simpler/cheaper computation in place of the one encryption of the two. It essentially goes back to some old thoughts of mine. What I have learnt here would certainly be helpful for an eventual concretization of that idea (in case it would indeed go so fat that I could request for comments and critiques). Thanking you once again, M. K. Shen
From: Maaartin on 13 Aug 2010 15:40 On Aug 13, 8:00 pm, Mok-Kong Shen <mok-kong.s...(a)t-online.de> wrote: > Currently I am considering a possibility of avoiding to use > two encryptions for processing one block, i.e. using some > presumably simpler/cheaper computation in place of the one > encryption of the two. AFAIK, that's sort of proven impossible. IIRC you need at least n +lg(n) block encryptions for encryption and authentication and there's an algorithm achieving this bound (I don't remember the paper).
From: Kristian Gj�steen on 13 Aug 2010 17:30 Maaartin <grajcar1(a)seznam.cz> wrote: >On Aug 13, 8:00�pm, Mok-Kong Shen <mok-kong.s...(a)t-online.de> wrote: >> Currently I am considering a possibility of avoiding to use >> two encryptions for processing one block, i.e. using some >> presumably simpler/cheaper computation in place of the one >> encryption of the two. > >AFAIK, that's sort of proven impossible. IIRC you need at least n >+lg(n) block encryptions for encryption and authentication and there's >an algorithm achieving this bound (I don't remember the paper). It seems to me as if OCB is better than that. -- kg
From: Mok-Kong Shen on 13 Aug 2010 17:45 Maaartin wrote: > Mok-Kong Shen wrote: >> Currently I am considering a possibility of avoiding to use >> two encryptions for processing one block, i.e. using some >> presumably simpler/cheaper computation in place of the one >> encryption of the two. > > AFAIK, that's sort of proven impossible. IIRC you need at least n > +lg(n) block encryptions for encryption and authentication and there's > an algorithm achieving this bound (I don't remember the paper). In CBC MAC, one uses the same block algorithm in two runs, once to encrypt and once to get the MAC. I am roughly thinking of the following: If one uses a coupled scheme, like the one I sketched here, it might be good enough to replace the one that computes S[i] with a block algorithm that is simpler/cheaper. (Wouldn't the lg(n) indicate something in that direction 'in effect'?) M. K. Shen
From: Greg Rose on 13 Aug 2010 18:47
In article <i44di3$149$1(a)orkan.itea.ntnu.no>, Kristian Gj�steen <kristiag+news(a)math.ntnu.no> wrote: >Maaartin <grajcar1(a)seznam.cz> wrote: >>On Aug 13, 8:00�pm, Mok-Kong Shen <mok-kong.s...(a)t-online.de> wrote: >>> Currently I am considering a possibility of avoiding to use >>> two encryptions for processing one block, i.e. using some >>> presumably simpler/cheaper computation in place of the one >>> encryption of the two. >> >>AFAIK, that's sort of proven impossible. IIRC you need at least n >>+lg(n) block encryptions for encryption and authentication and there's >>an algorithm achieving this bound (I don't remember the paper). > >It seems to me as if OCB is better than that. Yes, Rogaway's OCB mode requires one encryption per block of data, plus two extra encryptions. Gligor's mode XCBC and Jutla's original IAPM required the logarithmic number of extra encryptions. The problem with all of these modes is that they all have patents, and in at least one case the patent appears to cover the other modes as well. So technically excellent work, that won't be used for another ten years or so. Greg. -- |