Cryptography-Digest Digest #835, Volume #9 Tue, 6 Jul 99 13:13:03 EDT
Contents:
Re: RSA Padding (S.T.L.)
A junior Kryptos? ("Douglas A. Gwyn")
Weak padding ? in message signature (Francois Grieu)
Shamir´s no-key protocol (Georg Zetzsche)
Re: Can Anyone Crack The Zip Password In (Georg Zetzsche)
Keeping File Formats Safe (Ronald Klazar)
Re: I need help seeking cryptography-related employment (fungus)
Re: DES-NULL attack (fungus)
Re: Summary of 2 threads on legal ways of exporting strong crypto (Mok-Kong Shen)
Re: Summary of 2 threads on legal ways of exporting strong crypto (Mok-Kong Shen)
Kryptos is cracked ("collomb")
Re: Help!! Looking for a modular exponentiation algorithm. (Thierry Moreau)
Re: DES-NULL attack (Patrick Juola)
Re: The Constrained One-Time Pad and the Cryptanalyst's Lucky Day
([EMAIL PROTECTED])
Re: RSA Padding ([EMAIL PROTECTED])
Re: Why this simmetric algorithm is not good? ([EMAIL PROTECTED])
Re: I need help seeking cryptography-related employment (Keith A Monahan)
Re: Standard Hash usage (John Myre)
Re: Weak padding ? in message signature (Jean-Jacques Quisquater)
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (S.T.L.)
Subject: Re: RSA Padding
Date: 06 Jul 1999 04:41:51 GMT
<<Well you said having 3-digit msgs... that's why I said freq analysis
would work.>>
I think that I also mentioned that I concatenate the digits before RSA
encryption.
Moo-Cow-ID: 33 Moo-Cow-Message: Most
-*---*-------
S.T.L. ===> [EMAIL PROTECTED] <=== BLOCK RELEASED! 2^6972593 - 1 is PRIME!
Quotations: http://quote.cjb.net Main website: http://137.tsx.org MOO!
"Xihribz! Peymwsiz xihribz! Qssetv cse bqy qiftrz!" e^(i*Pi)+1=0 F00FC7C8
E-mail block is gone. It will return if I'm bombed again. I don't care, it's
an easy fix. Address is correct as is. The courtesy of giving correct E-mail
addresses makes up for having to delete junk which gets through anyway. Join
the Great Internet Mersenne Prime Search at http://entropia.com/ips/ Now my
.sig is shorter and contains 3379 bits of entropy up to the next line's end:
-*---*-------
Card-holding member of the Dark Legion of Cantorians, the Holy Order of the
Catenary, the Great SRian Conspiracy, the Triple-Sigma Club, the Union of
Quantum Mechanics, the Polycarbonate Syndicate, the Roll-Your-Own Crypto
Alliance, and People for the Ethical Treatment of Digital Tierran Organisms
Avid watcher of "World's Most Terrifying Causality Violations", "When Kaons
Decay: World's Most Amazing CP Symmetry Breaking Caught On [Magnetic] Tape",
"World's Scariest Warp Accidents", "World's Most Energetic Cosmic Rays", and
"When Tidal Forces Attack: Caught on Tape"
Patiently awaiting the launch of Gravity Probe B and the discovery of M39
Physics Commandment #11: The Strong Force Is Carried By Gluons.
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: A junior Kryptos?
Date: Tue, 06 Jul 1999 07:54:25 GMT
I stumbled across the following article:
http://www.news-observer.com/daily/1997/06/03/nc06.html
which says that the Kryptos sculptor has created another cipher puzzle,
at UNC Charlotte, entitled "The Cyrillic Projector".
------------------------------
From: [EMAIL PROTECTED] (Francois Grieu)
Subject: Weak padding ? in message signature
Date: Tue, 06 Jul 1999 10:25:28 +0200
In light of recent almost-sucessfull theoretical attacks against
carefully designed padding scheme like ISO/IEC 9796-1 and -2 (refer to
<http://www.rsa.com/rsalabs/html/sigforge_qa.html> for details),
I wonder if the following simple signature scheme could be attacked
due to it's overly simplistic padding.
Using the public exponent E=3, an authority chooses and publishes
an RSA public key N with 0 < N-2^n < 2^(3*n/4), n even (say n=512),
and keeps the secret exponent D.
The authority chooses m messages Mi with 2^(n/4) <= Mi < 2^(n/2)
and publishes the signatures obtained by
Si := ( Mi * (1+2^(n/2)) )^D mod N
[note: multiplying by 1+2^(n/2) simply duplicates the message]
The verifier receiving a signature S computes S^3 mod N and checks
it is of the form M * (1+2^(n/2)) with 2^(n/4) < M < 2^(n/2) ;
in this case the recovered message M is accepted.
The attacker has no way to influence the choice of messages, but the
authority choose messages in a non-random, mostly incremental way.
As an oversimplification we may assume Mi = M0 + i*2^k
for some k<n, maybe k=0.
Can a valid signature be forged with less effort than factoring N ?
Francois Grieu
------------------------------
From: Georg Zetzsche <[EMAIL PROTECTED]>
Subject: Shamir´s no-key protocol
Date: Tue, 06 Jul 1999 12:44:19 +0200
Hi all!
Can ynobody tell me how you get the number a´(the key that is used
to decrypt the second message)
from a (the secret key from the first message) in shamir´s no-key protocol ?
______________________________________
Georg Zetzsche ([EMAIL PROTECTED])
------------------------------
From: Georg Zetzsche <[EMAIL PROTECTED]>
Subject: Re: Can Anyone Crack The Zip Password In
Date: Tue, 06 Jul 1999 12:37:07 +0200
Download zipcrack.zip from ftp.aanet.ru/pub/dos/
This program will do for you what you want it to do.
The BusMan wrote:
> The file EntryPro.Zip? "EntryPro 2.06" Look I won't bullshit
> you I'm very new to this! I've been tyring to break this thing
> for 41 days, with some luck, I found out that if I put "%l%"
> for a password it will start to decommpress but mid way I
> get an "BAD CRC" error, and it either unloads 1/4 the file
> size or "0" the file size. This is as far as I can go with
> what little Skills I have... Please If there is someone out
> there who can help me solve this... You will have FRIEND for
> LIFE!!! Thank-You for hearing me out!
> The BusMan
> 05July1999
> 12:25 a.m.
>
> Sent via Deja.com http://www.deja.com/
> Share what you know. Learn what you don't.
--
______________________________________
Georg Zetzsche
------------------------------
From: Ronald Klazar <[EMAIL PROTECTED]>
Subject: Keeping File Formats Safe
Date: Tue, 06 Jul 1999 13:06:36 +0200
Hello,
I would like to prevent other people from discovering the format of the
data files for my application. Is there a sound method for implementing
a system such as this when both the application and data file are stored
locally?
Hard coding an encryption key in the application is not feasible because
reverse engineering presents a way to uncover the key.
Compressing the data file provides too little protection.
Does there, then, exist a method that would at least prove a challenge
for anyone wanting to know the format?
Any help would be greatly appreciated.
Ronald Klazar..
------------------------------
From: fungus <[EMAIL PROTECTED]>
Subject: Re: I need help seeking cryptography-related employment
Date: Tue, 06 Jul 1999 13:54:20 +0200
"S.T.L." wrote:
>
> <<Would someone please respond with a link to the fastest algorithm for
> factoring numbers on the order of less than 2^64? The algorithm should
> be suitable for programming on a machine with a m68000 processor w/512KB
> memory.>>
>
> Let me guess. A TI-92+. I'm right, aren't I? The memory you stated
> would make it a TI-92+. Or a TI-89. Their processors run at 10Mhz!
> Anything you try will be blazingly slow. :-D
>
Or an Atari ST...
--
<\___/>
/ O O \
\_____/ FTB.
------------------------------
From: fungus <[EMAIL PROTECTED]>
Subject: Re: DES-NULL attack
Date: Tue, 06 Jul 1999 13:53:22 +0200
"S.T.L." wrote:
>
> This is a semi-off-topic post. Just be glad I'm not David A. Scott.
>
> <<billion Gigabytes>>
>
> Why not say the real word? People work with gigabytes all the time,
> so a billion doesn't seem like that much. However, one Terabyte seems
> humongous.
I know people who own several files which occupy a couple of terabytes
(each file!)
--
<\___/>
/ O O \
\_____/ FTB.
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Crossposted-To: talk.politics.crypto
Subject: Re: Summary of 2 threads on legal ways of exporting strong crypto
Date: Tue, 06 Jul 1999 12:29:36 +0200
Isaac wrote:
>
> What you hope to accomplish in your transform appears to be
> hiding illegal activity rather than accomplishing a legal
> transaction. I find speculation on whether you'll get caught
> uninteresting.
I said that there is NO hiding. Everyone knows that (in all likelihood)
lower case means 0 and upper case means 1. It is an attempt to
'openly' confront the bureaucrats, who have to offer anyway reasons
as to why apparently arbitrarily using lower and upper case to write
English text is against laws. (Some perphaps not irrelevant analogy:
If one writes an ordinary sentence and somebody can 'construct' a
certain key and a certain algorithm to transform that to another
sentence that is a message about some illegal activity, does that
necessarily mean that one has transmitted a ciphertext of that
secrect message? I believe that such possibilities of 'bogous'
interpretations are abundant.)
>
> I sincerely hope no one follows any advice from your 'summary'. It
> doesn't appear to reflect anything I've seen posted in this newsgroup.
You have discussed the second scheme, but not the first. The first
is certainly o.k. and also convenient, provided one can obtain
assistance from a foreign server. On another internet list there
has already been one person outside US who voluntarily offers
possibilities of storing the relevant stuffs on his server. This
clearly shows that web publication of strong crypto, which is at the
heart of the Bernstein case, is practical today.
M. K. Shen
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Crossposted-To: talk.politics.crypto
Subject: Re: Summary of 2 threads on legal ways of exporting strong crypto
Date: Tue, 06 Jul 1999 12:36:52 +0200
[EMAIL PROTECTED] wrote:
>
> I believe you have missed my point. Of course it is English text, and
> there are no laws against exporting English text. But it is _also_ a
> machine-readable form of strong crypto source code, and there are laws
> against exporting such.
Perhaps I might refer to my answer to a post by Issac.
>
> If there were laws against exporting English text, and no laws against
> exporting machine-readable souce code for strong crypto would you still
> maintain it was exportable because one form of interpretation was not
> prohibited?
>From logic one knows that from falsity anything can follow. Since the
above premise is fundamentally false, I am unable to answer your
question.
M. K. Shen
------------------------------
From: "collomb" <[EMAIL PROTECTED]>
Subject: Kryptos is cracked
Date: 6 Jul 1999 11:40:02 GMT
Hello
Message Numero 1
Glimpses into the decyphering of Krystos
While decyphering, the whole sculpture proceeded, before me, like a
crypted movie which would follow the episodes of end-time, evoked in the
Revelation to John in chapter 20, verses 7, 8 and 9:
< 7 – When the thausend years are ended, Satan will be released from his
prison,
8 - and will come out to deceive the nations at the four corners of the
earth, Gog and Magog, in order to gather them for the battle ; they are as
numerous as the sands of the sea.
9 - They marched up over the breadth of the earth and surrounded the camp
of the saints and the beloved city (Jerusalem). And fire came down from
heaven ( from God obviously) and consumed them.>
One drawing laid out in the form of the word : <GOD> disposed diagonally,
marks finally the intervention of God to save the Holy City, Jerusalem,
encircled by the armies of Gog and Magog.
The other letters of the puzzle compose some other expressive sketchings.
Will continue later.
See also at : http://calvaweb.calvacom.fr/collomb/
Best regards
Collomb-Chabrery
[EMAIL PROTECTED]
------------------------------
From: Thierry Moreau <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Subject: Re: Help!! Looking for a modular exponentiation algorithm.
Date: Tue, 06 Jul 1999 07:12:13 -0400
Keith Reeves wrote:
>
> I'd really appreciate if someone could help me out! I'm looking for a
> modular exponentiation algorithm, one that can be used with RSA. Could
> anyone point me in the right direction? If anyone knows where I can
> find one of these on the web, explained in semi-layman terms, it would
> be a big help.
Try http://www.connotech.com/MONTGOM.HTM
------------------------------
From: [EMAIL PROTECTED] (Patrick Juola)
Subject: Re: DES-NULL attack
Date: 6 Jul 1999 08:49:37 -0400
In article <7lrfnl$313$[EMAIL PROTECTED]>,
Xcott Craver <[EMAIL PROTECTED]> wrote:
>>What *are* you talking about?
>
> Alex is notorious for these kinds of attacks, apparently
> unaware that they amount to nothing more than brute-force.
A very selective and intelligent kind of brute force, however....
> In this case, he seems to be saying the same for DES, that one
> can just build a table of every possible encryption of a null
> string --- only about a billion Gigabytes for 56-bit DES ---
> and use this as a huge lookup table.
>
> One problem with this attack is that there is no way to tell
> if a block is an encryption of a null or something else.
> With a message of 2,000 blocks, Alex will have to look up
> 2,000 entries. Chances are 1 in 10 quadrillion that one
> of them will be a null. 1 in 10000000000000000 times, his
> room full of Gigabyte drives will be useful.
Except that NULL blocks are rather common in some sorts of files; if
what he's looking for are executable files, for intstance, those tend
to have lots of zero blocks lying around. Similarly, if I wanted to
find English text, the string " in the " is exactly sixty-four bits
in length (i.e. one DES block) and occurs with much greater frequency
than 1 in 10 quadrilliion.
-kitten
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: The Constrained One-Time Pad and the Cryptanalyst's Lucky Day
Date: Tue, 06 Jul 1999 12:34:56 GMT
In article <[EMAIL PROTECTED]>,
[EMAIL PROTECTED] (S.T.L.) wrote:
> Anyone can guess at plaintexts, with nothing to go on but thin air.
This is not
> a problem. Properly working OTPs *never*, *ever* leak information,
period. No
> clarification needed.
In theory the OTP is truly the only secure method. If the key is truly
random then the ciphertext will be random. The practical problem is
when the key stream is predicable or detectable, say all zeroes or all
0x80 ... It's possible to have a random stream of never ending zeroes
because who says that is not random?
That's the argument. However if the zeroes are all truly random then
the ciphertext is truly random period. No matter what the key stream
was. You could get better 'guesses' though from that form of weak key
stream...
Tom
--
PGP key is at:
'http://mypage.goplay.com/tomstdenis/key.pgp'.
Sent via Deja.com http://www.deja.com/
Share what you know. Learn what you don't.
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: RSA Padding
Date: Tue, 06 Jul 1999 12:31:58 GMT
In article <[EMAIL PROTECTED]>,
[EMAIL PROTECTED] (S.T.L.) wrote:
> <<Well you said having 3-digit msgs... that's why I said freq analysis
> would work.>>
>
> I think that I also mentioned that I concatenate the digits before RSA
> encryption.
Well that's just super. BTW drop the huge sig dude they are annoying.
Tom
--
PGP key is at:
'http://mypage.goplay.com/tomstdenis/key.pgp'.
Sent via Deja.com http://www.deja.com/
Share what you know. Learn what you don't.
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Why this simmetric algorithm is not good?
Date: Tue, 06 Jul 1999 12:30:34 GMT
In article <[EMAIL PROTECTED]>,
fungus <[EMAIL PROTECTED]> wrote:
> procedure cipher(Key : uint128 ; plain: file ; cipher : file)
> begin
> setRandomSeed(Key);
> while not EOF(plain)
> begin
> p := getNext128bits(plain) xor Random(0..2^128-1)
> writeNext128bits(cipher, p)
> end
> end
Not to be picky but the procedure name should not be the same as any
paramaters or locals. It makes it clearer and avoids compiler errors.
Also the line could have read
-=-
while not EOF(plain)
writeNext128Bits(cipher, getNext128bits(plain) xor Random(...));
-=-
Just a coding thing...
Tom
--
PGP key is at:
'http://mypage.goplay.com/tomstdenis/key.pgp'.
Sent via Deja.com http://www.deja.com/
Share what you know. Learn what you don't.
------------------------------
From: [EMAIL PROTECTED] (Keith A Monahan)
Subject: Re: I need help seeking cryptography-related employment
Date: 6 Jul 1999 13:47:15 GMT
Or a Commodore Amiga 500/1000.
Keith
fungus ([EMAIL PROTECTED]) wrote:
: "S.T.L." wrote:
: >
: > <<Would someone please respond with a link to the fastest algorithm for
: > factoring numbers on the order of less than 2^64? The algorithm should
: > be suitable for programming on a machine with a m68000 processor w/512KB
: > memory.>>
: >
: > Let me guess. A TI-92+. I'm right, aren't I? The memory you stated
: > would make it a TI-92+. Or a TI-89. Their processors run at 10Mhz!
: > Anything you try will be blazingly slow. :-D
: >
: Or an Atari ST...
: --
: <\___/>
: / O O \
: \_____/ FTB.
------------------------------
From: John Myre <[EMAIL PROTECTED]>
Subject: Re: Standard Hash usage
Date: Tue, 06 Jul 1999 09:18:30 -0600
David P Jablon wrote:
>
> That function, hash = sha1(P) || sha1(P || sha1(P)), limits the
> entropy to no more than 160-bits, when P has more than 160-bits
> of entropy.
I don't see why this is so.
Can you explain it, or point me at the right place to
read about it? Does it have anything to do with SHA in
particular, or the order of the appending, or is it a
general fact about hash functions?
Thanks -
John M.
------------------------------
From: Jean-Jacques Quisquater <[EMAIL PROTECTED]>
Subject: Re: Weak padding ? in message signature
Date: Tue, 06 Jul 1999 17:10:42 +0200
Francois Grieu wrote:
> In light of recent almost-sucessfull theoretical attacks against
> carefully designed padding scheme like ISO/IEC 9796-1 and -2 (refer to
> <http://www.rsa.com/rsalabs/html/sigforge_qa.html> for details),
> I wonder if the following simple signature scheme could be attacked
> due to it's overly simplistic padding.
> Using the public exponent E=3, an authority chooses and publishes
> an RSA public key N with 0 < N-2^n < 2^(3*n/4), n even (say n=512),
> and keeps the secret exponent D.
> The authority chooses m messages Mi with 2^(n/4) <= Mi < 2^(n/2)
> and publishes the signatures obtained by
> Si := ( Mi * (1+2^(n/2)) )^D mod N
> [note: multiplying by 1+2^(n/2) simply duplicates the message]
>
> The verifier receiving a signature S computes S^3 mod N and checks
> it is of the form M * (1+2^(n/2)) with 2^(n/4) < M < 2^(n/2) ;
> in this case the recovered message M is accepted.
>
> The attacker has no way to influence the choice of messages, but the
> authority choose messages in a non-random, mostly incremental way.
> As an oversimplification we may assume Mi = M0 + i*2^k
> for some k<n, maybe k=0.
>
>
> Can a valid signature be forged with less effort than factoring N ?
Here is a part of the answer, given in the context of this attack:
[I changed a little bit the notations for easier reading]
Scheme with messages of 128 bits:
================================
Let an RSA public modulus N of length 513 bits (to avoid any problem
related
to too large messages)
public exponent: 3
secret exponent: D
each given message Mi is transformed by the multiplication of some
number b
in the integers and then signed by the RSA function:
here b is F8 (the 8th Fermat number) well-known to be composite
(2 prime factors found in 1980 by Brent and Pollard: 123...7 * 9...321)
If we know the factorization of Mi, it is trivial to find the
factorization
of Mi*b. So ... we are in the context where we can use the
multiplicative
attack you refer (anyway).
Now suppose we intercept m messages Mi of length 128 bits:
we select the smooth messages amongst these Mi's:
a number of 128 bits has the probability 1/175,000 to have only prime
factors less than 1,000,000 (concept of smooth number)
(see Riesel, Prime numbers and computer ..., Birkhauser, 1985, p. 171
and also use some program by Jon Sorenson): it means a basis of about
50,000 prime factors. It means: if you intercept about
175,000 * 50.000 messages you are able to "sign" any smooth message of
(1) (2) 128 bits!
(1) 1 / (proba to be 1,000,000-smooth);
(2) number of factored smooth numbers we need.
So intercepting about 8 billions (random) messages means
nearly a full breaking (NB: these figures are approximate):
the only computations you need is factorization of these
messages by the prime numbers less than one million and
a Gaussian elimination for a matrix 50,000*50,000
(elements are modulo 3). It is definitively less than the
effort needed to factorize a number of 512 bits.
And then an attacker is able to simulate the signatures of
1 out of 175,000 possible messages. There are other possible
attacks (see the papers by JF Misarski for further refs).
To say that in another way:
suppose a TTP is signing a message for each people on the planet:
an attacker will be able to simulate the signatures of about
50.000 people.
Scheme 2 (other length of messages and incremental messages).
Another time.
So at ISO we tried to be better (in the 80's for the part 1, related to
the presented scheme).
Jean-Jacques Quisquater,
------------------------------
** 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
******************************
