Cryptography-Digest Digest #336, Volume #12 Wed, 2 Aug 00 06:13:00 EDT
Contents:
Re: Stream Ciphers ("Douglas A. Gwyn")
Re: Small block ciphers (Mack)
Re: counter as IV? ("Douglas A. Gwyn")
I did do it PROTOCOL: ("R Fabian")
Re: unbreakable code? ("Graham Orme")
Re: Pegwit - "Weak" ECC with GF(2^m), m composite? ("Sergio Arrojo")
Re: counter as IV? (Mark Wooding)
Re: Skipjack and KEA test vectors (Mark Wooding)
Parameter generation ("Sergio Arrojo")
Re: Combining bit sequences (Mok-Kong Shen)
Re: Small block ciphers (Mok-Kong Shen)
Re: Small block ciphers (Mok-Kong Shen)
----------------------------------------------------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Subject: Re: Stream Ciphers
Date: Wed, 02 Aug 2000 08:18:05 GMT
Tom Anderson wrote:
> classical stream ciphers (which are CPRNGs whose output stream is
> xored/added into the plaintext stream to give ciphertext stream, with no
> input into the CPRNG save the key) suffer badly from ...
Stream ciphers don't have to be structured that way.
That you seldom see them described otherwise in the
open literature is simply due to a failure of
imagination and lack of experience with them.
------------------------------
From: [EMAIL PROTECTED] (Mack)
Subject: Re: Small block ciphers
Date: 02 Aug 2000 08:25:10 GMT
>
>On 01 Aug 2000 04:16:24 GMT, in
><[EMAIL PROTECTED]>, in sci.crypt
>[EMAIL PROTECTED] (Mack) wrote:
>
>>[...]
>>Obviously an 8 bit cipher is subject to dictionary attack.
>>With a small password a cipher is subject to brute force.
>
>If by "dictionary attack" you mean an attack on the key, that is not
>obvious. An "8-bit" block cipher is a permutation of 2^8 = 256
>elements, and so there are 256! possible keyings, or (from
>
> http://www.io.com/~ritter/JAVASCRP/PERMCOMB.HTM#Factorials
>
>), some binary value with about 1684 bits. This is a large enough
>keying potential.
>
By dictionary attack I mean the accumulation of a dictionary of
plaintext/ciphertext pairs. This may be done through statistical
analysis of ciphertext, known plaintext, or chosen plaintext.
>
>>But perhaps it is possible to make a cipher that is
>>provably secure if we use 8 bit blocks. By provably secure
>>I mean no attacks better than dictionary or brute force.
>
>The problem with a small block is that there are so few elements in
>the selected random permutation.
>
>First, if we encipher individual letters into block elements, the
>result will have the same statistics as the letters. This is just
>Simple Substitution as in newspaper ciphers.
>
This is the application of a statistical analysis to a ciphertext only
dictionary attack.
>Next, we normally expect to encounter known plaintext. But with an
>8-bit block, even in the best possible case we can't send any more
>than 255 blocks before the transformation is absolutely known. (In
>general, a better estimate would be 16 blocks before we start getting
>repeats we already know.)
>
>And of course defined plaintext will resolve the block directly.
>
These are examples of a dictionary attack.
>
>>My current interest is in block ciphers. I am not sure
>>what relevance the security of stream ciphers has in this.
>>Certainly adding state increases security, however doing so
>>it is no longer a block cipher.
>
>Small transformations may make more sense as a stream cipher, since
>there will be some hidden RNG involved, or tables can be used in
>arbitrary order, or their contents changed. For the single unchanging
>transformation of a block cipher, only size and plaintext distribution
>hides the contents.
I am more interested in the theoretical properties of a small block cipher.
For example, If we change the key after every second encryption. Can an
attacker find the key? Or if we change the key in some linear manner after
every encryption can an attacker find the key for N encryptions where the
key size is N*M?
>
>---
>Terry Ritter [EMAIL PROTECTED] http://www.io.com/~ritter/
>Crypto Glossary http://www.io.com/~ritter/GLOSSARY.HTM
>
Mack
Remove njunk123 from name to reply by e-mail
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Subject: Re: counter as IV?
Date: Wed, 02 Aug 2000 08:36:15 GMT
"David A. Wagner" wrote:
> Note that your proposal _can_ be modified to allow a proof of security.
> Introduce a secure pseudo-random function F, and choose the secret key K
> from the keyspace of F. Then,
> set N := 0
> for each plaintext block Bi:
> let L_N := F(K, N)
> encrypt Bi using key L_N in algorithm E
> increment N
> It is straightforward to prove this secure (so long as N never repeats).
? Why is a "related-key" attack not still possible?
For a *known* F and N, surely there is a known relationship
between F(K,N) anf F(K,N+1), although it might not be
expressable as simply as when F is merely the XOR function.
Indeed, clearly the scheme is *not* secure in an absolute
sense, since for normal plaintext the key can be recovered
(by exhaustive search of the key space). I guess you meant
that it cannot be cracked more easily than E used as ECB.
It would be instructive to see the "straightforward" proof.
My intuition is that F would have to be a genuinely random
function to make the proof work.
------------------------------
From: "R Fabian" <[EMAIL PROTECTED]>
Subject: I did do it PROTOCOL:
Date: Wed, 2 Aug 2000 09:46:52 +0100
Is there any way (protocol) that can be used to prove that a person (in this
case game player) has got the ping he says he has. Also, is there any way
that I can use a protocol to proove that a choice was made before helpful
data was recieved? By this I mean, is there a protocol that could eliminate
the DODGE.BOT scripts. I want to make sure the client decided to dodge based
on guess work rather than information.
Server will be trustworthy, but client will be aggressive cheater. roughly
all I really need is a system that proves that a network packet was sent at
the time it was sent.
------------------------------
From: "Graham Orme" <[EMAIL PROTECTED]>
Subject: Re: unbreakable code?
Date: Wed, 02 Aug 2000 08:56:14 GMT
"jkauffman" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> In article
> <u0bh5.16860$[EMAIL PROTECTED]>, "Graham
> Orme" <[EMAIL PROTECTED]> wrote:
> > My apologies if this is old, but this seems to be a
> > technique that creates
> > an encryption that cannot be decoded. This is because
> > there is a key for
> > every permutation of the encrypted message, so one can
> > make it into anything
> > at all.
> > This example works on 1000 digit blocks of
> > numbers, which might be for
> > example ascii. John and Mary wish to exchange
> > messages. First, John sends by
> > some secure method a (for example) 10,000 digit number
> > perhaps by meeting or
> > by courier. Mary now has the 10,000 digit number,
> > called A. John then
> > composes a password of 10,000 digits called B and
> > subtracts A from it and
> > send this to Mary. Mary receives B-A and because she
> > knows A now knows B but
> > no eavesdropper can know B or A which can be any
> > possible 10,000 digit
> > numbers. Mary gets another 10,000 digit number called
> > C perhaps randomly and
> > subtracts B from it, and sends C-B to John. Of course
> > an eavesdropper cannot
> > know C or B from the number sent. They continue in
> > this way until they have
> > enough secure passwords. Note that if someone learned
> > A they could find out
> > the rest, so the security hinges on A being secure.
> > John and Mary now want to send 1000 digit numbers
> > to each other, which
> > might be ascii messages or anything else. John's first
> > message is called Z.
> > John takes the first 1000 digits of B and subtracts it
> > from the message Z,
> > then takes the next 1000 digits of B and add it to Z,
> > then the next 1000
> > digits and subtracts it from Z and so on until the
> > 10,000 digits of B are
> > used. John sends this message and Mary decodes it
> > since she knows B. Mary
> > composes a message Y and encodes it with the password
> > C as before which John
> > knows how to decode. They can continue like this
> > forever wthout any
> > eavesdropper being able to decipher any message, since
> > each possible 1000
> > digit number can be gotten from a corresponding 10,000
> > digit number. One
> > therefore cannot narrow down what the 1000 digit
> > message to any less than
> > all the possible numbers up to 1000 digits long. The
> > password could be less
> > than 10,000 digits and still be secure, and might even
> > be ok at 1,000
> > digits.
> > Any flaws in this?
>
> What you've described is a one time pad. Unfortunately
> you've broken the golden rule of one time pads and used it
> twice. Once to encrypt a message and again to send a new
> otp. The otp itself, used once, is perfectly secure
> because all you know is that you're looking for a key (a
> pad) that decrypts to say an English text message. The
> problem is that any message of the right length is equally
> likely, so the attacker is stuck.
> The method you describe gives the attacker an advantage if
> he knows the history of the conversation, because he is now
> not only looking for a key that decrypts the message to
> English, but also one that, added to the last encrypted key,
> decrypts the last message to English.
> It's also highly vulnerable to known-plaintext attacks, and
> would become less secure over time for this reason.
G. This reply is for all 3 respondents. Yes I agree. However it seems
difficult to find this message because of all the combinations. The correct
message is 1 in 1e10,000, and the only way is to work on 2 messages or more
at once which is 1 in 1e20,000 of finding the right message. This can be
relatively easily improved for example by adding two passwords together say
B+D and even if the plaintext is found and this number worked out there is
still an enormous job to find B and D. The main benefit I find (if this is
all correct) is the encryption time would be very low, and passwords can be
exchanged in advance. Still another variation is to start with 3 secret
passwords exchanged when John and Mary meet. The first is used as before,
the second is added to C-B,D-C,etc on each transfer to mask these values,
and the third is added to B+D and each pair of passwords and the total used
to encrypt with. This doesn't slow down the process but makes cracking much
longer. For example even discovering the plaintext of 3 messages one would
apparently still not be able to decode the fourth for sure but would need to
work on two messages with the three cracked ones.
As an added wrinkle one could encrypt with BD here (that is, multiple 2
passwords together instead of adding them) and use the first 10,000 digits
as well. The main idea is in using additions one cannot be sure the message
one finds the correct one except by examining many together.
>
>
>
> * Sent from AltaVista http://www.altavista.com Where you can also find
related Web Pages, Images, Audios, Videos, News, and Shopping. Smart is
Beautiful
------------------------------
From: "Sergio Arrojo" <[EMAIL PROTECTED]>
Subject: Re: Pegwit - "Weak" ECC with GF(2^m), m composite?
Date: Wed, 2 Aug 2000 10:48:32 +0200
Reply-To: "Sergio Arrojo" <[EMAIL PROTECTED]>
">
> Further adding to my confusion is the fact that George Barwood writes that
> Pegwit uses "an elliptic curve over GF(2^255)." Well, 255 is prime so that
> shouldn't be a problem?
255 is not a prime, it can be divided by 5,3,17...
------------------------------
From: [EMAIL PROTECTED] (Mark Wooding)
Subject: Re: counter as IV?
Date: 2 Aug 2000 09:36:58 GMT
Douglas A. Gwyn <[EMAIL PROTECTED]> wrote:
> "David A. Wagner" wrote:
> > Note that your proposal _can_ be modified to allow a proof of security.
> > Introduce a secure pseudo-random function F, and choose the secret key K
> > from the keyspace of F. Then,
> > set N := 0
> > for each plaintext block Bi:
> > let L_N := F(K, N)
> > encrypt Bi using key L_N in algorithm E
> > increment N
> > It is straightforward to prove this secure (so long as N never repeats).
>
> ? Why is a "related-key" attack not still possible?
> For a *known* F and N, surely there is a known relationship
> between F(K,N) anf F(K,N+1), although it might not be
> expressable as simply as when F is merely the XOR function.
If F is secure then this relationship is `hard' to find.
Consider, as real-world examples:
F(K, N) = HMAC-SHA1_K(N)
and
F(K, N) = SEAL_K(N)
In each of these, there clearly *is* a relationship between F(K, N) and
F(K, N + 1), but finding it without knowing K is (believed to be)
intractible.
> Indeed, clearly the scheme is *not* secure in an absolute
> sense, since for normal plaintext the key can be recovered
> (by exhaustive search of the key space). I guess you meant
> that it cannot be cracked more easily than E used as ECB.
>
> It would be instructive to see the "straightforward" proof.
> My intuition is that F would have to be a genuinely random
> function to make the proof work.
I suspect that the type of proof David Wagner is talking about will give
a tight relationship between the difficulties of breaking F, E and the
new construction W(F, E).
This isn't the sort of thing I'm good at. I may try thinking about it
in a spare moment, though.
-- [mdw]
------------------------------
From: [EMAIL PROTECTED] (Mark Wooding)
Subject: Re: Skipjack and KEA test vectors
Date: 2 Aug 2000 09:40:16 GMT
Jason Stratos Papadopoulos <[EMAIL PROTECTED]> wrote:
> Mark Wooding <[EMAIL PROTECTED]> wrote:
>
> : My implementation agrees completely with Lewis' test vectors.
> : Together with the official Skipjack test vector, I think they test
> : something like all but 16 F-table entries.
>
> When Skipjack was first released I posted the following from a C
> implementation I cobbled together:
[snip -- thanks for these]
My implementation passes all of these.
> The F table matches an initial implementation in Ada somebody posted at
> that time, and I got independent verification from someone else's
> implementation that the results match. The NIST test vector alone uses
> about half the F table iirc, and the above will use all of it.
There's a much smaller collection of test vectors which will test the
entire F-table. I have one at home, but I've not sent out a version of
Catacomb with them in. Still, the more, the merrier. I'll put them
into tests/skipjack when I get home.
-- [mdw]
------------------------------
From: "Sergio Arrojo" <[EMAIL PROTECTED]>
Subject: Parameter generation
Date: Wed, 2 Aug 2000 11:33:07 +0200
Reply-To: "Sergio Arrojo" <[EMAIL PROTECTED]>
I need to download algorithms to be able to generate parameters of eliptic
curves without weaknesses. I ve already tried Pegwit but it seems to be
limitated to m composite and a6=0. Could anybody tell me where could I find
such a program.
Thanks
Sergio Arrojo
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Combining bit sequences
Date: Wed, 02 Aug 2000 12:00:07 +0200
Future Beacon wrote:
> I have been assuming that you wish to combine bit sequences in such
> a way that they cannot be undone. The must be used by the sender
> and receiver through shared data and a shared algorithm to arrive
> at the same result by combining in the same way. Is this correct?
The given streams are known to the partners but not to the oppoent.
The intended purpose of combining them is to somehow render the
result having less potential of being exploited to his advantage.
M. K. Shen
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Small block ciphers
Date: Wed, 02 Aug 2000 12:00:18 +0200
Mack wrote:
> I am more interested in the theoretical properties of a small block cipher.
> For example, If we change the key after every second encryption. Can an
> attacker find the key? Or if we change the key in some linear manner after
> every encryption can an attacker find the key for N encryptions where the
> key size is N*M?
I believe that, if the block cipher (and hence the key size) is small,
the opponent will simply do brute-force, for that's easy for him,
while a well-designed large block cipher is impractical to brute-force
and he has therefore to resort to more intelligent means, if available.
M. K. Shen
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Small block ciphers
Date: Wed, 02 Aug 2000 12:00:48 +0200
Mack wrote:
> >> Let see an actual example.
> >> This is rather long and uses ANF.
> >> It is rather simple but it shows the principle.
> >>
> >> This can be expanded to any number of bits T.
> >> B = bits of block size
> >> K = bits of key size.
> >> T = B + K
> >>
> >> The number of terms is equal to 2^T.
> >> The number of equations is B
> >> Obviously this is impractical for large T.
> >
> >Isn't it that one can have B equations where on the left sides one
> >has the known values of the output bits , while on the left side one
> >has functions involving the K unknown values of the key bits and the
> >B known values of the input bits? If yes, then we have B equations
> >and K unknowns. Or I am missing something here?
>
> For the most part that is it. But the B equations have K unknowns
> with lots of nonlinear terms. But at some point you have T unknowns.
> Ie. before you have known values. Basically you have to develop
> the representation in T unknowns.
We are doing at the bit level, aren't we? If one substitutes the known
bits into the T terms, how can one say that an expression involving
the T terms has T unknowns instead of B unknowns? (Compare
my example quoted below.)
> >> It also illustrates how a non-linear term can
> >> be assumed to be a variable. It shows
> >> how some pairs are better than others.
> >
> >The point is whether, on introducing a non-linear term as a
> >variable, one takes away a previously existing (simple) variable,
> >or one has the non-linear term as an 'additional' (new) variable.
> >This is essential, since, if I don't err, your argument of imfeasibility
> >has to do with the count of number of variables with respect to
> >the number of equations. To use an analogous case, the equation
> >x^2+x+1=0 is normally considered to have only one variable.
> >Do you want to regard x^2, which is non-linear, to be a variable
> >and thus consider the equation to be of two variables?
> >
>
> No it is still one variable. Although regarding it as two variables
> may make solving the system of equations easier. For some systems
> it may simply be impractical to solve the set of equations without
> such reductions.
>
> The final rule is that if you have B equations in K unknowns
> then it can only be solved if the B equations are nondegenerate
> and consistent and B>=K.
>
> nondegenerate and consistent having the standard meaning of
> linear equations.
>
Is your target argument 'impracticability' or 'impossibility'? Many
non-linear equations in normal computations are very difficult to
solve. This is only impractical not impossible. My current
understanding is that you are seeking a set of equations that are
difficult to solve. But then you run into certain troubles. For the
'difficulty' is in general cases hard to quantify.
M. K. Shen
------------------------------
** 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
******************************
