Cryptography-Digest Digest #744, Volume #10 Wed, 15 Dec 99 11:13:02 EST
Contents:
Re: Better encryption? PGP or Blowfish? (Tom St Denis)
Re: security of 3des ?= des (Frank Gifford)
Re: Why no 3des for AES candidacy ("Tim Wood")
Re: discrete logorithm reduction to factoring (Nick Williams)
help: I need to crack a ms-access pwd (Olaf Kesch)
Re: how easy would this encryption be to crack? (Christoffer
=?iso-8859-1?Q?Lern=F6?=)
Re: discrete logorithm reduction to factoring (Anton Stiglic)
SSL/RC4_128_EXPORT40 ("Tobias Martin")
Re: help: why q|(p-1) (Anton Stiglic)
Re: Non-linear PRNGs (John Myre)
Prime series instead (Re: Pi) (Matthew Montchalin)
Re: SSL/RC4_128_EXPORT40 (Arturo)
Re: Better encryption? PGP or Blowfish? (James Felling)
Re: Why no 3des for AES candidacy (Paul Koning)
Re: discrete logorithm reduction to factoring (John Bailey)
----------------------------------------------------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: Better encryption? PGP or Blowfish?
Date: Wed, 15 Dec 1999 12:32:42 GMT
In article <836gmb$1g50$[EMAIL PROTECTED]>,
[EMAIL PROTECTED] (SCOTT19U.ZIP_GUY) wrote:
> 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.
You are possibly the most ignorant person on the face of earth and may
god have mercy on your soul.
BTW: If the message space is larger then the key space as is the case
for all block ciphers/stream ciphers, then you can always brute force
the keyspace. It might be infeasible in the ammount of time it will
require, but it's still possible.
Tom
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: [EMAIL PROTECTED] (Frank Gifford)
Subject: Re: security of 3des ?= des
Date: 15 Dec 1999 08:29:58 -0500
In article <[EMAIL PROTECTED]>, Tim Tyler <[EMAIL PROTECTED]> wrote:
>karl malbrain <[EMAIL PROTECTED]> wrote:
>: <[EMAIL PROTECTED]> wrote in message
>
>:> i was wondering if it has been shown that 3des is more secure
>:> than des.
>:>
>:> my understanding is that if des transformations form a group
>:> than any composition of des transformations is equivalent to
>:> a single des encryption,
>
>: In the sense that DES is a 64 bit block function that MAPS one input to one
>: output, yes, you can combine DES operations as a single MAPPING, and there
>: is no security gain. [...]
>
>However you look at it, it's been proven not to be true that any
>composition of DES transformations is equivalent to a single DES
>encryption.
Well, you should be clear here. It's true that since DES is not a group,
that 3-DES cannot be reduced to 1-DES. But that does not imply that it
is impossible for some (plaintext1, key1, ciphertext1) tupple in N-DES to
be found as (plaintext1, key2, ciphertext1) in 1-DES.
-Giff
--
Too busy for a .sig
------------------------------
From: "Tim Wood" <[EMAIL PROTECTED]>
Subject: Re: Why no 3des for AES candidacy
Date: Wed, 15 Dec 1999 13:43:08 -0000
> I am just an Engineer also but had to do programming all my life
>since most computer people not up on engineer problems.
>They lack the mathematical background one gets in Engineering.
>
you taking the mickey?
>David A. Scott
>--
tim
------------------------------
From: [EMAIL PROTECTED] (Nick Williams)
Crossposted-To: comp.theory
Subject: Re: discrete logorithm reduction to factoring
Date: 15 Dec 1999 13:54:47 -0000
In article <8373h1$7vb$[EMAIL PROTECTED]>, <[EMAIL PROTECTED]> wrote:
>It is my understanding from these discussions that
>if there was a solution for discrete log, with say
>a worst case asymtote that was cubic, that then factoring
>would be polynomial as well.
Given that this is cross-posted to sci.crypt, as well as
comp.theory, I guess you're most interested in the cryptographic
take on this.
To be honest, I've no idea whether being able to do a discrete
logarithm in polynomial time implies the ability to factor in
polynomial time.
I do know that the ability to do discrete logarithms in finite
groups would be allow you to break (for example) RSA much more
easily, since the inverse operation of modular exponentiation is
the calculation of a discrete logarithm in a finite group: the
difficulty of breaking the RSA cryptosystem has not (to my
knowledge) ever been proven to be difficulty of factoring (pq).
Cheers,
Nick.
--
[ Nick Williams ]
[ MSc Computation Mobile - 07957-138179 ]
[ New College, Oxford http://www.new.ox.ac.uk/~nick/ ]
------------------------------
From: Olaf Kesch <[EMAIL PROTECTED]>
Subject: help: I need to crack a ms-access pwd
Date: Wed, 15 Dec 1999 15:37:32 +0100
Hi...
I hope to be in the right newsgroup with my probelm. Here is it:
Somebody asked me to add some functionalities to his (legal) copy of a program
based on ms-access 2.0. Unfortunately the program-database is protected from
accessing by password (you have to be in the right group with the right pwd to
access it, I think).
Can anybody help me? You can mail to <[EMAIL PROTECTED]>.
Thanks, Olaf.
------------------------------
From: Christoffer =?iso-8859-1?Q?Lern=F6?= <[EMAIL PROTECTED]>
Subject: Re: how easy would this encryption be to crack?
Date: Wed, 15 Dec 1999 15:48:32 +0100
Jerry Coffin wrote:
> In article <[EMAIL PROTECTED]>, [EMAIL PROTECTED] says...
> > I'm using a rather simple encryption scheme and I'm kind of wondering
> > how easy it would be to crack,
> > if anyone'd like to take a look at it I'd be very happy:
>
> [ a double substitution cipher ]
>
> > keya & keyb would have different length, for example keya would be 1
> > byte longer than keyb
> >
> > Too easy to crack?
>
> The effective key length is (at most) the GCD of the lengths of the
> two keys. Assuming they're relatively prime, that means the product
> of their lengths. E.g. if they were 5 and 7 bytes long, then the
> effective key length would be 35 bytes.
Ok.
> Against a threat-model like known-plaintext or chosen-plaintext, this
> provides essentially no security at all -- once the text you've
> encrypted is just over double the effective key length, the repetition
> of the key is obvious.
Yes, just posting the algorithm made me see its flaws rather easily.
With a chosen-plaintext of zero bytes would produce the key.
Of course I got the addition of the spin variable which lengthens
the key somewhat, but still the key is there plain to see and feeding
a long enough plaintext would give it.
So, I did a slight variation, basically introducing another variable just
counting the position and rotating the bits after the first xor (see my
other mailing), I was hoping the rotation would hide the byte used to
xor the paintext. I don't know if this hides the key (the rotation depends
on one of the keys as can be seen in the algorithm) sufficiently - at
least xor:ing with byte sequence gotten from sending zeroes as a
plaintext attack won't work.
As I wrote in the other message, I checked for repetition and found
none as far as I looked (about 1000000 positions), also I got an
even distribution of numbers feeding zeroes as plaintext despite the
fact I was using two random keys of length 5 and 10 respectively.
Try this:
plaintext 14 zeroes gives
A0 3D 18 C1 E6 40 8E 5F 0C F7 D7 9D 4A 7A
a simple ascii message (14 characters):
32 1D 30 F4 EE 68 AE 1A 76 A4 87 35 05 D2
keys are 11 & 7 bytes long
How easy is this to decipher?
/Christoffer
------------------------------
From: Anton Stiglic <[EMAIL PROTECTED]>
Crossposted-To: comp.theory
Subject: Re: discrete logorithm reduction to factoring
Date: Wed, 15 Dec 1999 10:25:22 -0500
==============8DF3A79831C1604C4E4E4978
Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: 7bit
[EMAIL PROTECTED] wrote:
> After reviewing some older threads about discrete log
> and factoring I had come across a few that discussed
> the ability to factor using discrete log.
>
> It is my understanding from these discussions that
> if there was a solution for discrete log, with say
> a worst case asymtote that was cubic, that then factoring
> would be polynomial as well.
>
> It is not clear based on these discussions if this was
> indeed factual, so I have come up with the following
> questions.
>
> Is it true that discrete log reduces to factoring ?
You are talking about a solution to dicrete log problem
beeing able to help you solve factoring, but then
you ask if discrete log reduces to factoring.
You talk about two different reductions.
I can partialy answer one side: Given a fatorization of n,
you can compute discrete logs in a group mod n
in time complexity in O(sum{i=1}{r} e_i(lg n + sqrt(p_i)) )
where n = p_1 ^e_1 * ... * p_r ^ e_r.
see for example the Handbood of Applied Cryptography,
section 3.6.4.
This comes from Pohlig-Hellman algorithm for computing
discrete logarithms, which essentialy breaks up the initial
group into non trivial subgroups (given by the factorization)
and then computes DL in does subgroups.
Anton
==============8DF3A79831C1604C4E4E4978
Content-Type: text/html; charset=us-ascii
Content-Transfer-Encoding: 7bit
<!doctype html public "-//w3c//dtd html 4.0 transitional//en">
<html>
[EMAIL PROTECTED] wrote:
<blockquote TYPE=CITE>After reviewing some older threads about discrete
log
<br>and factoring I had come across a few that discussed
<br>the ability to factor using discrete log.
<p>It is my understanding from these discussions that
<br>if there was a solution for discrete log, with say
<br>a worst case asymtote that was cubic, that then factoring
<br>would be polynomial as well.
<p>It is not clear based on these discussions if this was
<br>indeed factual, so I have come up with the following
<br>questions.
<p>Is it true that discrete log reduces to factoring ?</blockquote>
You are talking about a solution to dicrete log problem
<br>beeing able to help you solve factoring, but then
<br>you ask if discrete log reduces to factoring.
<br>You talk about two different reductions.
<br>I can partialy answer one side: Given a fatorization of n,
<br>you can compute discrete logs in a group mod n
<br>in time complexity in O(sum{i=1}{r} e_i(lg n + sqrt(p_i)) )
<br>where n = p_1 ^e_1 * ... * p_r ^ e_r.
<br>see for example the Handbood of Applied Cryptography,
<br>section 3.6.4.
<p>This comes from Pohlig-Hellman algorithm for computing
<br>discrete logarithms, which essentialy breaks up the initial
<br>group into non trivial subgroups (given by the factorization)
<br>and then computes DL in does subgroups.
<p>Anton
<pre></pre>
</html>
==============8DF3A79831C1604C4E4E4978==
------------------------------
From: "Tobias Martin" <[EMAIL PROTECTED]>
Subject: SSL/RC4_128_EXPORT40
Date: Wed, 15 Dec 1999 16:38:55 +0100
Dear all,
I have a question about SSL. Export versions of U.S. browsers (e.g. german
versions of Netscape and MSIE) normaly use the SSL cipher suite
..._RC4_128_EXPORT40_..., i.e. 40 bit encryption, when negotiating an SSL
session. I wrote a program which performs a brute-force attack on RC4 with a
40 bit key by searching every possible key. The aim of this program is to
demonstrate how fast a weak encrypted SSL session can be decrypted by using
standard off-the-shelf hardware, i.e. a standard PC with one CPU running
Win98 or Linux which one can buy for say 1000 Euro.
The question is: What key is used by the SSL cipher suite RC4_128_EXPORT40?
Is there a 40 bit key used, i.e. a five byte key, or is a 128 bit key used
(16 bytes) where 88 bits are set to zero or to an other value? If so, what
bits are set to what value to form the 128 bit key out of the 40 keybits?
If I started my program by using the wrong "key format" it would not
terminate.
Can anybody answer that question (those people familiar with the SSL
specification)?
Thanks, Tobias
------------------------------
From: Anton Stiglic <[EMAIL PROTECTED]>
Subject: Re: help: why q|(p-1)
Date: Wed, 15 Dec 1999 10:35:31 -0500
Arrianto Mukti Wibowo 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).
>
> Does it has something to do with Pollard (p-1) ?
Yes it is. You might wan to look at the Handbood of Applied Cryptography,
section 3.2.3. which explains it well. Pollard(p-1) can find a prime factor p
of
n if p -1 is B-smooth for some small value of B.
For an integer to be B-smooth means that it's factors are all smaller or
equal to B. By picking a prime p such that p-1 has at least one large
factor, we prevent Pollard(p-1) attacks, we ant n to have factors such
as p. Also look at the defintion of a strong prime, this is essentialy what
you want.
Anton
------------------------------
From: John Myre <[EMAIL PROTECTED]>
Subject: Re: Non-linear PRNGs
Date: Wed, 15 Dec 1999 08:45:38 -0700
David Wagner wrote:
> Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
<snip>0
> > 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).
<snip>
>
> 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,
Yeah - it doesn't feel comfortable recalling the old PRNG maxim,
"well, use the high bits, they're much better". Can't we reduce
mod 3, or anything, just as well?
> 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.
I'm not convinced that the bootstrapping to more bits would work
so straightforwardly. Doesn't the same observation about low bits
not depending on high bits hold for linear systems? AFAIK, those
are not solved in this stepwise way. And even reducing mod 4 leaves
f(x) = a_0 + a_1*x + a_2*x^(2) + a_3*x^(3).
>
> 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.
Too much handwaving for me, at least. Remember the old joke about
the math professor? He is writing equations on the board during the
lecture, and at one point says, "and then it is obvious that...".
He stops, thinks, and leaves the room for a few minutes. When he
comes back, he says, "yes, I was right, it is obvious."
John M.
------------------------------
From: Matthew Montchalin <[EMAIL PROTECTED]>
Crossposted-To: sci.math
Subject: Prime series instead (Re: Pi)
Date: Wed, 15 Dec 1999 07:49:57 -0800
On 15 Dec 1999, Seraph-sama wrote:
| hamish wrote:
| >How do they work out Pi to so many d.p?
|
| For Pi there are a number of formulas you can use to get any number of digits.
| That these formulas work is proven in advanced mathematics. For example, such a
| formula is
|
| Pi = 4(1 - 1/3 + 1/5 - 1/7 + 1/9 - 1/11 + ...)
Is there any practical value to the number derived from using primes
instead of odds in that formula? E.g.,
N = 4(1 - 1/3 + 1/5 - 1/7 + 1/11 - 1/13 + 1/17 ... )
Probably a lot of people have looked into this, and I was wondering what
they came up with. Does the binary progression of bits 'look' random?
How well does the resulting number compare to pi as a pseudo-random
number?
------------------------------
From: [EMAIL PROTECTED]=NOSPAM (Arturo)
Subject: Re: SSL/RC4_128_EXPORT40
Date: Wed, 15 Dec 1999 15:45:58 GMT
On Wed, 15 Dec 1999 16:38:55 +0100, "Tobias Martin"
<[EMAIL PROTECTED]> wrote:
>Dear all,
>
>I have a question about SSL. Export versions of U.S. browsers (e.g. german
>versions of Netscape and MSIE) normaly use the SSL cipher suite
>..._RC4_128_EXPORT40_..., i.e. 40 bit encryption, when negotiating an SSL
>session. I wrote a program which performs a brute-force attack on RC4 with a
>40 bit key by searching every possible key.
Would you make that program available on request? Not that I
want to blow anybody�s protectio, just for curiosity�s sake (like
Bruce�s RC2-buster-screensaver).
------------------------------
From: James Felling <[EMAIL PROTECTED]>
Subject: Re: Better encryption? PGP or Blowfish?
Date: Wed, 15 Dec 1999 10:00:28 -0600
molypoly wrote:
> Ok, I'm a 'newbie' and am trying to understand this. With a "zero
> information system" such as PGP, one can easily read the encrypted
> file.
> If you are using PcCrypto, where the passphrase is not stored
> ANYWHERE, then one cannot read the encrypted file. Am I getting this?
> Thanks in advance.
I think that is what they are saying, but I think that they are wrong.
<Snip argument>
------------------------------
From: Paul Koning <[EMAIL PROTECTED]>
Subject: Re: Why no 3des for AES candidacy
Date: Wed, 15 Dec 1999 10:58:02 -0500
Eric Lee Green wrote:
> ...
> Today's enterprise-class tape drives can handle streams of up to 40 megabytes
> per seconds. The servers that feed these beasts may have multiple gigabit
> Ethernet cards so that they can suck down enough data to keep the pipe full. I
> looked at encrypting those streams with 3DES, since 3DES is a nice proven
> algorithm, but it was just TOO BLOODY SLOW.
Actually, in silicon 3DES isn't too bad. You can already get
commercial chips that can do it at several hundred megabits
per second. So one, or at most two, of those will match the tape
drive data rate you mentioned. And if you do an ASIC
where you just lay 3 DES blocks end to end, you can do 3DES
at the same speed as single DES (if you don't mind doing
interleaved CBC to keep the pipeline full).
When done in software, 3DES is quite painful.
paul
------------------------------
From: [EMAIL PROTECTED] (John Bailey)
Crossposted-To: comp.theory
Subject: Re: discrete logorithm reduction to factoring
Date: Wed, 15 Dec 1999 16:03:01 GMT
On Wed, 15 Dec 1999 03:56:18 GMT, [EMAIL PROTECTED] wrote:
>
>
>After reviewing some older threads about discrete log
>and factoring I had come across a few that discussed
>the ability to factor using discrete log.
>
>It is my understanding from these discussions that
>if there was a solution for discrete log, with say
>a worst case asymtote that was cubic, that then factoring
>would be polynomial as well.
Its important to distinguish the enviroment an algorithm is supposed
to work in. The claim for polynomial time computation of discrete
logs and large number factoring is sometimes based on application of
Shor's algorithms which assume execution on a (not yet existent)
Quantum Computer
Quoting Shor himself regarding times in classical computing
environment, from: quant- ph/ 9508027 (Los Alamos national archive)
The fastest algorithm known for finding discrete logarithms modulo
arbitrary primes p is Gordon's adaptation of the number field sieve
(D. M. Gordon (1993), Discrete logarithms in GF(p) using the number
field sieve, SIAM J. Discrete Math., 6, pp. 124{139.,) which runs in
time exp(O(log p) 1=3 (log logp) 2=3 )).
In the earlier paper (for which I have only a hard copy) Shor mentions
log inversion for smooth numbers in Polynomial Time, as a special
exception. That reference no longer appears in later versions of his
classic paper.
------------------------------
** 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
******************************
