Re: [STDS-P1619] Applicability of recent attacks on AES-256 to IEEE 1619 modes

[Matt Ball <matt.ball@xxxxxxxx>]

On Thu, Aug 6, 2009 at 11:44 AM, James Hughes <jphughes@xxxxxxx> wrote:

On Aug 6, 2009, at 8:55 AM, Matt Ball wrote:

Hi Folks,

I'm sure you've all seen the recent news on cryptographic breaks of AES-256.  Bruce Schneier has some good blog posts that cover these attacks:

• Biryukov, Khovratovich, and Nikoli, Distinguisher and Related-Key Attack on the Full AES-256, May 28, 2009
• Biryukov and Khovratovich, Related-key Cryptanalysis of the Full AES-192 and AES-256, June 28, 2009: (blog: http://www.schneier.com/blog/archives/2009/07/new_attack_on_a.html
• Biryukov, Dunkelman, Keller, Khovratovich, and Shamir, Key Recovery Attacks of Practical Complexity on AES Variants With Up To 10 Rounds, July 30, 2009 (blog: http://www.schneier.com/blog/archives/2009/07/another_new_aes.html)
  

So this begs the question:  Are the IEEE P1619.x family of cryptographic modes affected by these results?

If the base security of the algorithm is flawed, any mode that uses the algorithm is flawed because the proofs that XTS is secure rests on the assumption that AES is secure.

Yes and no -- The P1619 modes constrain the attacks against AES somewhat so that some of these attack techniques are not possible.

I believe that the general answer is 'no', but I'd like to hear from some cryptographers who have read the papers more closely to confirm this suspicion.  Let me know your thoughts.

The general answer is that, while AES is slowing some weaknesses, it is not broken (yet). These attacks are not feasible for recovering plaintext.

The fact is that there are no replacements for AES. Action by this working group regarding the insecurity of AES is premature. The usual progression of a flaw like this is to open a fissure that only gets wider. It is my suggestion that the group watch the actions of NIST, and if NIST abandons AES (maybe to suggest an AES2 variant or some other improvements) the group should take immediate action to follow their lead. 

Saying P1619 is secure because of some cryptanalysis of our modes is just incorrect. The statement is that "The P1619 working group is following the progress of the cryptanalysis of AES closely, and will ultimately follow and NIST recommendations regarding AES's security" is correct.

Let me restate the question more precisely:  "Do the constraints imposed by the AES-256 IEEE P1619.x family of modes allow the attacks described in any of these papers to reduce the effective key strength to less than 256-bits?"

The second paper only applies when the attacker is allowed to have extreme control over the block cipher.  In general, the P1619.x modes don't allow this level of control.  For example, both CCM and GCM use counter (CTR) mode for encryption, with a fixed-sequence counter input.  The decryption direction of AES is never used in CTR mode, making it so that the attacker doesn't necessarily have the control needed to make this attack work.

So yes its true that we need to watch the attacks closely and think of migration plans, but I'm also wondering if people will over-react and claim that AES-256 is weaker than AES-128 in all cases.

-Matt