Subject: [Cfrg] Authenticated encryption primitive -- SOBER-128

From: Greg Rose <[email-masked]>
Date: Sun, 11 May 2003 10:25:23 +1000

There is a need for a primitive stream cipher construction that is fast 
(faster than a block cipher in counter mode), easy to use correctly, well 
understood, freely available, and secure. SOBER-128 has been designed to 
meet these requirements, by being based entirely on a well-studied 
primitive in a manner that preserves the existing analyses.

Additionally, SOBER-128 introduces functionality (based on that of Helix, 
another recent stream cipher) to enable simultaneous calculation of a 
Message Authentication Code, and allows full integrity checking of 
partially encrypted messages.

SOBER-128 is a synchronous stream cipher designed for a secret key that is 
up to 128 bits in length. The cipher outputs the key stream in 32-bit 
blocks. SOBER-128 is a software-oriented cipher based on 32-bit operations 
(such as 32-bit XOR and addition modulo 2^32), and references to small 
fixed arrays. Consequently, SOBER-128 is at home in many computing 
environments, from firmware and smart cards to large computers. Source code 
for SOBER-128 is freely available and use of this source code, or 
independent implementations, is allowed free for any purpose.

SOBER-128 was developed from SOBER, proposed by Rose in 1998.  The ciphers 
SOBER-t16 and SOBER-t32 were submitted to the NESSIE program ; SOBER-t16 as 
a stream cipher for 128-bit key strength and SOBER-t32 as a stream cipher 
with 256-bit key strength. SOBER-t16 and SOBER-t32 proved to be among the 
strongest stream cipher submissions to NESSIE. However, both ciphers were 
found to fall short of the stringent NESSIE requirements (as were all other 
stream ciphers).

SOBER-128 is an improved version of SOBER-t32. The modifications directly 
address the concerns arising in the analyses of the t-class ciphers. The 
128-bit key strength proposed for SOBER-128 is reduced from the 256-bit key 
strength proposed for SOBER-t32 to ensure that SOBER-128 provides far in 
excess of the stated security level.

In practice, much communication is done in messages, where it is desirable 
to provide message integrity for the whole message, and privacy 
(encryption) for all or part of the message. The same secret key should be 
usable for the entire (multi-message) communication, using an 
Initialisation Vector or Nonce to distinguish individual messages. 
SOBER-128 supports this model of use.

SOBER-128 is intended to provide security under the condition that no IV is 
ever reused, that no more than 2^80 words of data are processed with one 
key, and that no data failing authentication checks will be further 
processed (in particular, that the result of decrypting a message that 
fails authentication will not be revealed). There is no requirement that 
IVs be random, which makes guaranteeing uniqueness much easier. The sender 
and recipient of secure data must agree on which parts of the data are 
encrypted, and which parts are authenticated, for correct operation, as the 
encryption operation is plaintext-aware when message authentication is 
being performed.

A 40-page design document and reference implementations of SOBER-128 may be 
found at QUALCOMM Australia's web site: http://www.qualcomm.com.au . The 
full paper is also available on the IACR eprint server, and a shorter 
version has been submitted to SAC.

-----------------------------
The above text is the basic announcement of SOBER-128, but I wanted to add 
a bit specifically for CFRG.

I'm seriously concerned about ongoing use of RC4 for, basically, anything. 
It's elegant and simple, but very often is used incorrectly, if only to the 
extent that it's often used without message authentication. The problems 
with rekeying as in WEP are devastating, and probably represent the biggest 
single failure of a deployed cryptosystem since Enigma. And lastly, the 
distinguishing attacks, at around 2^32 bytes, verge on real vulnerability 
too. We wanted to provide a credible replacement for RC4 in any of its 
modes of use. That's what SOBER-128 is.

For IETF use, obviously we need to write an RFC. I've never written an RFC 
before (in fact, blush, have never been to an IETF meeting) and could use 
some guidance on just how much information should be put in, and what 
should happen to it then.

regards,
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

_______________________________________________
Cfrg mailing list
[email-masked]
https://www1.ietf.org/mailman/listinfo/cfrg

---

From: Alex Alten <[email-masked]>
Date: Sat, 10 May 2003 23:00:28 -0700

Hello Greg,

For the public record.

Have you had any serious independent cryptanalysis done on SOBER-128
that proves that it is well designed?  It's no good throwing it to the wolves
until you can defend it properly.

As we discussed last year, apparently RC4 is not a viable cipher (its key
setup is too weak).  I wish a paper would come out with the proof so that
we can give it a proper burial.

Regards,

- Alex

At 10:25 AM 5/11/2003 +1000, Greg Rose wrote:
<snipped>

>It's elegant and simple, but very often is used incorrectly, if only to 
>the extent that it's often used without message authentication. The 
>problems with rekeying as in WEP are devastating, and probably represent 
>the biggest single failure of a deployed cryptosystem since Enigma. And 
>lastly, the distinguishing attacks, at around 2^32 bytes, verge on real 
>vulnerability too. We wanted to provide a credible replacement for RC4 in 
>any of its modes of use. That's what SOBER-128 is.
>

--

Alex Alten
[email-masked]

---

From: John Viega <[email-masked]>
Date: Sun, 11 May 2003 02:46:21 -0400

Greg's work is about as well analyzed as any viable stream cipher is, 
which isn't saying that much compared to the kind of scrutiny AES saw.

In all fairness, key setup problems alone aren't enough to make RC4 
non-viable.  That doesn't reflect poorly on the actual encryption 
algorithm, and there are two recommended strategies for mitigating the 
problem... pass the key material through a PRF first, or discard the 
first 256 outputs.  Both thwart the Fluhrer et al. attack.  The paper 
on the attack:

http://www.eyetap.org/~rguerra/toronto2001/rc4_ksaproc.pdf

If that were the only problem, no one would have major reservations 
with RC4 beyond the difficulty of using it securely (which is already a 
problem with most stream ciphers).  However, Fluhrer and McGrew have an 
attack that distinguishes RC4 from random with high probability after 
2^30 outputs.  They also had some other fairly damning observations.  
See:

http://www.mindspring.com/~dmcgrew/rc4-03.pdf

That's a bit more worrisome from my perspective, but then again, it's 
only a one-bit information leak after 2^30 outputs, which is not all 
that big a risk in the real world on a 128-bit key.

I do agree that we should be looking at better solutions, such as 
Greg's work.  Particularly, people use RC4 because of it's software 
speed, and there are faster, more secure algorithms for software 
environments out there.  I'm fond of SNOW 2.0, myself:

http://www.it.lth.se/cryptology/snow/

While it is not authenticating, as is Greg's scheme, it is easy to 
combine a stand-alone stream cipher with a MAC that is fast in software 
using a universal hash.  Just hash the ciphertext, then take a few more 
keystream bytes to mix in with the hash value (which needs to be done 
carefully).

Bernstein's hash127 (http://cr.yp.to/hash127.html) runs at impressive 
speeds in software... under 4cpb on a P3, and can be easily integrated 
into such a scheme.  As implemented, hash127 doesn't make it easy to 
build an AEAD scheme that also authenticates non-encrypted data, but a 
slightly different implementation approach for hash127 would allow it 
without that big a speed hit.

The problem with this is that hash127 is not XOR-universal, which 
means, so far as I know, you don't currentlyhave theoretical backing to 
just XOR the hash with with keystream from a stream cipher (even though 
it is probably not a big deal).  If using Bernstein's hash127 
implementation, one would take 128 bits of RC4 keystream and pass it in 
where the nonce goes, which has the desired effect.

John

On Sunday, May 11, 2003, at 02:00  AM, Alex Alten wrote:

>> The above text is the basic announcement of SOBER-128, but I wanted 
>> to add a bit specifically for CFRG.
>>
>> I'm seriously concerned about ongoing use of RC4 for, basically, 
>> anything. It's elegant and simple, but very often is used 
>> incorrectly, if only to the extent that it's often used without 
>> message authentication. The problems with rekeying as in WEP are 
>> devastating, and probably represent the biggest single failure of a 
>> deployed cryptosystem since Enigma. And lastly, the distinguishing 
>> attacks, at around 2^32 bytes, verge on real vulnerability too. We 
>> wanted to provide a credible replacement for RC4 in any of its modes 
>> of use. That's what SOBER-128 is.
>>
>> For IETF use, obviously we need to write an RFC. I've never written 
>> an RFC before (in fact, blush, have never been to an IETF meeting) 
>> and could use some guidance on just how much information should be 
>> put in, and what should happen to it then.
>>
>> regards,
>> Greg.
>>
>>
>> Greg Rose                                       INTERNET: 
>> [email-masked]

---

From: Alex Alten <[email-masked]>
Date: Sun, 11 May 2003 01:44:12 -0700

At 02:46 AM 5/11/2003 -0400, John Viega wrote:
<snipped>
>problem... pass the key material through a PRF first, or discard the first 
>256 outputs.  Both thwart the Fluhrer et al. attack.  The paper on the attack:
>
>If that were the only problem, no one would have major reservations with 
>RC4 beyond the difficulty of using it securely (which is already a problem 
>with most stream ciphers).  However, Fluhrer and McGrew have an attack 
>that distinguishes RC4 from random with high probability after 2^30 
>outputs.  They also had some other fairly damning observations.
>See:
<snipped>

Scott and David should talk with Peter Schweitzer of ISSI.
I suspect with his help they can nail RC4 into its coffin.  I'm
willing to contribute to the funeral and burial expenses.

- Alex

--

Alex Alten
[email-masked]

---

From: Greg Rose <[email-masked]>
Date: Mon, 12 May 2003 08:06:40 +1000

>until you can defend it properly.

Yes. If you read the details, SOBER-t32 has been analysed up the wazoo, and 
was secure at the 128-bit level; just not at the 256-bit level that we 
thought, which ruled it out of NESSIE. Most of this analysis was done on 
the "unstuttered" -t32, and applies directly to SOBER-128.

regards,
Greg.

---

From: David Mcgrew <[email-masked]>
Date: Wed, 14 May 2003 13:24:35 -0700

Greg,

At 10:25 AM 5/11/2003 +1000, Greg Rose wrote:
>environments, from firmware and smart cards to large computers. Source 
>code for SOBER-128 is freely available and use of this source code, or 
>SOBER-t16 and SOBER-t32 were submitted to the NESSIE program ; SOBER-t16 
>as a stream cipher for 128-bit key strength and SOBER-t32 as a stream 
>cipher with 256-bit key strength. SOBER-t16 and SOBER-t32 proved to be 
>among the strongest stream cipher submissions to NESSIE. However, both 
>ciphers were found to fall short of the stringent NESSIE requirements (as 
>were all other stream ciphers).

And these requirements aren't met by AES used in any standard encryption 
mode, right?  I recall that you'd written up a critique of these 
requirements.  Is it available on the web?

>128-bit key strength proposed for SOBER-128 is reduced from the 256-bit 
>key strength proposed for SOBER-t32 to ensure that SOBER-128 provides far 
>in excess of the stated security level.
>
>SOBER-128 is intended to provide security under the condition that no IV 
>is ever reused, that no more than 2^80 words of data are processed with 
>one key, and that no data failing authentication checks will be further 
>encrypted, and which parts are authenticated, for correct operation, as 
>the encryption operation is plaintext-aware when message authentication is 
>being performed.
>
>A 40-page design document and reference implementations of SOBER-128 may 
>be found at QUALCOMM Australia's web site: http://www.qualcomm.com.au . 
>The full paper is also available on the IACR eprint server, and a shorter 

Yes, this is a worthwhile goal.   I look forward to reading about SOBER-128.

David

---

From: Greg Rose <[email-masked]>
Date: Thu, 15 May 2003 13:05:35 +1000

At 01:24 PM 5/14/2003 -0700, David Mcgrew wrote:
>>...
>>SOBER-128 was developed from SOBER, proposed by Rose in 1998.  The 
>>ciphers SOBER-t16 and SOBER-t32 were submitted to the NESSIE program ; 
>>SOBER-t16 as a stream cipher for 128-bit key strength and SOBER-t32 as a 
>>stream cipher with 256-bit key strength. SOBER-t16 and SOBER-t32 proved 
>>to be among the strongest stream cipher submissions to NESSIE. However, 
>>both ciphers were found to fall short of the stringent NESSIE 
>>requirements (as were all other stream ciphers).
>

That's correct. There's a generic distinguishing attack against block 
ciphers, based on the fact that they produce permutations and not random 
output. This distinguishes AES-CTR from random with about 2^68 bytes, 
whether with 256-bit keys or 128-bit keys; hence we argue that key length 
is not terribly relevant to distinguishing attacks, rather that known 
plaintext requirements should determine.

In the meantime, the strongest distinguishing attack against SOBER-t32 
(IIRC) requires something like 2^150 bytes of output. Note that you can 
build an entire codebook for AES in less data and processing than was 
required for a simple distinguishing attack on t32. We did indeed write a 
paper on this subject, and submitted it to NESSIE; there's also a copy on 
the IACR eprint server: http://eprint.iacr.org/2002/142/ .

Greg.