|
|
MAC forgery attack on the original SOBER-128
Watanabe & Furuya (FSE 2003)
showed an attack on the MAC functionality of SOBER-128 when accumulating
plaintext.
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.
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, (taking the necessary
hits) and have been making evolutionary, not revolutionary, changes. We
consider this to be another step along that path, albeit an embarrassing
one.
|
|
