Re: SOBER-128 draft rfc

From: Gregory G Rose (ggr_at_qualcomm.com)
Date: 02/20/04 

Date: 19 Feb 2004 16:34:02 -0800

In article <c0eejg$t2q@qualcomm.com>, Gregory G Rose <ggr@qualcomm.com> wrote:
>fse048
>Title: A MAC forgery attack on SOBER-128
>Authors: Dai Watanabe and Soichi Furuya

>Anyway, I will report back.

Well, this is one of those very hard things to
write...

The attack certainly works, although the authors
didn't make it very clear that it only works when
MACing unencrypted material.

For those who haven't seen it, here's my
one-paragraph synopsys: you flip the 0x100 bit of
one input word, the same bit of the word two
words later, the 0x001 bit of the word 13 words
later, and the 0x100 bit again of the word 17
words later. (These correspond to the LFSR
feedback stages.) Then, with p=1/32, the MAC
doesn't change.

I'm very embarrassed, because it falls into the
category of things I/we should have though of.
Which is not to detract from Watanabe and Furuya 's
work, which is neat. If it was obvious, I like
to think we would have seen it. In a way, we did
see it, because we extensively analysed the MAC
function in combination with encryption. The
reason that plaintext was input to the MAC
feedback function was to ensure that differences
in plaintexts would appropriately change the
keystream output, thus leveraging the stronger
nonlinearity of the keystream NLF. (That was a
handwaving description of something I think we
express more clearly in the design document.) I
failed to take into account that this left us
potentially vulnerable in the plaintext-only
scenario; after all, we were designing a cipher,
right?

Is this problem fixable? Without sacrificing too
much performance? As it happens, yes... there's a
simple fix to this problem that we'd already
considered in the design phase (that the authors
above missed). Feed back ciphertext, not
plaintext, when not encrypting. We originally
didn't do this purely for the efficiency of not
generating the unneeded keystream, not realizing
that we'd opened up the same problem we'd already
avoided once.

To clarify: The input to the MAC feedback function
now uses ciphertext bits when transmitting
plaintext, and plaintext bits when transmitting
ciphertext. These can be mingled at the level of
individual bits, although our reference code only
supports a byte-at-a-time interface.

This mirrors our PEMI (Partial Encryption with
Message Integrity) enhancement of Jutla's IAPM
parallel encryption-and-MAC mode, which has been
proven secure. The good outcome of this is that we
might even be able to develop a proof of security
for the MAC functionality based on the assumption
of security for the stream cipher; but that's in
the future. In the meantime, at least the fix is
"pre-analyzed", because we are confident that
duality applies and the MAC function now has the
same security in both directions, and we believe
that to be quite strong, although time will tell.

While adapting the RFC we also noticed another
"D'oh" moment. We hadn't fully specified how the
MAC behaved when not using entire words, and
allowed extension of partial words with zero bits
to have the same MAC. We fixed this along the way.

New versions of the reference (C and Java) source
code, an updated design document, and updated RFC
will be available on our website
www.qualcomm.com.au approximately
contemporaneously with this message. Note that the
only behaviour that has changed has to do with
MACing unencrypted plaintext. The keystream
generator hasn't changed, and the result of MACing
entirely encrypted plaintext hasn't changed. So
we're not making a big change to the name of the
cipher, just adding a version number for clarity
to the various code and document names.

Please bear in mind that our goal here is to
produce a practical and usable cipher that has had
lots of cryptanalysis applied to it. So we've done
a lot of the development, historically, in public
(and taken the necessary hits) and have been
trying evolutionary, not revolutionary, changes.
We consider this to be another step along that
path, albeit an embarrassing one.

Greg. 

-- 
Greg Rose
232B EC8F 44C6 C853 D68F  E107 E6BF CD2F 1081 A37C
Qualcomm Australia: http://www.qualcomm.com.au

Relevant Pages

  • Re: Order of Encryption and Authentication
    ... >>encryption should be done before authentication. ... >>ciphertext and forge a mac. ... >>and the mac of the plaintext, the attacker would have to recover both ... Known plaintext and encryption by XORing the plaintext with the ...
    (sci.crypt)
  • Re: ASCII_Modulated _Trapdoor Cipher – New Cryptography.
    ... plaintext transformed into cipher text in secure communications. ... encryption data in use each has demonstrable randomness but the cipher ... the decryption algorithm should be Cipher text – ...
    (sci.crypt)
  • Re: Combining stream and block encryption techniques
    ... in stream encryption each plaintext bit is ... or a common block cipher in counter mode) and there is thus a 'state'. ...
    (sci.crypt)
  • Re: Order of Encryption and Authentication
    ... Known plaintext and encryption by XORing the plaintext with the ... > If the attacker obtains key2, they can alter the ciphertext and generate ... > a new mac for it; the receiver would validate the mac and ... The whole point of using a MAC is that the encryption does not provide ...
    (sci.crypt)
  • Authenticating encrypted messages?
    ... I'm working on implementing a symmetric encryption program that needs ... to ensure that cipher text has not been tampered with while in transit ... what if we need to encrypt both the message and MAC before ... Encrypt I in the CBC mode with the block cipher to produce C ...
    (sci.crypt)