Cryptography-Digest Digest #667, Volume #12 Wed, 13 Sep 00 03:13:00 EDT
Contents:
Re: Problem with Tiger hash algorithm and binary files (David Hopwood)
Re: Scottu19 Broken (Johnny Bravo)
Re: Getting Started, advice needed (FAQs , yes I read them) ("Paul Pires")
Re: nice simple function ("Douglas A. Gwyn")
Re: Getting Started, advice needed (FAQs , yes I read them) (Andy C)
Disappearing Email redux (Daniel R. Kegel)
----------------------------------------------------------------------------
Date: Wed, 13 Sep 2000 04:23:55 +0100
From: David Hopwood <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Subject: Re: Problem with Tiger hash algorithm and binary files
=====BEGIN PGP SIGNED MESSAGE=====
Daniel Leonard wrote:
> On Tue, 12 Sep 2000, John Myre wrote:
>
> > Daniel Leonard wrote:
> > <snip>
> > > While on the subject, which reference implementation is the right one:
> > > the one from Eli Biham site, or the one from Ross Anderson site ?
> >
> > How are they different? Do they give different answers?
>
> Last time I checked (around April-May), the difference in the
> implemetation was in the padding.
>
> Anderson's: 0x80, 0x00, ...
>
> Biham's : 0x01, 0x00, ...
>
> It gives different results.
The paper says, "For drop-in compatibility, we adopt the outer structure of
the MD4 family."
Except for differences in the byte order used to encode the number of bits,
MD4, MD5, SHA-1, and RIPEMD-128/160 all use the same padding, starting with
a byte of 0x80 (not 0x01).
OTOH, Eli Biham's page says:
# Note that in the original reference implementation that we have published
# in this page there was a typo that used the wrong bit order when it
# padded the '1' bit at the end of the message. It used the constant 0x80,
# rather than 0x01 to append this bit. The reference implementation and
# test results given above are already corrected. We are grateful to John
# Lull who found this typo.
IOW, the spec originally specified the same padding as the MD4 family, i.e.
0x80, and was implemented that way. Then someone called John Lull erroneously
pointed out that the padding should use 0x01, and this was accepted by Eli
Biham and/or Ross Anderson. The version at Eli Biham's page (which is the
official Tiger home page) was changed, but the one in Ross Anderson's FTP
directory at <http://www.ftp.cl.cam.ac.uk/ftp/users/rja14/tiger.tar.gz> was
overlooked (that file has not been changed since February 1996).
Another reference implementation has since been written in Java, and
distributed with the Cryptix JCE snapshot
<http://www.cryptix.org/products/jce/>; that version uses 0x01.
[You might be able to see the funny side of the following code from
PaddingMD.java, which also handles MD5, SHA-1 et al:
this.buf[this.bufOff++] = (mode==MODE_TIGER) ? (byte)0x01 : (byte)0x80;
]
I think that at this point the version to be used is 0x01, but all-in-all
this is a textbook example of how not to handle apparent errors in a
reference implementation.
- --
David Hopwood <[EMAIL PROTECTED]>
Home page & PGP public key: http://www.users.zetnet.co.uk/hopwood/
RSA 2048-bit; fingerprint 71 8E A6 23 0E D3 4C E5 0F 69 8C D4 FA 66 15 01
Nothing in this message is intended to be legally binding. If I revoke a
public key but refuse to specify why, it is because the private key has been
seized under the Regulation of Investigatory Powers Act; see www.fipr.org/rip
=====BEGIN PGP SIGNATURE=====
Version: 2.6.3i
Charset: noconv
iQEVAwUBOb7zDzkCAxeYt5gVAQFUNQf9H8s0lzgk4YL8eQtuc2VHVWNk9JipxcQj
hVQuZAptHUIvUChiSBSDhZJzdE0tojY/zyRCBzw+E9uf/12a+Aixy538sifvEut8
PBBGhsYTcgIC+khUlwus1bxur8EYurlMh+QKZYivOqqPBhB8JggvEiJVoB6ofjIa
P2NdDAhORSSIPbq33CjqNYdzq74zMxBVgzvljct5Nn9iMq5tM/qHWQJ2QfN4nRZh
H8WqGYHbEG3j7OYDDdDJaPxEucmMZXtXQbVgaAd7TgN7/2KR2TxKVN7YiUMv17+U
h+/EJRBm41lCDRQA6isT13Hlf1ffCvPUwLyNVgyYkhtXfEijtbxgrw==
=i6eQ
=====END PGP SIGNATURE=====
------------------------------
From: Johnny Bravo <[EMAIL PROTECTED]>
Subject: Re: Scottu19 Broken
Date: Wed, 13 Sep 2000 01:07:09 -0400
On Tue, 12 Sep 2000 19:33:22 GMT, "Douglas A. Gwyn"
<[EMAIL PROTECTED]> wrote:
>Mok-Kong Shen wrote:
>> Perfectly. This the raison d'etre of high-level programming
>> languages and comment statements in these, not to mention
>> object-oriented design methodologies and other software
>> engineering tools.
>
>Object-oriented design has nothing to do with fixing the
>problems in the example source code. More to the point
>would be Kernighan & Plauger's "The Elements of Programming
>Style".
And now the punchline for those who haven't actually compiled and
ran the code I listed, here is the clearer version most of us would
rather try to figure out than the tangled mess that resembles the code
distributed by the aforementioned loony.
#include <stdio.h>
main()
{
printf("Hello World!\n");
}
--
Best Wishes,
Johnny Bravo
BAAWA Knight, EAC - Temporal Adjustments Division
"The most merciful thing in the world, I think, is the inability
of the human mind to correlate all its contents." - HP Lovecraft
------------------------------
From: "Paul Pires" <[EMAIL PROTECTED]>
Subject: Re: Getting Started, advice needed (FAQs , yes I read them)
Date: Tue, 12 Sep 2000 22:09:58 -0700
Scott Fluhrer <[EMAIL PROTECTED]> wrote in message
news:8pmv3g$p14$[EMAIL PROTECTED]...
>
> Paul Pires <[EMAIL PROTECTED]> wrote in message
> news:n3zv5.82540$[EMAIL PROTECTED]...
> >
> > Scott Fluhrer <[EMAIL PROTECTED]> wrote in message
> > news:8pjugo$l7q$[EMAIL PROTECTED]...
> > >
> > > Paul Pires <[EMAIL PROTECTED]> wrote in message
> > > news:cI%u5.61866$[EMAIL PROTECTED]...
> > > >
> > > > Scott Fluhrer <[EMAIL PROTECTED]> wrote in message
> > > > news:8phpk5$plr$[EMAIL PROTECTED]...
> > > > >
> > > > > Paul Pires <[EMAIL PROTECTED]> wrote in message
> > > > > news:U_Yu5.60123$[EMAIL PROTECTED]...
> > > > > > Why would anyone brute force the key. It seems to me that if
> > > > > > you can be made to encrypt some known material at the
> > > > > > beginning of a file, I get your key using only a pencil and
> > > > > > paper.
> > > > > >
> > > > > > first tempKey = theKey;
> > > > > >
> > > > > > > temp1 = data[counter] + tempKey;
> > > > > > > temp1 = ((temp1 << 19) | (temp1 >>13)) - 26087;
> > > > > > > temp1 = ((temp1 << 23) | (temp1 >> 9));
> > > > > > > tempData[counter] = temp1;
> > > > > > > tempKey = tempKey + temp1 - 26087;
> > > > > >
> > > > > > Let's refrase the first cycle:
> > > > > >
> > > > > > temp1 = plaintext + the honest to god key;
> > > > > > temp2 = ((temp1 << 19) | (temp1 >>13)) - 26087;
> > > > > > temp3 = ((temp1 << 23) | (temp1 >> 9));
> > > > > Actually, this should be:
> > > > > temp3 = ((temp2 << 23) | (temp2 >> 9));
> > > > >
> > > > > > ciphertext= temp3;
> > > > > > tempKey = tempKey + temp1 - 26087;
> > > > > Actually, this should be:
> > > > > tempKey = tempKey + temp3 - 26087;
> > > > > Neither of these affect your attack materially...
> > > >
> > > > Sorry for the typo's. I finally found an easy one to respond to
> > > > and was rushing like mad to post it before the real guns saw it :-)
> > >
> > > No problem -- I know the feeling. "I gotta get this break out before
> Wagner
> > > sees the post, and stomps the system flat..."
> > >
> > > > > Actually, this attack can be strengthened somewhat, in that it can
> be
> > > > > applied to any block (and, it relies on a known plaintext block,
> rather
> > > than
> > > > > a chosen one as you appeared to have implied). Suppose you
> know/guess
> > > the
> > > > > value of plaintext block 10. Then, you use the above attack to
> derive
> > > the
> > > > > value of tempKey at the start of the encryption of block 10. Then,
> > > looking
> > > > > at the last two steps of the iteration for block 9:
> > > > >
> > > [snip]
> > > >
> > > > Yep, that works too.
> > >
> > > Actually, thinking about the system some more (yes, I don't have a
> life...
> > > why do you ask?), the system is essentially:
> > >
> > > C = F( P+K )
> > > K += C + Const
> > >
> > > where:
> > > P is the plaintext block
> > > C is the ciphertext block
> > > K is hidden state, initialized to be the key
> > > Const is -26087
> > > F is an unkeyed invertible 32 bit->32 bit function
> > > Finv is the inverse of F
> > > All addition/subtraction is done mod 2**32
> > >
> > > then,
> > >
> > > Finv(C) - P = K
> > >
> > > Then, if we have two adjacent ciphertext blocks C1, C2, then
> > >
> > > Finv(C1) - P1 = K1
> > > Finv(C2) - P2 = K2
> > > K2 = K1 + C1 + Const
> >
> > Be gentle, If I go FUBAR here, please forgive.
> >
> > Doesn't this also mean that K2-K1 = C1 + Const ?
> Well, yes
>
> >
> > Wouldn't this mean that the diference between adjacent round
> > keys is defined entirely by the first ciphertext? So if C1 is
> > (2^32) - Const , Then C1 + Const = 0, and K2 = K1 ?
> >
> > Wierd property. I wonder if you could craft a chosen ciphertext
> > hack on it? Some way of fooling the guy into handling two
> > adjacent blocks with the same working key.
> >
> > What does that get me? I think I just lost myself.
> Actually, you're not really interested in the keys, you're interested in the
> plaintext -- you care about the keys only because it'd give you the
> plaintext. And, once you do have the plaintext, you have already shown how
> to go back and get the keys if you care to.
>
> And, we have:
>
> > > P2 - P1 = Finv(C2) - Finv(C1) - C1 - Const
> > >
> > > Everything on the right side is known to the attacker, and so he can
> deduce
> > > the arithmetic differences between any two blocks. Depending on the
> > > characteristics of the plaintext (eg. if there is a checksum of all the
> > > blocks at the end of the plaintext), this may make recovering it real
> > > easy...
>
> or, in other words, for a given set of ciphertext blocks C[], there exists a
> key-independent transformation that gives a set of blocks C'[] such that:
>
> P[i] = C'[i] + K mod 2**32
>
> for some unknown K (which is not the attackers key), which is identical for
> all the blocks (and P[] are the plaintext blocks).
>
> How can this help? Well, we can make this transformation, and pretend that
> the above "add" cipher [1] was being used. And, this cipher has obvious
> weaknesses. For example:
>
> - If you have the lower 16 bits of one block, and the upper 16 bits of
> another, you can rederive K, which gives you all the plaintext. For that
> matter, as long as for each bit N, 0<=N<32, you know that value of that bit
> for *some* plaintext block, you can rederive K.
>
> - If the packet has a checksum (either additive or xor based), then this
> formula allows you to figure out K efficiently.
>
>
> [1] I dup it the "add" cipher because it is analogous to the "xor" cipher
> beloved by klewless newbie cryptographers everywhere...
Ouch. Thanks for the time and walking me through it
Paul
>
> --
> poncho
>
>
>
>
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: nice simple function
Date: Wed, 13 Sep 2000 01:31:28 -0400
Simon Johnson wrote:
> Right, what is linearness? - Clearly its a measure of the vunrability
> to attack by linear cryptanaylsis. So the next question is what is
> linear cryptanylsis? I don't think this question has ever been answered
> properly while i've been posting/reading. :)
Actually, linearity is a standard mathematical property:
A function f is said to be linear iff for all a,x,y (for
which the expressions are well defined): f(a*x) = a*f(x)
and f(x+y) = f(x)+f(y). (In algebras with just one
operator, only the second condition applies.)
Matsui's so-called "linear cryptanalysis" in essence
replaces the detailed encryption with a simplified model
composed of pieces each of which is a linear function
(from original input and output to key bit) that is
maximally biased with respect to the probability of the
corresponding key bit. (The algebraic operations
involved are those of GF(2).) Detailed write-ups exist,
e.g. in Bruce's book.
The importance of linear approximations for analyzing
cryptosystems was appreciated long before Matsui's paper,
but that seems to have been the first public appearance
of the idea and the impetus for public research on bent
functions.
------------------------------
Subject: Re: Getting Started, advice needed (FAQs , yes I read them)
From: [EMAIL PROTECTED] (Andy C)
Date: Wed, 13 Sep 2000 05:52:35 GMT
On 12 Sep 2000, [EMAIL PROTECTED] (Scott Fluhrer) spake in
<8pmv3g$p14$[EMAIL PROTECTED]>:
>
>Paul Pires <[EMAIL PROTECTED]> wrote in message
>news:n3zv5.82540$[EMAIL PROTECTED]...
>>
>> Scott Fluhrer <[EMAIL PROTECTED]> wrote in message
>> news:8pjugo$l7q$[EMAIL PROTECTED]...
>> >
>> > Paul Pires <[EMAIL PROTECTED]> wrote in message
>> > news:cI%u5.61866$[EMAIL PROTECTED]...
>> > >
>> > > Scott Fluhrer <[EMAIL PROTECTED]> wrote in message
>> > > news:8phpk5$plr$[EMAIL PROTECTED]...
>> > > >
>> > > > Paul Pires <[EMAIL PROTECTED]> wrote in message
>> > > > news:U_Yu5.60123$[EMAIL PROTECTED]...
>> > > > > Why would anyone brute force the key. It seems to me that if
>> > > > > you can be made to encrypt some known material at the
>> > > > > beginning of a file, I get your key using only a pencil and
>> > > > > paper.
>> > > > >
>> > > > > first tempKey = theKey;
>> > > > >
>> > > > > > temp1 = data[counter] + tempKey;
>> > > > > > temp1 = ((temp1 << 19) | (temp1 >>13)) - 26087;
>> > > > > > temp1 = ((temp1 << 23) | (temp1 >> 9));
>> > > > > > tempData[counter] = temp1;
>> > > > > > tempKey = tempKey + temp1 - 26087;
>> > > > >
>> > > > > Let's refrase the first cycle:
>> > > > >
>> > > > > temp1 = plaintext + the honest to god key;
>> > > > > temp2 = ((temp1 << 19) | (temp1 >>13)) - 26087;
>> > > > > temp3 = ((temp1 << 23) | (temp1 >> 9));
>> > > > Actually, this should be:
>> > > > temp3 = ((temp2 << 23) | (temp2 >> 9));
>> > > >
>> > > > > ciphertext= temp3;
>> > > > > tempKey = tempKey + temp1 - 26087;
>> > > > Actually, this should be:
>> > > > tempKey = tempKey + temp3 - 26087;
>> > > > Neither of these affect your attack materially...
>> > >
>> > > Sorry for the typo's. I finally found an easy one to respond to
>> > > and was rushing like mad to post it before the real guns saw it :-)
>> >
>> > No problem -- I know the feeling. "I gotta get this break out before
>Wagner
>> > sees the post, and stomps the system flat..."
>> >
>> > > > Actually, this attack can be strengthened somewhat, in that it can
>be
>> > > > applied to any block (and, it relies on a known plaintext block,
>rather
>> > than
>> > > > a chosen one as you appeared to have implied). Suppose you
>know/guess
>> > the
>> > > > value of plaintext block 10. Then, you use the above attack to
>derive
>> > the
>> > > > value of tempKey at the start of the encryption of block 10. Then,
>> > looking
>> > > > at the last two steps of the iteration for block 9:
>> > > >
>> > [snip]
>> > >
>> > > Yep, that works too.
>> >
>> > Actually, thinking about the system some more (yes, I don't have a
>life...
>> > why do you ask?), the system is essentially:
>> >
>> > C = F( P+K )
>> > K += C + Const
>> >
>> > where:
>> > P is the plaintext block
>> > C is the ciphertext block
>> > K is hidden state, initialized to be the key
>> > Const is -26087
>> > F is an unkeyed invertible 32 bit->32 bit function
>> > Finv is the inverse of F
>> > All addition/subtraction is done mod 2**32
>> >
>> > then,
>> >
>> > Finv(C) - P = K
>> >
>> > Then, if we have two adjacent ciphertext blocks C1, C2, then
>> >
>> > Finv(C1) - P1 = K1
>> > Finv(C2) - P2 = K2
>> > K2 = K1 + C1 + Const
>>
>> Be gentle, If I go FUBAR here, please forgive.
>>
>> Doesn't this also mean that K2-K1 = C1 + Const ?
>Well, yes
>
>>
>> Wouldn't this mean that the diference between adjacent round
>> keys is defined entirely by the first ciphertext? So if C1 is
>> (2^32) - Const , Then C1 + Const = 0, and K2 = K1 ?
>>
>> Wierd property. I wonder if you could craft a chosen ciphertext
>> hack on it? Some way of fooling the guy into handling two
>> adjacent blocks with the same working key.
>>
>> What does that get me? I think I just lost myself.
>Actually, you're not really interested in the keys, you're interested in the
>plaintext -- you care about the keys only because it'd give you the
>plaintext. And, once you do have the plaintext, you have already shown how
>to go back and get the keys if you care to.
>
>And, we have:
>
>> > P2 - P1 = Finv(C2) - Finv(C1) - C1 - Const
>> >
>> > Everything on the right side is known to the attacker, and so he can
>deduce
>> > the arithmetic differences between any two blocks. Depending on the
>> > characteristics of the plaintext (eg. if there is a checksum of all the
>> > blocks at the end of the plaintext), this may make recovering it real
>> > easy...
>
>or, in other words, for a given set of ciphertext blocks C[], there exists a
>key-independent transformation that gives a set of blocks C'[] such that:
>
> P[i] = C'[i] + K mod 2**32
>
>for some unknown K (which is not the attackers key), which is identical for
>all the blocks (and P[] are the plaintext blocks).
>
>How can this help? Well, we can make this transformation, and pretend that
>the above "add" cipher [1] was being used. And, this cipher has obvious
>weaknesses. For example:
>
>- If you have the lower 16 bits of one block, and the upper 16 bits of
>another, you can rederive K, which gives you all the plaintext. For that
>matter, as long as for each bit N, 0<=N<32, you know that value of that bit
>for *some* plaintext block, you can rederive K.
>
>- If the packet has a checksum (either additive or xor based), then this
>formula allows you to figure out K efficiently.
>
>
>[1] I dup it the "add" cipher because it is analogous to the "xor" cipher
>beloved by klewless newbie cryptographers everywhere...
WOW - thanks for the walkthough. This taught me more than anything (well
amost) that I read in Schneier's book - I guess I learn better "hands on" -
that old saw about "no replacement for experience" certianly rings true on
this (at least for me).
------------------------------
From: [EMAIL PROTECTED] (Daniel R. Kegel)
Crossposted-To: alt.privacy,uk.legal
Subject: Disappearing Email redux
Date: 13 Sep 2000 06:27:04 GMT
pratik khasnabis <[EMAIL PROTECTED]> asked:
> As a communication engineer, I know a little about cryptography and am
> interested in practical applications. Today I read the story about
> disappearing emails. I have included the hyperlinks at the end. I want
> to know how is it possible by this technique to automatically send the
> encrypted message to the Disappearing access server and get it
> decrypted. How to prevent the message on screen to be copied and
> pasted. I am not able to understand this technique. Can you help.
> ... http://www.disappearing.com/
The basic idea is, it's a product for use between two cooperating
people who both want old emails to be deleted, and who agree
among themselves not to print out old emails, copy and paste
the text of encrypted emails, or otherwise try to defeat the system.
It currently requires Windows and Microsoft Outlook 98 or Outlook 2000,
and you have to be willing to install their (free) plugin.
When you install it, a second "Send" button appears on the Outlook
toolbar. Clicking on the new "Send" button causes the mail to be encrypted
before transmission. The key is stored on a server either at Disappearing, Inc.
or at your own company (if your company decides it uses Disappearing Email
so much it wants its own server), and the plugin requests the key from
the server whenever it needs to display an encrypted message. The plugin
never stores the message in plainext form.
On the recipient's side, if the recipient has the plugin installed,
it requests the key from the server and decrypts it locally; it doesn't
send the message to the server for decryption.
If the recipient doesn't have the plugin installed, plain old HTML image
links (not a scripting language!) are used to send the message up to
a secure web server for decryption and display in the email
reader's window (assuming it supports HTML messages).
When it's time for the message to expire, the server deletes it.
Since the plugin doesn't keep copies of the key for very long,
and never keeps plaintext copies of messages,
deleting the key from the server pretty much makes all outstanding
copies of the message unreadable.
A crossplatform SDK is coming, so programmers who want to incorporate
this kind of old document deletion into their own applications will be
able to do so fairly easily.
The system has been discussed on sci.crypt, alt.privacy, and uk.legal.
Here are some links to the old discussions, some of which are
quite interesting.
August 2000
"Dissapearing email", sci.crypt http://www.deja.com/getdoc.xp?AN=661457197
"encryption - check this out", uk.legal http://x61.deja.com/getdoc.xp?AN=514659910
"Make Your E-Mail Disappear", alt.privacy http://x74.deja.com/getdoc.xp?AN=661177919
March 2000
"are self-shredding files possible?", sci.crypt
http://www.deja.com/threadmsg_ct.xp?AN=594410255.1
November 1999
"Disappearing Inc.", sci.crypt http://www.deja.com/getdoc.xp?AN=53603873
It's also mentioned today on Forbes.com
(http://www.forbes.com/tool/html/00/sep/0912/feat.htm)
- Dan Kegel
(one of the guys who wrote the Disappearing, Inc. keyserver)
------------------------------
** FOR YOUR REFERENCE **
The service address, to which questions about the list itself and requests
to be added to or deleted from it should be directed, is:
Internet: [EMAIL PROTECTED]
You can send mail to the entire list (and sci.crypt) via:
Internet: [EMAIL PROTECTED]
End of Cryptography-Digest Digest
******************************
