Cryptography-Digest Digest #167, Volume #12 Thu, 6 Jul 00 03:13:01 EDT
Contents:
Re: Diffie Hellman Primes : Speed Tradeoff Q (Mark Wooding)
Re: Encryption and IBM's 12 teraflop MPC...... ("Douglas A. Gwyn")
Re: Help programming ("Joseph Ashwood")
Re: AONT (David Hopwood)
Re: multiplication and inversion in finite fields (David Hopwood)
Re: Hash and Entropy (JPeschel)
CRC question (Benjamin Goldberg)
Re: AONT (Benjamin Goldberg)
Re: A simple all-or-nothing transform (David Hopwood)
Re: CRC question ("Scott Fluhrer")
Re: Hash and Entropy (zapzing)
Re: Some dumb questions (John Savard)
Re: Even an Amplified Boomerang Won't Cascade (John Savard)
Information-theoretic hash question (was Re: CRC question) (Benjamin Goldberg)
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (Mark Wooding)
Subject: Re: Diffie Hellman Primes : Speed Tradeoff Q
Date: 5 Jul 2000 21:51:41 GMT
Anton Stiglic <[EMAIL PROTECTED]> wrote:
> As far as I know, there is no problem, as long as you work in the
> subgroup of a large prime. You want to be careful against Discreet
> Log attacks on the larger group (mod p), but with at least one prime
> factor of p-1 being large enough, I think your o.k. I'd work with
> Lim-Lee primes just to be on the safe side however...
Right, thanks. I'm aware that if p = q R + 1 where R is smooth then
discrete logs aren't so difficult.
I may write Lim-Lee prime generation stuff at some point.
-- [mdw]
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: Encryption and IBM's 12 teraflop MPC......
Date: Wed, 5 Jul 2000 21:51:14 GMT
Dan Day wrote:
> So no, a computer that's 12,000 times faster than the
> fastest new PC on the market doesn't make a really big dent.
> Unless, of course, you know a good breakthrough shortcut
> algorithm... But a shortcut, if any exists, is just
> as likely to be feasible on a 166MhZ Pentium as it is
> to require the kind of horsepower a 12 teraflop computer
> gives you.
There is a big difference between knowing what the message
says sometime next year and knowing today.
------------------------------
From: "Joseph Ashwood" <[EMAIL PROTECTED]>
Subject: Re: Help programming
Date: Wed, 5 Jul 2000 15:25:04 -0700
If the dependence is such that
x = f(a,b,c)
y = g(a,b,c)
z = h(a,b,c)
Then I can tell you immediately that by laws of algebra a solution exists
(you have 3 functions of 3 variables, the only issue arrives when you have
more variable than equations, or unknown variable, most modern ciphers rely
on this in some way). If however you have x = f(a,b,c), it is a simple
matter to hold two values the same and solve for the third, reducing the
space to (my overly optimistic estimate) 2^40. Overcoming this problem take
extreme effort, and likely the encoding of the pictures will severely reduce
the space. I think for a best case the security should be placed at 3*2^40,
overcoming that barrier will be extremely difficult, and then you are forced
to deal with predictability in the pictures themselves. Forther down the
road you have to become concerned about the disposal of your pictures,
because if they are not completely disposed of immediately, or were ever
transferred to you in an even slightly insecure way, the security is
compromised, I for one have probably downloaded certainly no more than
10,000 pictures in the last year, even if the 3x barrier is overcome
completely that still leave only 1,000,000,000,000 possible combinations, or
roughly 2^40, or a weekends work for a throw away computer. Unless someone
can prove independence and unpredictability of bytes in a picture file (that
was after all the original question so let's keep it there), I will stand my
ground that it's weak. If however someone can prove the independence,
unpredictability, and non-bias of a picture file, I will gladly accept that
we have once again discovered OTP.
Joe
"Jeffrey Williams" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> I must be missing something here. As I understand it, each plaintext byte
is
> somehow manipulated based on three key bytes. Each of those key bytes
comes
> from a different picture file (presumably it could be some other type of
file).
> I understand that there are a finite number of digitized pictures
available and
> that that finite number is further limited to the number of such pictures
that
> the user can access. So you're estimating the keyspace to be 2^40. Now,
if
> your estimate is the number of pictures available, then shouldn't the
keyspace
> be 2^120? After all, you use three pictures and you must have all three.
>
> Therefore, it seems to me, that if you have a limited number of pictures
> available, you could simply use more pictures.
>
> I don't see keyspace as the real issue here. I think the real issue is
whether
> the cipher is subject to a non-brute-force attack.
>
> Jeff
>
> Joseph Ashwood wrote:
>
> > > > Why 64bits? That a lot of pictures. The encryption would use all of
> > > the bytes of three pictures. And would need the same three pictures to
> > > decrypt. A one bit change in one of the pictures and you get mush for
> > > an output.
> >
> > Actually cryptographically speaking 2^64 isn't that big, it actually
small
> > enough that a public effort has been mounted against one
(distributed.net
> > RC5 challenge), I was simply stating that 2^64 is the upper limit of the
key
> > space, more likely the key space is under 2^40.
> >
> > I wasn't even dealing with the data inside the pictures, from the
vantage I
> > was taking they merely constitute a key schedule, I was addressing the
real
> > size of the key (the choice between which pictures to use). The length
of
> > the key is actually the space from which you choose your keys, Serpent
(an
> > AES finalist) could be easily broken if you knew the key to be one of
10,
> > and Serpent is very good cryptography. It's misleading to consider the
size
> > of the picture files to be the key for cryptographic purposes simply
because
> > your choices are much more limited (similar to the US Governments view
that
> > you can use whatever cryptographic algorithms you want for export, as
long
> > as there's only x-bits of randomness).
> > Joe
>
------------------------------
Date: Thu, 06 Jul 2000 01:15:22 +0100
From: David Hopwood <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Subject: Re: AONT
=====BEGIN PGP SIGNED MESSAGE=====
David Hopwood wrote:
> Benjamin Goldberg wrote:
> > To transform:
> > for i = 1 to M
> > // hash of all the data before and after block i
> > Z = H( data[1..(i-1)], data[(i+1)..M] )
> > data[i] = data[i] XOR Z
> > end for
>
> Suppose you have all of the plaintext blocks but one, all of the
> corresponding ciphertext blocks, and *some* of the bits of the
> remaining ciphertext block. In that case, you can find some of the
> unknown plaintext bits;
My apologies, that attack doesn't work.
- --
David Hopwood <[EMAIL PROTECTED]>
PGP public key: http://www.users.zetnet.co.uk/hopwood/public.asc
RSA 2048-bit; fingerprint 71 8E A6 23 0E D3 4C E5 0F 69 8C D4 FA 66 15 01
=====BEGIN PGP SIGNATURE=====
Version: 2.6.3i
Charset: noconv
iQEVAwUBOWPPgjkCAxeYt5gVAQEwTgf/QNo+h1zkaCYuR8RRPH7ZRuX6g5P98HQa
eduZNGIGNXXQfKrflTxVtn9jEN266q/mr301YpLa5xTDopiYvR4SssAG08u10SeN
B8fznguln2fku3OJCKSpuoCytQ2lPs1FGbs6SNPTr/t0jwcq+3A9Xr9fEzjxz+wm
7pL/rs1valH+6squlxJooz0ltNwLn1KwHv6MRP+K4L8CWIRF5sMU43LNA1QgzwiX
ZxXhhRxK7hMkN/nXDeRcSSSRI4YzPevW3aonpGmzAoAto3pZNfR1BtubrTAbS0sW
XwCWc4pEOE/v4nc11rQT6BW+QrXksDLLGn6jNR0lmquYgzlAnmviUA==
=Quaj
=====END PGP SIGNATURE=====
------------------------------
Date: Thu, 06 Jul 2000 01:41:37 +0100
From: David Hopwood <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Crossposted-To: sci.math,sci.math.num-analysis
Subject: Re: multiplication and inversion in finite fields
=====BEGIN PGP SIGNED MESSAGE=====
Mark Wooding wrote:
> Stefan Karrmann <[EMAIL PROTECTED]> wrote:
>
> > For finite fields with 2^(2^n) (n natural) elements, there is an
> > multiplication called Conway multiplication (see chapter 6
> > `The Curious Field On2' of the book `On Number of Games' by John
> > Horton Conway. [...]
>
> Hmm. Has anyone patented doing cryptography in elliptic curves in
> finite fields using Conway's representation?
I don't know, but it's not a good idea: there is a more efficient
algorithm for the discrete log problem in elliptic curves over GF(2^m)
when m is composite, than when m is prime (see
http://www.security.ece.orst.edu/emails/ieee00/0008 and
http://www.hpl.hp.com/news/ecc.html).
- --
David Hopwood <[EMAIL PROTECTED]>
PGP public key: http://www.users.zetnet.co.uk/hopwood/public.asc
RSA 2048-bit; fingerprint 71 8E A6 23 0E D3 4C E5 0F 69 8C D4 FA 66 15 01
=====BEGIN PGP SIGNATURE=====
Version: 2.6.3i
Charset: noconv
iQEVAwUBOWPVpzkCAxeYt5gVAQEQDQf7BwAouYl3DU3lL0M1ssc39x3LGhnwdGrz
Vauo4ijCw18B86z7izb8F40lrT3jWuKCfrjXieQykhQOCIXtKjsmdmdbA9I1V7S8
FRBKMMsKJgwlrvU5icYWQhZ7Lg+ZW8PFHjb/TWo0yj4rtWup3smn92PYK2htIiIZ
60+znLEBPo9nOHtmYzZDgUB8DGeHhd1lI6aEiV9k6wprCSuTtfbD1u8StJ3tfs4u
RQ+p6PTqLm/taDbTKIqcmz3ep25azQAHBz8vhQ14yMsg9L7V+n1JIqUw/0uWLHw9
Y2CV8OkQP+PQY/utS3p5pN+d+V78jtRn17CuashPWXM8hYMFQs3muA==
=vnFg
=====END PGP SIGNATURE=====
------------------------------
From: [EMAIL PROTECTED] (JPeschel)
Subject: Re: Hash and Entropy
Date: 06 Jul 2000 01:53:07 GMT
[EMAIL PROTECTED] (wtshaw) wrires, in part:
>The biggest problem is that the word can be taken to be opposite in
>meaning, such as "raising" a structure means.... to build it, or tear it
>down.
Nope, raising and razing are two different words.
>...which means that other words are better used, or that improper use is
>simply based on a poor understanding of physics.
or a poor understanding of English.
Joe
__________________________________________
Joe Peschel
D.O.E. SysWorks
http://members.aol.com/jpeschel/index.htm
__________________________________________
------------------------------
From: Benjamin Goldberg <[EMAIL PROTECTED]>
Subject: CRC question
Date: Thu, 06 Jul 2000 02:42:56 GMT
Is it possible, for an N-bit CRC, for any n ( 1 <= n <= N ) 1-bit
changes in a message M ( bitlength(M) <= 2**N ), the output value
changes?
If so, how do I generate the polynomial for such a CRC?
------------------------------
From: Benjamin Goldberg <[EMAIL PROTECTED]>
Subject: Re: AONT
Date: Thu, 06 Jul 2000 02:42:58 GMT
David Hopwood wrote:
> Benjamin Goldberg wrote:
> >
> > What do you people think of the following all-or-nothing-transform
> > [good, bad, ugly?]
>
> Ugly, because it takes time proportional to the square of the number
> of blocks in the message, and bad, because of the attack given below.
You're definitely right that it's ugly, especially wrt time, but I'm not
so sure about that attack
> > Start with a hash function H, which outputs N bits.
> > Partition the file into M N-bit blocks [it's ok if the last block is
> > short, but not-ok if the file is less-than one block]
> >
> > To transform:
> > for i = 1 to M
> > // hash of all the data before and after block i
> > Z = H( data[1..(i-1)], data[(i+1)..M] )
> > data[i] = data[i] XOR Z
> > end for
>
> Suppose you have all of the plaintext blocks but one, all of the
> corresponding ciphertext blocks, and *some* of the bits of the
> remaining ciphertext block. In that case, you can find some of the
> unknown plaintext bits; for a secure AONT, it shouldn't be possible
> to do this.
I'd be interested in how you're going to get all of the plaintext blocks
but one. Actually, I'd be interested in knowing how you're going to get
any plaintext blocks.
> For some applications of AONTs this wouldn't matter, but combined with
> the poor efficiency, I think it's enough to knock this scheme on the
> head.
Erm, you're right that the efficiency is bad, but I don't know how to
make it better. I should point out that the hash function need not be
cryptographically secure, but merely good ... I think CRC might even be
sufficient.
------------------------------
Date: Thu, 06 Jul 2000 03:50:34 +0100
From: David Hopwood <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Subject: Re: A simple all-or-nothing transform
=====BEGIN PGP SIGNED MESSAGE=====
Mok-Kong Shen wrote:
> David Hopwood wrote:
> > Mok-Kong Shen wrote:
> > > David Hopwood wrote:
> > >
> > > > If the requirement for the function to be unkeyed is dropped, then
> > > > "all-or-nothing transform" is the wrong term to use; instead use
> > > > either "pseudo-random permutation" (for deterministic functions) or
> > > > "semantically secure encryption scheme" (for non-deterministic
> > > > functions).
> > >
> > > I don't share your view. All-or-nothing transform means that one
> > > applies a procedure to make the encryption (component) processes
> > > of a message so, that the opponent is forced to deal with the whole
> > > of the ciphertext material and can't simply concentrate his efforts
> > > to a part of it and thus achieve economy in his attack (which may even
> > > be critical for his success).
If the encryption scheme is secure then there is no feasible attack,
regardless of how much of the ciphertext is available. I therefore don't
see why it's useful to consider an "all-or-nothing encryption scheme"
(even if it were adequately defined) to be better than any other secure
scheme, for which there is *theoretically* sufficient information to
determine part of the plaintext even if not all of the ciphertext is
available, but for which no part of the plaintext can be found in
practice.
(Frankly, I don't see the point of the scheme in Rivest's 1997 paper; if
the key length is artificially limited to be too small, it is naive to
assume that multiplying the attacker's work by the message length will
improve that sufficiently. Messages simply aren't long enough to make such
a scheme secure, and even if they were, the attacker's work is only
multiplied by the same factor as the user's. Also, since the paper was
written, the premise behind limits on key sizes has been rendered moot by
the relaxation of U.S. export regulations. There are other useful
applications of AONTs, but most of them require an unkeyed function.)
> > For *any* secure encryption scheme, an adversary can't simply concentrate
> > his efforts on a part of the ciphertext. Roughly speaking, if an
> > adversary can feasibly recover any information about the plaintext given
> > all of the ciphertext, the encryption scheme is not semantically secure.
> > This obviously also holds if the adversary is given only part of the
> > ciphertext (if a scheme is considered insecure when an adversary can break
> > it given some amount of information, it must also be considered insecure
> > when he/she can break it given a strict subset of that information).
> >
> > This means that what you appear to be requiring of a keyed AONT can't be
> > objectively distinguished from what is required of any other semantically
> > secure encryption scheme. That's why I claim that it is clearer to use
> > one of the terms "all-or-nothing transform" (which must be unkeyed),
> > "pseudo-random permutation", or "semantically secure encryption scheme".
> > All of these have formal definitions of security, the first given in
> > [Boyko99], and the other two in [BDJR97], for example.
>
> People that brute force a block cipher work only on a couple of
> blocks, don't they?
A secure block cipher will not be breakable by brute-force; that's one of
the simplest attacks to defend against, by making the key sufficiently
long.
However, if you really want to analyse whether information about the
plaintext can be found by a computationally unbounded attacker when not
all of the ciphertext is available, that can be done by assuming that the
key is known, as I did in my first reply to this thread. That gives the
same result as assuming that the key can be brute-forced, and so there is
no loss of generality in taking AONTs to be unkeyed.
[snip]
> > > As to the second half of your sentence, I wonder how I am going to
> > > classify my use of two non-linear block chaining steps (see a follow-up
> > > of mine of 3rd. Jul), which also forces the opponent to treat the entire
> > > message, according to your terminology.
> >
> > I wouldn't try to classify what security properties it has unless I had
> > time to analyse it thoroughly, which I don't.
>
> Independent of whehter my scheme is any good, it plainly shows
> that your classification scheme is inappropriate.
No, it doesn't. Your scheme is an encryption scheme, not an AONT. Whether
it is semantically secure or not, I've no idea.
- --
David Hopwood <[EMAIL PROTECTED]>
PGP public key: http://www.users.zetnet.co.uk/hopwood/public.asc
RSA 2048-bit; fingerprint 71 8E A6 23 0E D3 4C E5 0F 69 8C D4 FA 66 15 01
=====BEGIN PGP SIGNATURE=====
Version: 2.6.3i
Charset: noconv
iQEVAwUBOWPpkTkCAxeYt5gVAQGC3Af/YVpO8IWI0Xni/DG19t+ByRsAheBEKSg6
kOJbK69id6zBIS0X/2X8yu7vHK7LJgrToj1MuEsmauUiNYUC4zAMTCS1bRvB0dvm
LjBdwDVlzSbD7IsYToFcDMCBNHvy/99QHQ0VfaPoXkIBn6dI/UwpVaApnRR3/5Id
/T/J+Y1/svhQM9oqVxDkWgYWAZOudpvhyAPuymvndQ5cJW1NFeAvnxRD40ecRJt8
nT98a/faBZ5ULYPtRBSW+1wCsCdfG35B2967s3+g6xZQ+0ioqdDui3MIpnWBf69G
0Warp83E8z+YXm/qGsJIJmRs7TXp8kO4SR9J9vrK6tjRcC9zmTSiww==
=iEv+
=====END PGP SIGNATURE=====
------------------------------
From: "Scott Fluhrer" <[EMAIL PROTECTED]>
Subject: Re: CRC question
Date: Wed, 5 Jul 2000 21:02:18 -0700
Benjamin Goldberg <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> Is it possible, for an N-bit CRC, for any n ( 1 <= n <= N ) 1-bit
> changes in a message M ( bitlength(M) <= 2**N ), the output value
> changes?
No, unless N = 1
Consider the 2**N messages consisting of 2**N-1 zeros and a one, and the 1
message consisting of 2**N zeros. There is a total of 2**N+1 messages here,
and each pair of messages has either 1 bit or 2 bit hamming distance. Since
an N-bit CRC has only 2**N possible values, there is a collision in here
somewhere.
--
poncho
------------------------------
From: zapzing <[EMAIL PROTECTED]>
Subject: Re: Hash and Entropy
Date: Thu, 06 Jul 2000 04:37:42 GMT
In article <8ju0de$b7q$[EMAIL PROTECTED]>,
David A Molnar <[EMAIL PROTECTED]> wrote:
(many snips)
>
> At the "wishful thinking" end of the spectrum, we would like our
> hash function to perfectly simulate a "random function" or "random
> oracle." Put another way, we want the output of the function to
> "look random." We can think of a random function as one which,
> on a given input, flips coins to give an output and "remembers"
> all the previous inputs -- if you ask it for a new x, it gives
> a random h(x), but if you ask the same y you asked before, it
> gives the same h(y).
The word "oracle" is certainly getting alot of
use these days. I wish people would use it for
its original use, which was a theoretical (and
probably impossible) device which could
determine if a given program would terminate
at some time or run forever.
--
If you know about a retail source of
inexpensive DES chips, please let
me know, thanks.
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: Some dumb questions
Date: Thu, 06 Jul 2000 06:13:55 GMT
On Tue, 06 Jun 2000 10:13:10 +0200, Mok-Kong Shen
<[EMAIL PROTECTED]> wrote, in part:
>1. If a bit sequence has a certain known small bias in
> frequency but is uncorrelated, how can one exploit
> that fact to analyse messages encrypted with xor?
One can't, very well. That's why the NSA considered the improved
SIGCUM secure, even though the bits it produced had a slight bias. The
original version generated exactly 50% ones, but had _genuine_ flaws.
See my web page, with information derived from a paper in Cryptologia
entitled "The SIGCUM Story".
>2. If an ideal OTP is misused, in that it is used a small
> number n of times, how is one going to attack, if
> absolutely no known plaintext is available?
This one has already been answered, I think by me among others; it is
fairly easy.
John Savard (teneerf <-)
http://www.ecn.ab.ca/~jsavard/crypto.htm
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: Even an Amplified Boomerang Won't Cascade
Date: Thu, 06 Jul 2000 06:45:34 GMT
On Wed, 05 Jul 2000 13:48:51 GMT, [EMAIL PROTECTED]
(John Savard) wrote, in part:
>Well, after playing with the idea, I saw why it still would not work.
>However, even this failed attempt might be instructive, and so an
>account of it is now added to my web page, at
>http://www.ecn.ab.ca/~jsavard/crypto/co041001.htm
I've added a diagram, and added a few minor corrections, including a
clear explanation of how the birthday paradox would work the second
time (of course, using it twice makes the complexity equal to that of
the codebook attack).
Of course, a characteristic like that of a single Feistel round
essentially requires a unique value for only half the block, so under
some extraordinary circumstances (a Feistel cipher where all the
rounds except the first and last have an informative characteristic
with 99.9999% probability) this 'attack' might have some value. Or
perhaps it will stimulate others to think of something useful.
John Savard (teneerf <-)
http://www.ecn.ab.ca/~jsavard/crypto.htm
------------------------------
From: Benjamin Goldberg <[EMAIL PROTECTED]>
Subject: Information-theoretic hash question (was Re: CRC question)
Date: Thu, 06 Jul 2000 07:02:56 GMT
Hmm, what if I change it to bitlength(M) strictly-less-than 2**N, rather
than less-than-or-equal ? Or do I have to use 2**(N-1) for it to work?
Broadening the question, and asking various permutations:
1) What is the maximum hamming distance that two Y-bit messages can
have, and still have two different X-bit hashes?
2) What is the minimum hash size needed to detect differences in Y-bit
messages which have a hamming distance Z?
3) What is the maximum message length for which an X bit hash can detect
differences between messages which have a hamming distance of Z?
Scott Fluhrer wrote:
>
> Benjamin Goldberg <[EMAIL PROTECTED]> wrote in message
> news:[EMAIL PROTECTED]...
> > Is it possible, for an N-bit CRC, for any n ( 1 <= n <= N ) 1-bit
> > changes in a message M ( bitlength(M) <= 2**N ), the output value
> > changes?
> No, unless N = 1
>
> Consider the 2**N messages consisting of 2**N-1 zeros and a one, and
> the 1 message consisting of 2**N zeros. There is a total of 2**N+1
> messages here, and each pair of messages has either 1 bit or 2 bit
> hamming distance. Since an N-bit CRC has only 2**N possible values,
> there is a collision in here somewhere.
------------------------------
** 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
******************************
