Subject: [Cfrg] SOBER-128 draft rfc

From: Greg Rose <[email-masked]>
Date: Mon, 09 Feb 2004 16:43:49 +1100

http://www.ietf.org/internet-drafts/draft-paddon-sober128-01.txt

is a draft RFC for the newest member of our SOBER family of stream ciphers:

    SOBER-128 is a fast software-oriented stream cipher based on simple
    32 bit operations. Keys and optional nonces of arbitrary length are
    supported. Enumeration of keys is thought to be the most efficient
    attack for key lengths of 128 bits or less. SOBER-128 may be
    configured to calculate an arbitrary length Message Authentication
    Code (MAC) as part of the encryption or decryption process. Source
    code for SOBER-128 is freely available, and use of this source code,
    or independent implementations, is permitted for any purpose under a
    fee free license.

The design documents and implementations in C and Java are at our website, 
http://www.qualcomm.com.au . But I'll try to hit the high points:

. SOBER-128 is a very small evolution of SOBER-t32, basically tweaks to add 
efficiency and address the known cryptanalysis results of -t32. No attack 
better than 2^128 is known for -t32. The family of ciphers has been 
extensively analysed over a period of 6 years. I can say, with a straight 
face, that we believe SOBER-128 to be significantly stronger than its 
design target.

. SOBER-128 was designed to "drop in" to IPsec. (Expect an RFC for that 
soon.) In that mode, various benchmarks show that it significantly 
outperforms the AES/HMAC-SHA-1 combo by a factor of 3-8 depending on 
platforms, packet sizes, and so on.

Comments are, of course, welcome.

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: Greg Rose <[email-masked]>
Date: Tue, 10 Feb 2004 11:41:59 +1100

At 06:36 PM 2/9/2004 -0500, John Viega wrote:
>Greg,
>
>In FSE there was a MAC forgery attack that succeeded with very high
>probability.  Should something with such an attack really be an RFC,
>or was the attack actually incorrect?  I did see the talk and it
>seemed to make sense.

Clearly there is a timing problem; I was unable to attend FSE, and was 
unaware of this attack. (When we have attacks on other people's ciphers, we 
tell them... I wish others would show us the same courtesy.)

(I assume you mean:
fse048
Title: A MAC forgery attack on SOBER-128
Authors: Dai Watanabe and Soichi Furuya
which I only just found based on your comment. The other paper we were 
aware of and disagree with the complexity of the attack (and informed the 
authors), but we haven't seen the published version; that one didn't worry us.)

I have no answer at the moment. I'll go find out more and get back to the list.

>Also, I was wondering, what are the applications for new stream
>ciphers?  What I mean by this is that the speed difference between an
>authenticated encryption with AES and with something like SOBER-128
>is, in software, only about 2.5, which doesn't make a significant
>difference for any application I've ever seen.

I believe that efficiency always matters. Assuming that it doesn't, leads 
to things like bloated Windows.

There are two particular cases where efficiency matters, and these are at 
opposite ends of the spectrum. Encryption from the high end, where the bits 
are being pushed out at high gigabit rates, and hardware acceleration costs 
real money; doing more with less translates to real dollars. And at the low 
end, where a small microprocessor running at a low clock rate doesn't have 
the cycles to do everything it wants to.

I don't disagree with any of the other advantages you cite for block cipher 
based mechanisms, but I don't think we should stop research either.

regards,
Greg.

>   And, there are other
>advantages:
>
>- Provable security based on a much better studied cryptographic
>primitive.  As a field, we know quite a lot more about making good
>block ciphers, but clearly are not nearly as good with stream ciphers,
>as shown by the fact that NESSIE accepted no stream ciphers (Though, I
>will agree that the best attacks against some of the primitives were
>not very worrisome, but they are, individually, also far less studied
>than, say, AES).
>
>- The ability to use cheap off-the-shelf AES components in hardware.
>
>- Parallelizable modes that exist now can enable high-speed hardware,
>and still be interoperable with low-speed operations.
>
>The speed of block-based symmetric primitives is clearly becoming far
>less of an issue even in embedded systems.  For example, 3GPP's
>authenticated encryption mode is based on a block cipher.  My very
>first palm pilot had no problems with symmetric crypto (e.g., the SSH
>protocol), nearly six years ago.
>
>I certainly think that designing a good, dedicated stream cipher is an
>interesting and worthy challenge, and the SOBER family has done much
>to advance these primitives.  I'm just trying to figure out the
>practical use cases so that I know when to recommend considering them.
>
>John
>
>On Mon, Feb 09, 2004 at 04:43:49PM +1100, Greg Rose wrote:

---

From: John Viega <[email-masked]>
Date: Mon, 9 Feb 2004 18:36:38 -0500

Greg,

difference for any application I've ever seen.  And, there are other
advantages:

John

---

From: John Viega <[email-masked]>
Date: Tue, 10 Feb 2004 02:39:38 -0500

On Feb 9, 2004, at 7:41 PM, Greg Rose wrote:

> unaware of this attack. (When we have attacks on other people's 
> ciphers, we tell them... I wish others would show us the same 
> courtesy.)

Indeed, it's surprising they did not tell you!

> aware of and disagree with the complexity of the attack (and informed 
> the authors), but we haven't seen the published version; that one 
> didn't worry us.)

Yes, that's the paper.  The other paper you're talking about was also 
published at FSE, correct?  That talk didn't leave me believing they 
had a significant attack, either.  In fact, I think that the authors 
revised their complexity bounds upward at the conference, probably due 
to your feedback.
> I believe that efficiency always matters. Assuming that it doesn't, 
> leads to things like bloated Windows.
>
> There are two particular cases where efficiency matters, and these are 
> at opposite ends of the spectrum. Encryption from the high end, where 
> the bits are being pushed out at high gigabit rates, and hardware 
> acceleration costs real money; doing more with less translates to real 
> dollars. And at the low end, where a small microprocessor running at a 
> low clock rate doesn't have the cycles to do everything it wants to.

Thanks for the perspective.  I certainly agree that efficiency matters 
quite a bit.  There's a good reason why RC4 was so popular back when 
3DES was the block cipher of choice, and it has even remained somewhat 
popular in the face of some fairly serious attacks.   The gap is 
starting to get quite small, though!

>
> I don't disagree with any of the other advantages you cite for block 
> cipher based mechanisms, but I don't think we should stop research 
> either.

Nor do I, especially because I think that block cipher design and 
stream cipher design can share ideas quite well, particularly in large 
s-box design.  One of the most impressive talks at FSE was Shamir's 
talk on t-functions, which have definite applications in this area.

Thanks,

John

> Gladesville NSW 2111    232B EC8F 44C6 C853 D68F  E107 E6BF CD2F 1081 
----
John Viega
CTO, Secure Software, Inc.
703-814-4402

Secure Programming Cookbook: http://secureprogramming.com
Building Secure Software: http://buildingsecuresoftware.com