Cryptography-Digest Digest #741, Volume #10 Tue, 14 Dec 99 20:13:01 EST
Contents:
Re: Why no 3des for AES candidacy ("Rich Ankney")
Re: Non-linear PRNGs (John Savard)
Re: The Cracking of SecurityPlus! 4.32 (Troed)
Re: Deciphering without knowing the algorithm? (SCOTT19U.ZIP_GUY)
Re: Better encryption? PGP or Blowfish? (SCOTT19U.ZIP_GUY)
Re: How to implement different modes using the twofish algorithm? (Eric Lee Green)
Re: Simple newbie crypto algorithmn (David Wagner)
Re: NAI granted export license for PGP (Keith)
Re: Non-linear PRNGs (David Wagner)
Re: Deciphering without knowing the algorithm? ("Arrianto Mukti Wibowo")
Re: Deciphering without knowing the algorithm? ("Arrianto Mukti Wibowo")
help: why q|(p-1) ("Arrianto Mukti Wibowo")
Re: Non-linear PRNGs (Tim Tyler)
Re: Non-linear PRNGs (Tim Tyler)
Re: Non-linear PRNGs (Tim Tyler)
Re: help: why q|(p-1) (David A Molnar)
----------------------------------------------------------------------------
From: "Rich Ankney" <[EMAIL PROTECTED]>
Subject: Re: Why no 3des for AES candidacy
Date: Tue, 14 Dec 1999 17:18:33 -0500
Trevor Jackson, III wrote in message <[EMAIL PROTECTED]>...
>Anton Stiglic wrote:
>
>> >
>> >
>> > You did not say why the objection was nonsense and confuses people, you
>> > just asserted so. Is there some divine revelation you can share with
>> > us?
>>
>> Sure, I could share (don't know if it's divine do!). The initial
>> question,
>> to the post was:
>>
>> Why isn't 3des being considered for the AES? Is it because it is
slower
>> than
>> DES?
>>
>> For which I answered:
>> One good reason:
>> The AES is supposed to support the following different key sizes: 128,
>> 192, 256
>> You can see why 3-DES, with it's single sized168 bit key, does not fit
>> in this
>> categorie.
>>
>> To which Mr. Uli responded:
>>
>> No I can't - there are ways to securely make key of any length
>> (from 64 bis to 768*3 bits) for 3DES.
>>
>> To which I responded negatively. 3DES, as define in the standard,
>> does not use 128, 192 nor 256 bit keys.
>
>"The standard"? What standard is that?
>
Umm, that would be FIPS 46-3 and ANSI X9.52, both of which allow
either 112-bit or 168-bit keys.
>3DES was originally proposed with a 112-bit key and E(D(E())) arrangement
to
>insure backward compatibility with DES. The 168-bit variant is not the
only
>valid usage.
>
True; 112-bit or 158-bit are allowed (and have been heavily studied).
>>
>>
>> What is so complicated? A modification of 3DES, as slight as it might
be,
>>
>> no longer defines 3DES (the standard).
>>
>> What do you not agree with?????????????
>
>Your last statement. 3DES with 128/168 bits of warm key is still 3DES. It
>just has a key (mis)management wrapper to match the AES requirements.
>
No. Also, you both forget that AES has a 128-bit blocksize...
>In a similar vein standard ciphers with 64 or 128-bit keys can be damaged
by
>restricting the key space in order to get export approval. Such a
mechanism
>does not invalidate the algorithm. It still operates according to the
>standard. Thus the key restriction mechanism introduces no new weaknesses
or
>attacks except that of the reduced key space.
>
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: Non-linear PRNGs
Date: Tue, 14 Dec 1999 15:11:43 GMT
Mok-Kong Shen <[EMAIL PROTECTED]> wrote, in part:
>Question: Has anyone studied such PRNGs from cryptological point
>of view? I surmise that they are extremely hard for analysis even
>with moderate values of n.
One thing is clear: the Blum-Blum-Shub algorithm, regarded as secure,
is closely related to this.
John Savard (jsavard<at>ecn<dot>ab<dot>ca)
http://www.ecn.ab.ca/~jsavard/crypto.htm
------------------------------
From: [EMAIL PROTECTED] (Troed)
Subject: Re: The Cracking of SecurityPlus! 4.32
Reply-To: [EMAIL PROTECTED]
Date: Tue, 14 Dec 1999 22:22:18 GMT
[EMAIL PROTECTED] (JPeschel) wrote:
>source code to Kremlin for analysis. But he didn't
>crack Kremlin or find any weakness; he recently
>e-mailed Mach5 Software and admitted defeat,
>saying 'OK, you won. I surrender!'."
Nice to hear, even though it makes all those photos in my .kgb a loss
:) Thanks for your input!
___/
_/
Nazister, rasister och andra d�rar - ger bara sig sj�lva kalla k�rar
------------------------------
From: [EMAIL PROTECTED] (SCOTT19U.ZIP_GUY)
Subject: Re: Deciphering without knowing the algorithm?
Date: Tue, 14 Dec 1999 23:39:35 GMT
In article <[EMAIL PROTECTED]>, Douglas Hinton <[EMAIL PROTECTED]>
wrote:
>Something which no one mentioned is that if you know what kind of
>encryption equipment is being used, one needs only to buy a similar unit
>and install the known key. The equipment could have the worlds strongest
>algorithm, but a person wouldn't need to anything about it to "listen
>in."
>
Something tells me that your not to bright. Where does one get the
"known key" You must be the kind of person who would be the type
to blow money on expensive crypto equipment from the Swiss where
it comes preinstalled with a red thread from our friendly NSA so they
can read the data realtime.
David A. Scott
--
SCOTT19U.ZIP NOW AVAILABLE WORLD WIDE
http://www.jim.com/jamesd/Kong/scott19u.zip
Scott famous encryption website NOT FOR WIMPS
http://members.xoom.com/ecil/index.htm
Scott rejected paper for the ACM
http://members.xoom.com/ecil/dspaper.htm
Scott famous Compression Page WIMPS allowed
http://members.xoom.com/ecil/compress.htm
**NOTE EMAIL address is for SPAMERS***
------------------------------
From: [EMAIL PROTECTED] (SCOTT19U.ZIP_GUY)
Subject: Re: Better encryption? PGP or Blowfish?
Date: Tue, 14 Dec 1999 23:34:51 GMT
In article <835f4t$9d$[EMAIL PROTECTED]>, Tom St Denis <[EMAIL PROTECTED]> wrote:
>In article <8348is$2g18$[EMAIL PROTECTED]>,
> [EMAIL PROTECTED] (SCOTT19U.ZIP_GUY) wrote:
>> This just shows how fucking stupid you are little boy pain
>> in the ass. Try reading what a ZERO Iinformation system is
>> sometimes instead of opening your mouth. In a ZERO information
>> protocall the seeds are in there to solve any encryption including
>> that of a random file. IF you think mine has enough information
>> for a random file break your not only full of shit but you know
>> nothing about encryption. Try to learn something Tom becasue
>> your posts are gettting dumber and dumber and it is getting
>> frustracting wasting my time to try to improve your pee brain.
>
>I will just go out invent this new attack called brute force. I will
>win a nobel. If I can brute force any system, then that system has
>given me enough information to break it.
>
>And last time I checked most block ciphers fell into this category. No
>matter how you use the block cipher, if the key is fixed, and used on
>more then one block it can be attacked.
>
Asshole even if I used a 4 bit key if the program I used was done
correctly you may not know what the anwser is. With a ZERO
knowledge method you KNOW what the encyrpted message is.
You may not know what it means but you know what the message
is ASSHOLE wake up and learn something. I getting tired of changing
your diapers so to keep from using so many swear words you going
back on my Kill file list. Actually your the only one on it.
David A. Scott
--
SCOTT19U.ZIP NOW AVAILABLE WORLD WIDE
http://www.jim.com/jamesd/Kong/scott19u.zip
Scott famous encryption website NOT FOR WIMPS
http://members.xoom.com/ecil/index.htm
Scott rejected paper for the ACM
http://members.xoom.com/ecil/dspaper.htm
Scott famous Compression Page WIMPS allowed
http://members.xoom.com/ecil/compress.htm
**NOTE EMAIL address is for SPAMERS***
------------------------------
From: Eric Lee Green <[EMAIL PROTECTED]>
Subject: Re: How to implement different modes using the twofish algorithm?
Date: Tue, 14 Dec 1999 16:23:11 -0700
"Martin B�deker" wrote:
>
> Hello!
>
> I'm a newbie to this and have problems to implement following modes of
> Twofish: CFB1,CBC,ECB. I already verified - using given testvectors -
> that my implementations of makeKey, BlockEncrypt and BlockDecrypt are
> delivering the valid outputs, but I can't get proper results in CBC
> mode.
> For CBC I XORed the plaintext (PT) and the IV and at then encrypted it
> using my function. But the resulting ciphertext (CT) differs from the
> CBC testvectors.
> CT = Encrypt(PT xor IV)
Make sure you're only XOR'ing with the IV for the first block. After that, you
XOR the current block with the last-encrypted block. Also make sure you're
XOR'ing the current block BEFORE you encrypt it, not AFTER.
--
Eric Lee Green [EMAIL PROTECTED]
Software Engineer Visit our Web page:
Enhanced Software Technologies, Inc. http://www.estinc.com/
(602) 470-1115 voice (602) 470-1116 fax
------------------------------
From: [EMAIL PROTECTED] (David Wagner)
Subject: Re: Simple newbie crypto algorithmn
Date: 14 Dec 1999 15:33:52 -0800
In article <[EMAIL PROTECTED]>,
Steven Siew <[EMAIL PROTECTED]> wrote:
> It's not designed to be fast. It's designed to be secure. Again memory
> was not considered by me during the design process.
Anyone can design a secure cipher if it's allowed to be big and slow.
Just use umpteen-DES, or somesuch, with ten copies of D. Scott's favorite
chaining mode thrown in for good measure (why not?).
The question is, why would anyone use a new, slow algorithm when there
are others available that are both faster and better understood (=> more
likely to be secure)?
(Maybe this was intended only for fun, and was not suggested for actual
use. If so, I apologize; my comments would be irrelevant in such a case.)
------------------------------
From: Keith <[EMAIL PROTECTED]>
Subject: Re: NAI granted export license for PGP
Date: Tue, 14 Dec 1999 15:44:48 -0800
On Mon, 13 Dec 1999 23:25:52 GMT, Bubba
<833v9r$vn5$[EMAIL PROTECTED]> wrote:
>http://www.nai.com/asp_set/about_nai/press/releases/pr_template.asp?
>PR=/PressMedia/12131999.asp&Sel=647
>
>
The problem is that we don't know what strength the cipher is.
PGP could be allowed to export 40 bit versions. Or maybe NSA
has created a crack for PGP. If the NSA has developed a crack
then it won't affect home users, but would be a concern to
business and government users world wide.
--
Best Regards,
Keith
===================================================================
Free Software: Pegasus & Mercury Email http://pmail.usa.com/
Cyberkit http://www.ping.be/cyberkit/
Hamster http://home.t-online.de/home/juergen.haible/english.htm
SLRN for *NIX/OS2/WIN32 http://space.mit.edu/~/davis/slrn.html
=====================================================================
------------------------------
From: [EMAIL PROTECTED] (David Wagner)
Subject: Re: Non-linear PRNGs
Date: 14 Dec 1999 15:44:54 -0800
In article <[EMAIL PROTECTED]>,
Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
> In a post of Feb 1988 in sci.crypt, V. S. Anashin has given a
> general theorem for constructing full period (2^m) non-linear
> PRNGs of arbitrarily high degree. (Literature: Mathematical Notes,
> Vol. 55, 1994, p. 109-133. Plenum Pub.). This is reproduced in
> essence below:
>
> Let f(x) = a_0 + a_1*x^(1) + a_2*x^(2) + ..... + a_n*x^(n)
> where x^(k) = x(x-1)(x-2)...(x-k+1).
> Then the generator u(i) = f(u(i-1)) mod 2^m (m>2) has period
> 2^m if and only if the following congruences hold:
> a_0 = 1 mod 2, a_1 = 1 mod 4, a_2 = 0 mod 2, a_3 = 0 mod 4.
>
> Question: Has anyone studied such PRNGs from cryptological point
> of view? I surmise that they are extremely hard for analysis even
> with moderate values of n.
I don't think this is secure for cryptographic purposes.
Note that this generator never mixes the higher-order bits into the
least significant bits. In other words, you can reduce everything in
sight mod two, and all the equations still hold.
This is already a really bad property, but it only gets worse.
Due to the above property, we can just look at the low bits.
Set v(i) := (u(i) mod 2), and note that the v's satisfy
v(i) = f(v(i-1)) mod 2, so we only need to examine the generator
for the case m=1. It is also useful to note that x^(j) = 0 mod 2
for all j>1, so in essence we only need to look at f(x) = a_0 + a_1*x.
I think at this point it should be obvious that such f are easy to
break. Finally, once you've recovered the sequence mod 2, I think
you can lift up to mod 4, work from there, and proceed iteratively.
There's a fair amount of handwaving in this post, but I suspect that
with some care it could be readily developed into a full attack.
------------------------------
From: "Arrianto Mukti Wibowo" <[EMAIL PROTECTED]>
Subject: Re: Deciphering without knowing the algorithm?
Date: Wed, 15 Dec 1999 07:42:46 +0800
HKXLF wrote in message <[EMAIL PROTECTED]>...
>algorithm that is used the encrypt the text in the first place. Is it
possible
>to decrypt some text without first knowing what algorithm is used to
encrypt
>it?
I just met with Dr.Bimal Roy at AsiaCrypt '99. He presented a paper about a
technique how to guess the plaintext from cipertext without knowing the
boxes (within the algoritm) by using statistics.
You can reach him at [EMAIL PROTECTED] He teaches in the Indian Statistical
Institute.
-mukti
ps: if you e-mail him, say hi from mukti... :-)
------------------------------
From: "Arrianto Mukti Wibowo" <[EMAIL PROTECTED]>
Subject: Re: Deciphering without knowing the algorithm?
Date: Wed, 15 Dec 1999 07:39:15 +0800
HKXLF wrote in message <[EMAIL PROTECTED]>...
>algorithm that is used the encrypt the text in the first place. Is it
possible
>to decrypt some text without first knowing what algorithm is used to
encrypt
>it?
If we can rephrase your question:
not knowing the algorithm
--into--> not knowing the P & S boxes within the algorithm
then... I just met with Dr.Bimal Roy at AsiaCrypt '99. He presented a paper
about guessing the plaintext from cipertext without knowing the boxes.
You can reach him at [EMAIL PROTECTED] He teaches in the Indian Statistical
Institute.
-mukti
------------------------------
From: "Arrianto Mukti Wibowo" <[EMAIL PROTECTED]>
Subject: help: why q|(p-1)
Date: Wed, 15 Dec 1999 07:51:15 +0800
Hi there...
I need help...
I'm a student studying cryptography and e-cash. I've been wondering, why
many cryptographic protocols based on discrete log problem such as Schnorr,
Brand's e-cash, Chaum & Pedersen's DLP blind signature, etc, we must choose
a prime q & p where q divides (p-1)? q is the exponentiation modulo and p is
the 'equation modulo' (or you may say the congruent equeation modulo).
Does it has something to do with Pollard (p-1) ?
Thank you very much.
Sincerely,
-mukti
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: Non-linear PRNGs
Reply-To: [EMAIL PROTECTED]
Date: Tue, 14 Dec 1999 23:45:28 GMT
John Savard <[EMAIL PROTECTED]> wrote:
: Mok-Kong Shen <[EMAIL PROTECTED]> wrote, in part:
:>Question: Has anyone studied such PRNGs from cryptological point
:>of view? I surmise that they are extremely hard for analysis even
:>with moderate values of n.
: One thing is clear: the Blum-Blum-Shub algorithm, regarded as secure,
: is closely related to this.
...as mud? ;-)
The BBS PRNG derives its security from the difficulty of
factoring the modulus into its large prime factors.
The generator described at this thread's head has a modulus of 2^m -
and multiplying primes together is not even mentioned.
I'd say any notion that the security of BBS also applied
to the generator described here was /extremely/ premature.
--
__________
|im |yler The Mandala Centre http://www.mandala.co.uk/ [EMAIL PROTECTED]
Depression is merely anger without enthusiasm.
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: Non-linear PRNGs
Reply-To: [EMAIL PROTECTED]
Date: Wed, 15 Dec 1999 00:07:56 GMT
Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
: There was a recent thread in this group discussing ways of
: obtaining from linear congruential PRNGs bit sequences useful
: for crypto applications.
: This reminds one immediately of non-linear PRNGs, which by their
: very nature are free from the difficulties arising from linearity
: at the outset.
: In a post of Feb 1988 in sci.crypt, V. S. Anashin has given a
: general theorem for constructing full period (2^m) non-linear
: PRNGs of arbitrarily high degree. (Literature: Mathematical Notes,
: Vol. 55, 1994, p. 109-133. Plenum Pub.). This is reproduced in
: essence below:
: Let f(x) = a_0 + a_1*x^(1) + a_2*x^(2) + ..... + a_n*x^(n)
: where x^(k) = x(x-1)(x-2)...(x-k+1).
If my maths is right, x^k = x!/(x-k)!
It seems to me that this would be rather computationally intensive
on the multiplication front, as k grows.
Again, if my maths is right, it seems equivalent to a straight:
: Let f(x) = c_0 + c_1*x + c_2*x^2 + ..... + c_n*x^n
(...where x^2 = x sqaured, etc.)
The case n=2 has been studied. It is called a Quadratic Congruential
Generator.
I have read that it has been cracked - exhibiting the same type of flaw as
LCGs do - though somewhat more subtley. I'd expect that problems with
them would be made worse by making the modulus a power of two.
--
__________
|im |yler The Mandala Centre http://www.mandala.co.uk/ [EMAIL PROTECTED]
Dates in calendars are often closer than they appear.
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: Non-linear PRNGs
Reply-To: [EMAIL PROTECTED]
Date: Wed, 15 Dec 1999 00:19:58 GMT
Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
: Let f(x) = a_0 + a_1*x^(1) + a_2*x^(2) + ..... + a_n*x^(n)
: where x^(k) = x(x-1)(x-2)...(x-k+1).
: Then the generator u(i) = f(u(i-1)) mod 2^m (m>2) has period
: 2^m if and only if the following congruences hold:
: a_0 = 1 mod 2, a_1 = 1 mod 4, a_2 = 0 mod 2, a_3 = 0 mod 4.
[...]
: Question: Has anyone studied such PRNGs from cryptological point
: of view? I surmise that they are extremely hard for analysis even
: with moderate values of n.
The reference I was thinking of was from RFC1750:
Not only have linear congruent generators been broken, but techniques
are now known for breaking all polynomial congruent generators
[KRAWCZYK].
[KRAWCZYK]: How to Predict Congruential Generators, Journal
of Algorithms, V. 13, N. 4, December 1992, H. Krawczyk.
http://www.cis.ohio-state.edu/htbin/rfc/rfc1750.html
http://blitzen.canberra.edu.au/RFC/rfc/rfc1750.html
I /believe/ the generator proposed above *is* simply a polynomial
congruent generator - if you expand out the "^" operations into their
component parts.
--
__________
|im |yler The Mandala Centre http://www.mandala.co.uk/ [EMAIL PROTECTED]
I just took an IQ test. The results were negative.
------------------------------
From: David A Molnar <[EMAIL PROTECTED]>
Subject: Re: help: why q|(p-1)
Date: 15 Dec 1999 00:47:26 GMT
Arrianto Mukti Wibowo <[EMAIL PROTECTED]> wrote:
> Hi there...
> I need help...
> I'm a student studying cryptography and e-cash. I've been wondering, why
> many cryptographic protocols based on discrete log problem such as Schnorr,
> Brand's e-cash, Chaum & Pedersen's DLP blind signature, etc, we must choose
> a prime q & p where q divides (p-1)? q is the exponentiation modulo and p is
> the 'equation modulo' (or you may say the congruent equeation modulo).
Computation "in the exponents" is taken mod the order of the group in which you
are computing. That is, if you pick a prime p, and a generator g, this
calculation :
g^x * g^y = g^(x + y) mod p
requires you to consider the (x + y) mod the order of Z_p^*. Since the
order of Z_p^* can be thought of as being the "number of elements relatively
prime to p", this is p-1.
The fun part is that while p is prime, p-1 is not (assuming 1 not prime :).
So p-1 has some prime factors, each of which corresponds to a subgroup of
that same order as the factor. In this case, you're asked to pick one
of these factors, call it "q", and then do all your computation "in the
exponents" in this subgroup.
Why ? Because you can pick q to be smallish (say 160 bits) by constructing the
prime p correctly, and then this guarantees that all
your exponents will be small. Since modular exponentiation hurts
computationally, keeping the exponent sizes small can be a good thing. Plus
you no longer have to worry about accidentally choosing values which belong
to a smaller subgroup in p-1 and possibly leaking info that way.
You may also have noticed that many of these protocols ask you to please pick a
prime of the form p = 2q + 1. This ensures that the subgroup size given by q is
Really Big, so you don't have to worry about attacks on the exponent.
Anyway, if you look at what you're picking mod q, odds are it will get used
as an exponent someplace. If you picked the value mod p, then you're not sure
what would happen...
> Does it has something to do with Pollard (p-1) ?
I don't think so. I don't know if the particular choice of q affects that attack
one way or the other. :-(
Thanks,
-David Molnar
------------------------------
** 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
******************************
