Cryptography-Digest Digest #421, Volume #9 Mon, 19 Apr 99 09:13:06 EDT
Contents:
Re: Extreme lossy text compression (Terry Ritter)
Re: How Much Randomness?? (Gurripato (x=nospam))
Re: Charles Booher is a complete IDIOT! (Gurripato (x=nospam))
SNAKE#4 is oil (no surprise there :-) wot about #5?? (Peter Gunn)
Re: PGP 6 Is garbage (Matthew Skala)
Re: Adequacy of FIPS-140 (Alan Braggins)
Re: AES Competition (Bob Deblier)
Re: Not a PGP Expert (Matthew Skala)
Re: Extreme lossy text compression (D. J. Bernstein)
Prime numbers generator ([EMAIL PROTECTED])
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (Terry Ritter)
Subject: Re: Extreme lossy text compression
Date: Mon, 19 Apr 1999 07:00:09 GMT
On 18 Apr 1999 08:27:02 GMT, in
<[EMAIL PROTECTED]>, in sci.crypt
[EMAIL PROTECTED] (D. J. Bernstein) wrote:
>Terry Ritter <[EMAIL PROTECTED]> wrote:
>> For production use, CRC's are table-driven.
>
>Indeed. The standard CRC-32 implementation reduces an n-bit polynomial
>modulo a degree-32 polynomial p using
>
> * n/8 additions of 32-bit polynomials,
Yes, this is the add of the table value.
> * n/8 multiplications of 24-bit polynomials by x^8, and
Note that this is just a single shift, and not a bit-by-bit
multiplication, as one might think from the comment below.
> * n/8 table lookups of f |-> (x^32 f) mod p, where f has 8 bits.
>[...]
>> "Division" mod an
>> irreducible mod 2 poly is just a test and conditional exclusive-OR,
>> which is, again, well supported.
>
>I said ``support for fast multiplication.'' Note the word ``fast.''
>Bit-by-bit multiplication, doing a conditional 128-bit addition for each
>bit of input, is not fast.
The only multiplication we have in CRC is a shift, but I expect an
integer multiply may be just as fast, in the registers. Outside the
registers, it looks like a multiple-precision operation, and 128 bits
sounds outside the registers. But my comment was made in the context
of the equations you showed:
>>> * reduce (Z/2)[x] modulo some prime x^128-... (CRC/``division'');
>>> * reduce Z modulo some prime 2^128-... (basically Karp-Rabin);
>>> * reduce F_(2^32)[x] modulo some prime x^4-... (Shoup);
>>> * reduce (Z/(2^31-1))[x] modulo some prime x^4-...;
>>> * reduce F_(2^128)[x] modulo some prime x-... (``evaluation'');
>>> * reduce (Z/(2^127-1))[x] modulo some prime x-... (hash127);
>>> * etc.
Everywhere here I see "modulo some prime." Now, that is hardly an
issue with CRC, but it sure can be an issue when dividing big integers
which here seem to be 128 bits. How do you deal with this?
>> So I would instead probably use 4
>> CRC's using different deg-32 primitives
>
>That's a very bad idea for authentication of long messages.
You're right.
>The maximum
>collision probability is around b^4/2^128 where b is the message length.
>Anyway, hash127 is much faster.
I still find this hard to believe. What happened to the
multi-precision divide?
---
Terry Ritter [EMAIL PROTECTED] http://www.io.com/~ritter/
Crypto Glossary http://www.io.com/~ritter/GLOSSARY.HTM
------------------------------
From: [EMAIL PROTECTED] (Gurripato (x=nospam))
Subject: Re: How Much Randomness??
Date: Mon, 19 Apr 1999 07:56:33 GMT
On Sun, 18 Apr 1999 21:26:55 -0700, "Charles Booher"
<[EMAIL PROTECTED]> wrote:
>How much randomness can be generated by clicked a computer key board four
>times?
>
>This is all it take to make a PGP key these days.
>
>Assuming you did this sometime in the last five years.
>
>101*101*101*101*1000*1000*1000*1000*60*60*24*365*1000
>
>=
>
>3281648805936000000000000000
>
>This would be a "Pretty Good" Key set. It still sucks, but it could get he
>job done.
That�s who PGP and other crypto programs use symmetric
encryption to cryptographycally "laundering" the random number
generator used, among other things, to create session keys. You do
hate to RTFM, don�t you?
>
>NAI sells sniffers to the NSA and FBI on a monthly basis.
How stupid from the FBI if they cannot make their own or use
one of the may sniffers roaming the Internet for free.
>Who do you think is paying the rent on the NAI red granite building if not
>Uncle Sam?
Maybe its earnings by selling software all over the world?
OK, it is a stupid answer, but who knows? Maybe NAI is selling
software in order to get money.
>Most people really don't look at the source code. If you have not
>personally looked at the source code I would NOT Trust my version of PGP.
Neither I look at the bus� engine but I use it anyway.
>It turns out the 2.6.2 version is also weak, but that is another story.
Don�t restrain yourself, I�ll love to hear it.
>Have you build your own version of PGP and looked at the source code for the
>random number generators closely?
Not this morning.
>If you have claimed to do this why should I trust you?
You don�t have to.
>People who trust PGP to be anything but "Pretty Good" are "Pretty Stupid
>People".
>
Coming from a person expressing himself from highly
substantiated and documented arguments, I�d rather take it as a
compliment.
------------------------------
From: [EMAIL PROTECTED] (Gurripato (x=nospam))
Subject: Re: Charles Booher is a complete IDIOT!
Date: Mon, 19 Apr 1999 07:50:13 GMT
On Sun, 18 Apr 1999 20:50:17 -0700, "Charles Booher"
<[EMAIL PROTECTED]> wrote:
>2000 Bit RSA with 168 bit symmetrical key transfer.
>
>P=11000696584989782544522619519913345124103231827575294339831181831725641326
>9078973365623589611193133131150098320982854342794549752349538621945655782352
>5076150294629891824228709867162991475077878389562841705590408935980850465894
>7009167798211554559031441201522614106107929095335547129793205216309949623
>
>Q=30249286728109405918590843071853357150479761190112573551181244804061530656
>7966488103515162846533700357315076546570614128626206647972523084036618161838
>1081715275206633689896102157200163506921943801470207574279413387359661286495
>117810101213945454757846133429836843058356967076365829299427856500883323
>
>N=P*Q=3327632252082898944546541012822144541462475018706396123819083253300756
>7014847067220457448959939512476725255788527394231781052398973437595519950639
>8248122262094013778324148397168678724428921406254140612371444804286834073668
>4114595040880345342787357220368926278547573410233564559472193952385307822017
>4259620030633074929577228678910849061091323554120496169531706398842320105510
>4533159887127587558132853664054796036043635729438672759207032229219091684277
>2196831514733819219148009546706141111914874049773018744737591999946559988270
>2561751814120820668977924537373095412692872590269845649159653130837229
>
>E=82317409759329182426842293264790168238591355369493268706801860918260171791
>8883814103497175172565599218595954875336834408124733188918705702018668860346
>6473457386387378338437897014818038891406959645563680271770904434133734544774
>7544824406940941002746152154956183747942618930038144511578375279779164644494
>978894252889762924768717093
>
>D=17704301246333665791443976907444203476519991937894913567621161627644358962
>7902777207470003407586451535505777756211264080365061166370086980119893800331
>8728906867973066366926276027606987059382784144048563884991988005112954409466
>4327943190324059477412657387012009145465111616323208022181380832352086000345
>7240976165025980756011144303523986081381464042498888927577917909293065048391
>8658360543809429083466411821041536580694560010080805726843532025739677189074
>3162495155755113880845516099305985286118094673166897075391670513066439904834
>987555041463273613141555386097427562373484848253729547505318565957
>
>Please check that
>
>(E*D)%((P-1)*(Q-1)) = 1
>
>M= (Padding + Symmetrical Key)
>9423796559209306750809270970748906292229816325807394395551683890889638675904
>9441588044408523985965918388427686757918680778969256501782765339624605362901
>3880883521465982209605236939365121870950506541940578893268878660397607434983
>3631845277738896241316207441352867059138468286262722069638818555476817326346
>3454654972967994224957041916570635754398142907306889285029687212737360015329
>8696724042193041919819433600244622314574716679621038403185995969228753361729
>3862936381456559926676802998544879424582072983764354382907621147360623286810
>45731847512107578921280002780055040573213301468509921361964347
>
>C=M^E%N=
>2732955010960213642757351044842014499680388248644971310193009335625645690187
>6674573758411495135868591899621034794073113347095445446255384287959172165458
>4290221680975823597078849458997156807419607335232074252432062560418924295304
>5621347273644854486177114599767993010054731228715142943565345845631545346826
>2722881592592312509284213776460805745875346230549694137534019483954426211302
>6651188675726013298128501546075630764276400127231281212377487056690271313858
>3652624633182255439031475477003219828311709388088034194688515203850563559118
>7411734184850564932364867419952843926508180878657510666627914049
>
>Symetrical Key (Lower 168 bits of M) =
>0ee1 76fa 5193 2db0 e111 6c07 e23b a579 79f5 3aad 3b
>
>The Clipboard format for the key
>
>{7146AE61-F434-11D2-8883-DEA6C5F6B936};rsa2000test;3327632252082898944546541
>0128221445414624750187063961238190832533007567014847067220457448959939512476
>7252557885273942317810523989734375955199506398248122262094013778324148397168
>6787244289214062541406123714448042868340736684114595040880345342787357220368
>9262785475734102335645594721939523853078220174259620030633074929577228678910
>8490610913235541204961695317063988423201055104533159887127587558132853664054
>7960360436357294386727592070322292190916842772196831514733819219148009546706
>1411119148740497730187447375919999465599882702561751814120820668977924537373
>095412692872590269845649159653130837229;823174097593291824268422932647901682
>3859135536949326870680186091826017179188838141034971751725655992185959548753
>3683440812473318891870570201866886034664734573863873783384378970148180388914
>0695964556368027177090443413373454477475448244069409410027461521549561837479
>42618930038144511578375279779164644494978894252889762924768717093;
>
>
>
And this proves what, please?
------------------------------
From: Peter Gunn <[EMAIL PROTECTED]>
Subject: SNAKE#4 is oil (no surprise there :-) wot about #5??
Date: Tue, 13 Apr 1999 12:25:09 +0100
"Roll up, Roll up, come and try the new miracle elixer..."
Thanks to Bryan & Thomas for pointing out that key=H(P,<DH private>)
is easily cracked when <DH private> is known and P is short.
I order to stop a man-in-the-middle calculating <DH private>
I would have to munge the <DH public>s with P... which
basically leads to EKE and friends.
But, no point in giving up now, and since encrypting the public
values is out, I need to look at authenticating both sides...
Attempt#5... All comments welcome :-)
PG.
=======================================================
SNAKE#5 => Some Numpty Attempt at Key Exchange
x1 is a random number (<p-1)
x2 is a random number (<p-1)
g is an agreed 'generator' (<p-1)
A is the Client.
B is the Server.
H() is a one way crypto hash function (SHA or similar)
p a fixed large safe prime
key is the resulting shared key
U is the userid (short, probably <=8 chars)
P is the user's password (short, probably <=8 chars)
[ NOTE: ^ means to-the-power-of, % means mod ]
1) A->B: y1=(g^x1)%p, U, z1=(g^H(P,x1))%p
2) B: z2=(g^H(P,x2))%p, key=H((y1^x2)%p)
3) B->A: y2=(g^x2)%p, z2
4) A: key=H((y2^x1)%p)
What happens is...
1) Client sends to Server his DH public value y1,
his user identifier U, and z1=(g^H(P,x1))%p
2) Server looks up user list using U to find password P,
to work out z2=(g^H(P,x2))%p, disconnecting the client
if (z1^H(P,x2))%p != z2.
3) Otherwise, he returns his DH Public value along
with z2, and works out the DH secret value.
4) Client disconnects if (z2^H(P,x1))%p != z1, otherwise
works out the DH secret value.
------------------------------
From: [EMAIL PROTECTED] (Matthew Skala)
Subject: Re: PGP 6 Is garbage
Date: 18 Apr 1999 19:59:19 -0700
In article <7f0sqg$[EMAIL PROTECTED]>,
Charles Booher <[EMAIL PROTECTED]> wrote:
>PGP 6 will only generate around 1,000,000,000 possible key pairs.
That's a rather incredible statement. Can you support it?
--
Matthew Skala Ansuz BBS (250) 472-3169 http://www.islandnet.com/~mskala/
GOD HATES SPAM
------------------------------
From: Alan Braggins <[EMAIL PROTECTED]>
Subject: Re: Adequacy of FIPS-140
Date: 19 Apr 1999 10:41:21 +0100
"Douglas A. Gwyn" <[EMAIL PROTECTED]> writes:
> The real problem with your suggestion is that few people know
> all relevant attacks that your system might be exposed to.
> (Except the enemy, who isn't going to help you analyze your
> system.)
And even if he did help you at design time, it wouldn't stop him
trying to develop new attacks in the future.
------------------------------
From: Bob Deblier <[EMAIL PROTECTED]>
Subject: Re: AES Competition
Date: Mon, 19 Apr 1999 11:48:10 +0200
"A [Temporary] Dog" wrote:
> On Sat, 17 Apr 1999 22:13:05 +0100, "Michael Scott" <[EMAIL PROTECTED]>
> wrote:
> >
> >I must say Rijndael is looking good, given that its completely patent free,
> >scales nicely to various architectures, and can also be used as a one-way
> >hash. Its only problem seems to be its awful name.
> >
> How do you pronounce that anyway? I've been (mentally) calling it
> "Rinj N Dall" (three syllables, like Toys R Us).
It's dutch, which is confusing to most english speakers. The 'ij' is a long
vowel, not a vowel and a consonant. The closest equivalent phonetically I can
come up with is reign-dahl.
Bob Deblier
------------------------------
From: [EMAIL PROTECTED] (Matthew Skala)
Subject: Re: Not a PGP Expert
Date: 18 Apr 1999 19:57:04 -0700
In article <[EMAIL PROTECTED]>,
Anthony Stephen Szopa <[EMAIL PROTECTED]> wrote:
>Now suppose the NSA has this person's Internet line bugged. The NSA
>also has the public key. Can the encrypted messages from these 1,000
>users of this public key have their messages decrypted by the NSA (or
>anyone else, for that matter) since they have the public key and the PGP
>software, too?
No. Please stop spreading FUD.
If NSA could break a key by examining 1000 messages encrypted to that key,
then they wouldn't need to obtain those messages by interception - they
could just encrypt 1000 messages to the public key *themselves* and then
use those to break the key. I imagine that you know that, and you were
hoping to use it as part of a "proof" that NSA can break PGP. I imagine
you must have a lot of spare time on your hands.
--
Matthew Skala Ansuz BBS (250) 472-3169 http://www.islandnet.com/~mskala/
GOD HATES SPAM
------------------------------
From: [EMAIL PROTECTED] (D. J. Bernstein)
Subject: Re: Extreme lossy text compression
Date: 19 Apr 1999 08:38:36 GMT
Terry Ritter <[EMAIL PROTECTED]> wrote:
> I still find this hard to believe.
That's why they pay me the big bucks. :-)
Get the code from http://pobox.com/~djb/hash127.html and try it for
yourself. On a Pentium it takes about 4.5 clock cycles per input byte.
---Dan
------------------------------
From: [EMAIL PROTECTED]
Subject: Prime numbers generator
Date: Mon, 19 Apr 1999 08:51:45 GMT
Hello all,
Using this program you can generate all
prime numbers in the diapason from 2 to
0FFFFFFFFh. The program runs ca. 10 hours.
The output file 'prime.hex' has the length
ca. 694 Mb. The record's length is 4 bytes
(dword-Assembler, integer- Delphi).
Please be aware that 4 bytes in memory
are dword type. You can get a correct presentation
after loading dword in register or using correct
integer type. You can split the output file
using your own routine. The file can be 30 %
compressed.
To download the executable and Delphi 4
source code (ZIP 161 Kb) please go in
the download area at
www.online.de/home/aernst
Link : Prime numbers generator
Known problem.
The executable file is compiled under Windows NT.
Would you start it under Windows 95/98 you should
resize the dialog window. To avoid this the source
should be recompiled.
Regards
Alex
============= Posted via Deja News, The Discussion Network ============
http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own
------------------------------
** 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
******************************
