Cryptography-Digest Digest #419, Volume #9 Mon, 19 Apr 99 00:13:03 EDT
Contents:
Re: Extreme lossy text compression (Terje Mathisen)
Re: Thought question: why do public ciphers use only simple ops like shift and XOR?
(John Savard)
Re: dumb question on releasing source code ([EMAIL PROTECTED])
Re: Comments on Boomerang Attack Sought (John Savard)
Re: True Randomness & The Law Of Large Numbers (R. Knauer)
Re: True Randomness & The Law Of Large Numbers (Dave Knapp)
Re: True Randomness & The Law Of Large Numbers (Herman Rubin)
Re: Extreme lossy text compression (D. J. Bernstein)
Re: Thought question: why do public ciphers use only simple ops like shift and XOR?
([EMAIL PROTECTED])
--- sci.crypt charter: read before you post (weekly notice) (D. J. Bernstein)
Re: FSE-6 Report: Slide Attack (David Wagner)
Re: dumb question on releasing source code (Geoff Thorpe)
Charles Booher is a complete IDIOT! ("Charles Booher")
Phil Zimmerman Works for the NSA ("Charles Booher")
How Much Randomness?? ("Charles Booher")
----------------------------------------------------------------------------
From: Terje Mathisen <[EMAIL PROTECTED]>
Subject: Re: Extreme lossy text compression
Date: Sun, 18 Apr 1999 20:45:27 +0200
David Wagner wrote:
>
> In article <[EMAIL PROTECTED]>,
> D. J. Bernstein <[EMAIL PROTECTED]> wrote:
> > Actually, a 128-bit CRC _with a random polynomial_ guarantees an
> > extremely low collision probability for any fixed set of inputs.
>
> I'm confused. Isn't it true that CRC(x) = CRC(0||x), for
> any polynomial? ("||" represents concatenation of bits.)
Only if your CRC function is initialized with zero!
That's why you often see CRC functions that start with (unsigned) (-1)
instead: This way all leading zero bits are significant.
Terje
--
- <[EMAIL PROTECTED]>
Using self-discipline, see http://www.eiffel.com/discipline
"almost all programming can be viewed as an exercise in caching"
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: Thought question: why do public ciphers use only simple ops like shift
and XOR?
Date: Sun, 18 Apr 1999 22:04:54 GMT
[EMAIL PROTECTED] () wrote, in part:
>Terry Ritter ([EMAIL PROTECTED]) wrote:
>: As I see it, the real opportunity for
>: cryptanalysis is as part of a dynamic and interactive cipher design
>: process, as opposed to final certification.
>Two comments are warranted here.
>- Since cryptanalysis represents the "hard" part of the work in designing
>a cipher, this is why cipher designers should themselves know something
>about cryptanalysis;
>- And I think you can see why this design process actually _increases_ the
>probability of a design which is strong against known attacks, but weak
>against a future attack someone might discover.
I should note, though, that I basically agree with your point - and I do
think that in the specific case of the AES, going back to the drawing board
a bit would make quite a bit of sense - but I simply think that these two
arguments also need to be addressed.
John Savard ( teenerf<- )
http://members.xoom.com/quadibloc/index.html
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: dumb question on releasing source code
Date: Sun, 18 Apr 1999 22:31:32 GMT
In article <7fdh2m$gp0$[EMAIL PROTECTED]>,
"Chris Cavitt" <[EMAIL PROTECTED]> wrote:
> I'm a college student at a US University, and I have several small crypto
> programs(GoldWasser-Micalli, Blum-Goldwasser, etc) which use keys ranging
> from 8 to 16bits. Is it legal under US law for me to post the source code to
> these programs on my web page given the small key sizes, or is that illegal?
> I thought I remembered a professor saying it was legal to post anything with
> keys <56bits, but I wanted to see if anyone else knew offhand before I did
> it.
>
> Thanks for any help.
>
> --
It is kind of like doing your income taxes. No matter how
hard you try to do what is legal you will make a mistake and
could be arrested if you publish source code. If you give
enough dough to clinton political machine or get something
accepted in the AES competion or write a book then it is ok.
But if your an average Joe it is illeagal. Best to do the
work in a free country like Mexico and then you can put it on
a web site there. If we are lucky maybe we can be free some
day but that is in distant futrue.
> Chris Cavitt
> ([EMAIL PROTECTED])
> Senior Computer Engineering Major,
> Clarkson University
>
>
--
http://cryptography.org/cgi-bin/crypto.cgi/Misc/scott19u.zip
http://members.xoom.com/ecil/index.htm
============= Posted via Deja News, The Discussion Network ============
http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: Comments on Boomerang Attack Sought
Date: Sun, 18 Apr 1999 22:14:53 GMT
[EMAIL PROTECTED] (David Wagner) wrote, in part:
>I can't at the moment think of any good examples of this phenomenom. Do
>you know of any ciphers (even artificial ones) where the probability of the
>best differential decays super-exponentially in the number of rounds, and
>this property is maintained for many rounds?
Not at all. I did not know what the general tendency is, having only a very
limited acquaintance with differential cryptanalysis; which is why I had to
ask such a question.
>> It seems to me, therefore, the "two cases" where the boomerang attack could
>> be useful aren't cases where a cipher is weak - but where measures that
>> would strengthen a block cipher just haven't been taken quite far enough.
>I don't know. You might be right.
>(One example that might support your argument: COCONUT98 can be broken by
>a boomerang precisely because it uses only one decorrelation module, whereas
>DFC (with one decorrelator per round) seems safe against boomerang techniques.)
I raised this point because it would be unfortunate if a method effective
against insufficient precautions of this type inspired people to think they
were useless, if they in fact were very helpful if used properly.
John Savard ( teenerf<- )
http://members.xoom.com/quadibloc/index.html
------------------------------
From: [EMAIL PROTECTED] (R. Knauer)
Subject: Re: True Randomness & The Law Of Large Numbers
Date: Mon, 19 Apr 1999 00:20:30 GMT
Reply-To: [EMAIL PROTECTED]
On Sun, 18 Apr 1999 23:35:16 GMT, Dave Knapp <[EMAIL PROTECTED]> wrote:
>I am, and I can assure you that whatever Bob thinks it is, he's wrong.
Prove it.
Bob Knauer
"Our revels are now ended. These are actors, as I foretold you were
all spirits, and then are melted into air, into thin air. And like
the baseless fabric of this vision, the cloud-capped towers, the
gorgeous palaces, the solemn temples, the great globe itself, yea,
and all that it inherits, shall dissolve. And like this insubstantial
pageant faded, leave not a rack behind. We are such stuff as dreams
are made on, and our little life is rounded with a sleep."
-- The Tempest
------------------------------
From: Dave Knapp <[EMAIL PROTECTED]>
Subject: Re: True Randomness & The Law Of Large Numbers
Date: Sun, 18 Apr 1999 23:35:16 GMT
Herman Rubin wrote:
>
> In article <[EMAIL PROTECTED]>,
> R. Knauer <[EMAIL PROTECTED]> wrote:
> >Are physicists who are exploring the "physics of information" at
> >places like the Sante Fe Institute and others, going in the right
> >direction according to your thinking?
>
> I am not sure what they are doing.
I am, and I can assure you that whatever Bob thinks it is, he's wrong.
-- Dave
------------------------------
From: [EMAIL PROTECTED] (Herman Rubin)
Subject: Re: True Randomness & The Law Of Large Numbers
Date: 18 Apr 1999 20:37:00 -0500
In article <[EMAIL PROTECTED]>,
R. Knauer <[EMAIL PROTECTED]> wrote:
>On 18 Apr 1999 08:19:25 -0500, [EMAIL PROTECTED] (Herman
>Rubin) wrote:
>>If one looks at statistics in a reasonably intelligent manner,
>>the problem is not to decide whether or not the point null
>>hypothesis is true, but to decide whether it is better to act
>>as if it is than the alternative. This does affect testing.
>It is interesting to note that in Billingsley's book where he
>discusses Chernoff's Theorem, he points out in balancing the error of
>rejecting one hypothesis over another for the value of p, that as p
>approaches 1/2 it becomes increasingly difficult to discriminate
>between the p = 1/2 hypothesis and an hypothesis for a slightly
>different value near 1/2.
Why should this be surprising? It is a little easier to see in
the case of a normal translation parameter, and the problem is
extremely similar; the sample size needed for a given amount of
discrimination is proportional to 1/Kd^2, where K is the Fisher
information in a single observation, and d is separation.
--
This address is for information only. I do not claim that these views
are those of the Statistics Department or of Purdue University.
Herman Rubin, Dept. of Statistics, Purdue Univ., West Lafayette IN47907-1399
[EMAIL PROTECTED] Phone: (765)494-6054 FAX: (765)494-0558
------------------------------
From: [EMAIL PROTECTED] (D. J. Bernstein)
Subject: Re: Extreme lossy text compression
Date: 18 Apr 1999 08:27:02 GMT
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,
* n/8 multiplications of 24-bit polynomials by x^8, and
* n/8 table lookups of f |-> (x^32 f) mod p, where f has 8 bits.
The analogous CRC-128 implementation would use
* n/8 additions of 128-bit polynomials,
* n/8 multiplications of 120-bit polynomials by x^8, and
* n/8 table lookups of f -> (x^128 f) mod p, where f has 8 bits.
Now, if you could magically set up a size-2^32 table instead of a
size-2^8 table, you could get away with far fewer operations:
* n/32 additions of 128-bit polynomials,
* n/32 multiplications of 96-bit polynomials by x^32, and
* n/32 table lookups of f -> (x^128 f) mod p, where f has 32 bits.
That's basically the speed achieved by hash127, with integers replacing
polynomials mod 2, and the CPU's fast multiplication (inside the FPU)
replacing table lookups.
> "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.
> 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. The maximum
collision probability is around b^4/2^128 where b is the message length.
Anyway, hash127 is much faster.
---Dan
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Thought question: why do public ciphers use only simple ops like shift
and XOR?
Date: Mon, 19 Apr 1999 02:24:57 GMT
In article <[EMAIL PROTECTED]>,
[EMAIL PROTECTED] wrote:
> When I look at most publicly-available cryptographic algorithms, I see
> that nearly all of them consist of round upon round of simple operations
> like: shift, exclusive-OR, and "bit-twiddling
> ...
> My question is, aside from possible requirements for constructing their
> ciphers in hardware, why do designers routinely limit themselves to
> these simple bitwise operators in designing ciphers? It seems to me as
> a layman that the older, more complex designs were also far more secure
> than what we have now, and that a computer program would have no
> particular difficulty implementing them. We are not building hardware
> devices; we are not limited to LFSR's.
>
Whether you use simple or complex operations to describe a cipher
is not relevant: a multiplication can be seen as a sequence of
SHIFTs and ADDs; in fact any cipher can in principle be expressed
using only ANDs and NOTs. What is relevant in practice is to have
a cipher design with fast software execution on some hardware
platform. Therefore it can be useful to use the more complex
machine instructions. For example a multiplication, when available
in hardware, is much faster than the corresponding sequence of
SHIFTs and ADDs. The designer will always try to make the hardware
processor expend as much cryptographically useful work as possible
within a particular time frame. That is why it is so difficult to
design a cipher that is fast on many different processor designs.
In other words, if a cipher is especially optimized for one
platform it will probably be comparatively slower on others.
DES, the mother of all ciphers, uses only XORs, substitutions, and
bit transpositions. When I designed Frog, I decided to use only
XORs and substitutions (and continue the tradition), even though I
knew that ADD has better diffusion properties than XOR. In all
synchronous processors ADD takes the same time as XOR and I think
now that I made a bad decision then.
============= Posted via Deja News, The Discussion Network ============
http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own
------------------------------
From: [EMAIL PROTECTED] (D. J. Bernstein)
Crossposted-To: talk.politics.crypto
Subject: --- sci.crypt charter: read before you post (weekly notice)
Date: 18 Apr 1999 05:00:36 GMT
sci.crypt Different methods of data en/decryption.
sci.crypt.research Cryptography, cryptanalysis, and related issues.
talk.politics.crypto The relation between cryptography and government.
The Cryptography FAQ is posted to sci.crypt and talk.politics.crypto
every three weeks. You should read it before posting to either group.
A common myth is that sci.crypt is USENET's catch-all crypto newsgroup.
It is not. It is reserved for discussion of the _science_ of cryptology,
including cryptography, cryptanalysis, and related topics such as
one-way hash functions.
Use talk.politics.crypto for the _politics_ of cryptography, including
Clipper, Digital Telephony, NSA, RSADSI, the distribution of RC4, and
export controls.
What if you want to post an article which is neither pure science nor
pure politics? Go for talk.politics.crypto. Political discussions are
naturally free-ranging, and can easily include scientific articles. But
sci.crypt is much more limited: it has no room for politics.
It's appropriate to post (or at least cross-post) Clipper discussions to
alt.privacy.clipper, which should become talk.politics.crypto.clipper at
some point.
There are now several PGP newsgroups. Try comp.security.pgp.resources if
you want to find PGP, c.s.pgp.tech if you want to set it up and use it,
and c.s.pgp.discuss for other PGP-related questions.
Questions about microfilm and smuggling and other non-cryptographic
``spy stuff'' don't belong in sci.crypt. Try alt.security.
Other relevant newsgroups: misc.legal.computing, comp.org.eff.talk,
comp.org.cpsr.talk, alt.politics.org.nsa, comp.patents, sci.math,
comp.compression, comp.security.misc.
Here's the sci.crypt.research charter: ``The discussion of cryptography,
cryptanalysis, and related issues, in a more civilised environment than
is currently provided by sci.crypt.'' If you want to submit something to
the moderators, try [EMAIL PROTECTED]
---Dan
------------------------------
From: [EMAIL PROTECTED] (David Wagner)
Subject: Re: FSE-6 Report: Slide Attack
Date: 18 Apr 1999 20:17:53 -0700
For those who are interested, the final version of the FSE slide attack
paper is available online from my "publications" page:
http://www.cs.berkeley.edu/~daw/papers/
------------------------------
From: Geoff Thorpe <[EMAIL PROTECTED]>
Subject: Re: dumb question on releasing source code
Date: Sun, 18 Apr 1999 23:45:06 -0400
My limited understanding is that in your case, compiled code is ok,
source is not - because the source code basically contains THE algorithm
(independant of key-size) with a couple of easily edited constants in
it? Correct me if I'm wrong. In short, if I can swap the 8s and 16s with
128s and 256s and get proper ciphers going then you're probably not
allowed to post it.
But on the other hand, I doubt very much the spooks would want to come
out of the woodwork to beat up on you about this ...
Good luck with your work,
Geoff
Chris Cavitt wrote:
>
> I'm a college student at a US University, and I have several small crypto
> programs(GoldWasser-Micalli, Blum-Goldwasser, etc) which use keys ranging
> from 8 to 16bits. Is it legal under US law for me to post the source code to
> these programs on my web page given the small key sizes, or is that illegal?
> I thought I remembered a professor saying it was legal to post anything with
> keys <56bits, but I wanted to see if anyone else knew offhand before I did
> it.
>
> Thanks for any help.
>
> --
> Chris Cavitt
> ([EMAIL PROTECTED])
> Senior Computer Engineering Major,
> Clarkson University
------------------------------
From: "Charles Booher" <[EMAIL PROTECTED]>
Subject: Charles Booher is a complete IDIOT!
Date: Sun, 18 Apr 1999 20:50:17 -0700
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;
------------------------------
From: "Charles Booher" <[EMAIL PROTECTED]>
Subject: Phil Zimmerman Works for the NSA
Date: Sun, 18 Apr 1999 21:04:21 -0700
Phil Zimmerman works for the NSA
NAI (Network Associates) Now owns PGP.
NAI pays the rent on its chick red granite office building by selling
sniffers to the FBI and NSA.
The poeple who trust PGP Are fools!
------------------------------
From: "Charles Booher" <[EMAIL PROTECTED]>
Subject: How Much Randomness??
Date: Sun, 18 Apr 1999 21:26:55 -0700
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.
If PGP is using the key codes and the current time along with the
millisecond counter as a seed then this would be adequate, but...
Maybe they are not using the key codes, and...
Maybe they are not using the current time with the millisecond time.
Then we have
1000*1000*1000*1000
This would be easily computed using the resources available to the NSA.
Remember, these guys buy Ultra Sparcs by the semi-tractor trailer on a
monthly basis.
Also,
NAI sells sniffers to the NSA and FBI on a monthly basis.
Who do you think is paying the rent on the NAI red granite building if not
Uncle Sam?
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.
It turns out the 2.6.2 version is also weak, but that is another story.
Have you build your own version of PGP and looked at the source code for the
random number generators closely?
If you have claimed to do this why should I trust you?
Has anybody checked the binaries coming of www.pgpi.com?
Well, no it would require access to Microsoft Internal documents to be able
to do this. Remember Microsoft has their own binary format that is not
published.
No doing a byte by byte binary compare is not going to work because they
will always come up different.
People who trust PGP to be anything but "Pretty Good" are "Pretty Stupid
People".
------------------------------
** 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
******************************
