Fwd: I like big blocks (and will say why)

[Watson Ladd]

Dear Ciphermode enthusaists,

While sitting down and writing out a HBSH based proposal (similar to
Adantium https://iacr.org/cryptodb/data/paper.php?pubkey=29245) , I
realized that there's a problem with using previous NIST primitives to
build a stream cipher with an extended nonce: the blocks are just not
that big, and we only permute them.

First there is the PRP to PRF step. Using only counter mode we have a
quadratic loss in the number of blocks, as a PRF would collide
eventually, while the counter never does until it wraps. Secondly with
128 bits there isn't a lot of room for a block counter and a nonce to
fit in: you end up with a loss in length as inputs start to get
repeated if they live in the same space, versus different. Making an
XChaCha like construction to extend the nonce space runs into the key
agility issue, and I don't think the clever structure of XChaCha
really works out for AES. If we had a XChaCha20 analogue life would be
a lot easier when making stream ciphers.

That said we do have sponges in SHA3, but that's going to take a
rather different approach to construction. Or I could do some actual
work with OCB3 like constructions for the encryption stage. However, a
bigger block hash function for use in a stream cipher would make the
analysis easier, and the downsides of big blocks vanish when
streaming.

Sincerely,
Watson Ladd

--
Astra mortemque praestare gradatim

[Paul Crowley]

At the NIST workshop on cipher modes in October, I urged NIST to standardize Rijndael-256-256, to the general support of the room. It's probably not literally the best possible 256-bit-width block cipher we could standardize today, but I'd argue that its standardization could be fast-tracked compared to any other proposal, since it is so closely related to AES and it has been a public target of cryptanalysis for 25 years. It is also amenable to acceleration using existing AES instructions on both Intel and ARM processors. This would really solve a lot of problems!

Another measure that would make building fast modes a lot easier would be the standardization of TurboSHAKE.

Note the below in Proposal of Requirements for an Accordion Mode:

--
To unsubscribe from this group, send email to ciphermodes-fo...@list.nist.gov

View this message at https://list.nist.gov/ciphermodes-forum
To unsubscribe from this group and stop receiving emails from it, send an email to ciphermodes-fo...@list.nist.gov.

[John Preuß Mattsson]

Yes,

Ericsson strongly agree that NIST should standardize Rijndael-256-256 as soon as possible. We think a block cipher with 256-bit key and block size is essential in building fast algorithms with 256-bit security, not just the accordion.

When designing a 256-bit version of MILENAGE (the key derivation algorithm found in all SIM cards in 3G-5G) we noticed that a 256-bit block size is essential for 256-bit security. The narrow 128-bit block size of AES is extremely limitinh. You can work around if but is significantly increases complexity and performance.

Another example is AES-256-GCM with random IVs. If r random nonces are sent in cleartext an attacker can find a (key, nonce)-collision with time complexity  2^97/r, i.e. the security is 97 - log2(r) bits. I don't understand why NIST is allowing GCM with random nonces. I think anything giving < 97 bit security with AES-256 should be forbidden.

We also think NIST should approve TurboSHAKE, but I don't have. a clear view on how use of TurboSHAKE would affect the accordion. We are not convinced be the restriction that the accordion is a block cipher mode.

Cheers,
John Preuß Mattsson

[Panos Kampanakis]

+1 on a wide-block permutation for the future, but don't forget we can't use it unless there is a wide-block GCM mode, or OCB mode, or arguably Accordion mode or whatever. Rijndael-256-256 on its own can't give us much because it can't be plugged in any existing modes as-is. 

[Watson Ladd]

On Fri, Jun 7, 2024 at 10:54 AM Panos Kampanakis <pan...@gmail.com> wrote:
>
> +1 on a wide-block permutation for the future, but don't forget we can't use it unless there is a wide-block GCM mode, or OCB mode, or arguably Accordion mode or whatever. Rijndael-256-256 on its own can't give us much because it can't be plugged in any existing modes as-is.

Possibly CBC. But my perspective was as someone who would design an
entry for the modes competition: having the underlying ciphers
approved is helpful in making the argument for approval of the mode,
vs. having to deal with them separately.

What I don't know about Rijndael-256 is how much the acceleration
hardware that is commonly deployed for AES works for it. I imagine
some does some doesn't.

Sincerely,
Watson

[sanketh]

> On Jun 9, 2024, at 2:23 AM, Watson Ladd <watso...@gmail.com> wrote:
>
> What I don't know about Rijndael-256 is how much the acceleration
> hardware that is commonly deployed for AES works for it. I imagine
> some does some doesn't.

This is a great question and I think it would be nice to have some concrete numbers and consensus on target hardware.

As Paul Crowley mentioned upthread Intel and ARM and a couple other ISAs implement AES acceleration using round function instructions (see Section 2.3.1 of https://eprint.iacr.org/2020/930) and therefore would also accelerate Rijndael-256/256. However, as you note, this is only a subset of hardware and many low-power devices, for instance, have crypto modules with a singular "aes128 encrypt" instruction.

My *feeling* is that it should be okay to target devices with round function instructions and let the low-power devices use Ascon. However, right now, that is just a feeling not backed by any real evidence.

> On Jun 9, 2024, at 2:23 AM, Watson Ladd <watso...@gmail.com> wrote:
>
> On Fri, Jun 7, 2024 at 10:54 AM Panos Kampanakis <pan...@gmail.com> wrote:
>>
>> +1 on a wide-block permutation for the future, but don't forget we can't use it unless there is a wide-block GCM mode, or OCB mode, or arguably Accordion mode or whatever. Rijndael-256-256 on its own can't give us much because it can't be plugged in any existing modes as-is.
>
> Possibly CBC. But my perspective was as someone who would design an
> entry for the modes competition: having the underlying ciphers
> approved is helpful in making the argument for approval of the mode,
> vs. having to deal with them separately.

Please please please no CBC in 2024. 😰 But I totally concur on separately standardizing ciphers and modes, as another person who'd love to design an entry for a future modes competition.

Best,
Sanketh

Quick disclaimer: these are *my views* and may not be shared by my collaborators or other entities I am currently or was previously affiliated with.

[John Preuß Mattsson]

GCM with Rijndael-256-256 would be quite trivial. GCM can (and should) be described as a mode for a stream cipher / keystream generator similar as done in the GCM-SST specification

https://csrc.nist.gov/csrc/media/Events/2023/third-workshop-on-block-cipher-modes-of-operation/documents/accepted-papers/Galois%20Counter%20Mode%20with%20Secure%20Short%20Tags.pdf

Watson Ladd wrote:
>But my perspective was as someone who would design an
>entry for the modes competition: having the underlying ciphers
>approved is helpful in making the argument for approval of the mode,
>vs. having to deal with them separately.

Yes. It would be very good if NIST made a clear announcement now that they will approve Rijndael-256-256 and add it to FIPS 197. Which modes to update could be discussed later.

>What I don't know about Rijndael-256 is how much the acceleration
>hardware that is commonly deployed for AES works for it. I imagine

>some does some doesn't.hardware that is commonly deployed for AES works for it. I imagine

>some does some doesn't.

My understanding is that x86, Arm, and RISC-V works and are quite fast.
https://www.springerprofessional.de/en/software-optimization-of-rijndael-for-modern-x86-64-platforms/20367064

Interfaces only supporting AES-128 or AES-256 would to my understanding not work, but a lot of AES hardware I have seen is even more limiting only supporting AES-ECB or. AES-CBC. They would not be able to support the Accordion with good performance anyway.

I think designing for a small set of existing AES APIs that does not support the round function should be a very low priority. The Accordion will likely live for the next 50 years so designing too much for existing AES APIs makes no sense and makes everyone else suffer for 50 years. If NIST must design a modes compatible with AES-128 and AES-256 APIs, I think NIST should make several accordions. Designing an 256-bit security Accordion as a mode of operation of AES-256 would likely make the Accordion more complex, less performant, and/or have worse security properties than it would otherwise have.

When designing a 256-bit version of MILENAGE, ETSI SAGE strongly recommended Rijndael-256-256 but a few companies insisted on having a AES-256 version to compare to as they already had AES-256. After ETSI SAGE provided that my feeling is that most companies in 3GPP have understood that using AES-256 is not worth it.
https://www.3gpp.org/ftp/TSG_SA/WG3_Security/TSGS3_112_Goteborg/Docs/S3-234134.zip

Paul's suggestion to base the Accordion on Rijndael-256-256 and TurboSHAKE makes a lot more sense to me than basing it on AES-256. 3DES was deprecated because the block size was just 57% of the claimed security strength. AES-256 has the same problem...

Cheers,

John

[Paul Crowley]

On Sun, 9 Jun 2024 at 23:59, John Preuß Mattsson <john.m...@gmail.com> wrote:

GCM with Rijndael-256-256 would be quite trivial. GCM can (and should) be described as a mode for a stream cipher / keystream generator similar as done in the GCM-SST specification

Sure, once we define a 256-bit polynomial - though I think there's room to improve on GCM in multiple ways, starting with clearing up the endianness confusion.

Paul's suggestion to base the Accordion on Rijndael-256-256 and TurboSHAKE makes a lot more sense to me than basing it on AES-256. 3DES was deprecated because the block size was just 57% of the claimed security strength. AES-256 has the same problem...

I didn't have in mind that a single mode would use both Rijndael-256-256 and TurboSHAKE - I imagine you'd mostly use one or the other.