Cryptography-Digest Digest #405, Volume #9 Sat, 17 Apr 99 00:13:04 EDT
Contents:
Re: Extreme lossy text compression (Geoff Thorpe)
Re: Thought question: why do public ciphers use only simple ops like shift and XOR?
("Steven Alexander")
quantum crypto + shortest vector problem (David A Molnar)
AES Competition ("Michael Scott")
Re: AES Competition ([EMAIL PROTECTED])
Re: Thought question: why do public ciphers use only simple ops like shift and XOR?
(ybizmt)
Re: Thought question: why do public ciphers use only simple ops like shift and XOR?
(ybizmt)
Re: AES Competition ("Nick Strauss")
Re: AES Competition (DJohn37050)
Re: How robust are pencil and paper cyphers? (Erm Yankoil)
Re: Radiation/Random Number question ("R H Braddam")
Re: PGP HowTo (Boris Kazak)
Re: PGP=NSA (PGP 6 totally cracked by NSA!!) ("Douglas A. Gwyn")
Re: Thought question: why do public ciphers use only simple ops like shift and XOR?
(Boris Kazak)
----------------------------------------------------------------------------
From: Geoff Thorpe <[EMAIL PROTECTED]>
Subject: Re: Extreme lossy text compression
Date: Fri, 16 Apr 1999 22:43:57 -0400
Hi there,
> I think I understand what you mean by a "good hash" based upon your
> description of its characteristics. You mentioned two flavors: SHA-1 and
> MD5. While I have seen C source code posted for SHA-1 by an individual, I
> wondered whether there is any authoritative site where proven source can be
> found? Is there a web site that is considered the "Hash Authority".
Loads of implementations are available in loads of places. I use
cryptlib (http://www.cs.auckland.ac.nz/~pgut001/cryptlib/) and mostly
through my Java wrapper for it (http://www.hoopal.com/geoff/jniCryptlib)
... if ALL you need is a hash function this would be somewhat like
swatting flies with a large bus. I've just checked and cryptlib is using
Eric Young's code (from SSLeay) for the hashing - that's under a GNU
license I think ... anyway, you can probably just suck that code out
(for SHA1) and use it, bearing in mind you can't sell or redistribute
the result without taking a close look at the license. (BTW: For "proven
source" - The various FIPS standards demostrate test vectors to check
your implementation against, Peter has included these in cryptlib for
start-up self-testing and you could probably consult his code to see the
test vectors).
> What about licensing these hashes? Who owns them? Is it considered
> freeware, shareware, or what? Or is it more just a programming structure like
> a "nested loop" which isn't really owned by anybody?
Not sure about the licensing - but for sure it's not just a "nested
loop" because this is more than a hash-function we're talking, it's a
SECURE hash function which may be more than you actually need.
> To answer your question, in actual fact, I DO want to count even a 1 byte
> change as a change, so a good hash sounds BETTER than perfect for my needs.
Yeah - but do you need a secure hash? The strength(s) of SHA1 (and MD5
and the other crypto-hash functions) is not just that they provide a
good "ID" of a given piece of data (with your required property of any
change in the input generating, with all probability, a corresponding
change in output), but also that they are collision-resistant (as John
said) ... that is, a hacker has a very tough job to find a piece of
input data that would generate a chosen hash-value ... if you're just
looking for a good index into your data-store, this is not an issue ...
because you're not going to be deliberately trying to create texts that
ARE different to anything there but have a matching hash-value just to
force your application run an extra lookup to check.
Maybe all you need is to use a standard hash function (or even cut your
own if you feel daring) - lots of XORs and you're away [;-)
Basically a standard hash (should) give you;
============================================
- If A and B are the same data, their hashes match (ie it's totally
deterministic - the output is a function of the data only, no external
or random information is used in the function).
- If A and B are different (and independant/unrelated), then the
probability their hashes match is pretty close to one in "m" (where "m"
is the number of possible hash values, hopefully this would be equal to
2^n where n is the number of bits in the hash-value). This assumes
however that A and B are independant - in most cases this probability
REALLY isn't that microscopic if somebody is trying to intentionally
construct a B for the purpose of matching A's output.
If your texts are likely to be similar quite often - you might want to
deterministically "munge" your input before applying a "standard" hash
... in other words choose a method for mashing up the contents to spread
any differences in the text around ... then compression is always handy
for hiding redundancy.
A "secure hash" gives you;
==========================
- the same as a standard hash function, EXCEPT;
- even if somebody tries to construct a B for the purpose of matching
A's output, they will (hopefully) fail to improve the probability much
beyond 1 in "m" - this is why secure hashes are used in cryptographic
"signature" techniques. The collision probabilty stays astronomically
small even when you're TRYING to get them to collide.
So a secure hash will solve your problems and by design, shouldn't
require you to take the additional steps I suggested (if you had to then
by definition, it's vulnerable to the problems those steps try to
avoid). You just have to decide on convenience and/or performance. In C,
on most platforms (OS and hardware), it's possible to get some pretty
quick hashes going and from my experience; in network systems,
particularly involving large databases, the time taken in a secure hash
will be the last of your worries [;-)
> I wonder whether sufficient randomization can be achieved in just 20 bytes
> considering the non-random characteristic of my inputted plaintext.
> Generally the plaintext is going to be ordinary English language text (like
> that found in Usenet or in ordinary Email), so there will be a high
> concentration of the 26 letters A-Z upper and lower case, plus spaces and
> some punctuation. Can a "good hash" still output sufficiently random results
> from that input? Do hash developers run any statistical tests to back up
> their theory?
See my above comment - making any change in the output data (be it
appending something to it, transforming it all in some rational way, or
just changing one byte a little bit) should make radical changes in the
output of a secure hash function (and probably most good regular hash
functions). Compressing data is a particularly good idea on language
text (and should be considered when storing masses of it - especially if
it's for archiving and not really high-load processing), but is not
necessary at all in a secure hash. However, it may be handy for
performance properties. English language text usually compresses a lot
with typical algorithms (ZIP, etc) - you might want to try benchmarking
the speed trade-offs on using or not using compression first (the
compression takes a little time, but reduces the time required to hash
because you're hashing less data).
So a secure hash (unless it's been broken) is as good as the size of the
hash-values it maps data to. And 20 bytes can hold a lot of different
hash values. If the number of records in your database tables got close
to even a 5-byte number I would be staggered. Some quick (and probably
way-off) probability calculations; If you had 256^5 (maximum 5-byte
number - just over a thousand billion) records in your database, which
is a little optimistic - the probability that ANY two records had the
same SHA1 hash would be less than 1 in 256^10 (that last huge number
squared). Some realists would say you don't even have to run a check if
two texts have matching hash-values - the chance that they do but aren't
the same text is ... well ... unlikely (to grossly understate things).
Another comment (although you probably don't want any more); if each
record is storing a 20-byte hash in a seperate field (as a fixed-length
ASCII field - 27 chars using BASE64, or 40 chars using
hex-representation), you can optimize your database querying
dramatically either by using it as your primary key (if you're prepared
to take that astronomically small chance of a collision), or by putting
an index on it (again, if you're prepared to take the non-risk then you
could put a UNIQUE constraint index on it). The hash will provide a good
serial number for each record, and with the index it would speed up your
checks for duplicates.
Cheers,
Geoff
------------------------------
From: "Steven Alexander" <[EMAIL PROTECTED]>
Subject: Re: Thought question: why do public ciphers use only simple ops like shift
and XOR?
Date: Fri, 16 Apr 1999 17:05:05 -0700
What exactly is your suggestion for the creation of a cipher in which we can
place our trust? The best we can do at any one point is to create a cipher
that is secure against the attacks that we know of . If we do not know of
many attacks this will not entail much. If we have a group of the best
cryptanalysts who analyze a cipher and find no vulnerabilities, this does
not mean that any vulnerabilities do not exist...it only means that those
that we know of...and variations thereof do not exist in that cipher. This
gives us a degree of trust in the cipher. In RSA for example, we believe
that the only way to break the cipher is to factor n. If I find a new way
to factor n in just a couple of minutes on your typical PC the cipher is
broken. However, the odds that someone will invent a way to factor that is
so phenomenally better is very unlikely. If I try to build a cipher and do
not understand cryptanalysis I will not ahve any idea how to protect my
cipher. If you have a better way to design ciphers, please share.
-steven
------------------------------
From: David A Molnar <[EMAIL PROTECTED]>
Subject: quantum crypto + shortest vector problem
Date: 16 Apr 1999 18:10:49 GMT
Has anyone come up with a means of solving the shortest
vector problem on a quantum computer? or evidence against
such a thing?
Thanks,
-David Molnar
------------------------------
From: "Michael Scott" <[EMAIL PROTECTED]>
Subject: AES Competition
Date: Fri, 16 Apr 1999 22:55:53 +0100
Is it possible to make a modest bet on the outcome of the AES competition?
Which are the favourites?
Is anyone willing to shout out the odds?
Mike Scott
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: AES Competition
Date: Sat, 17 Apr 1999 01:18:00 GMT
Why would you say that MARS, DFC, Twofish, and Rijndael are "taken out"?
In article <fLOR2.340$[EMAIL PROTECTED]>,
"Steven Alexander" <[EMAIL PROTECTED]> wrote:
> Hmmmm.
> I'd say that the following are taken out:
>
> Loki97
> DEAL
> FROG
> Magenta
> MARS
> Hasty Pudding
> Crypton
> DFC
> TwoFish
> RUNDAEL
>
> leaving:
>
> RC6
> Serpent
> CAST-256
> SAFER+
> E2
>
>
============= Posted via Deja News, The Discussion Network ============
http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own
------------------------------
From: [EMAIL PROTECTED] (ybizmt)
Subject: Re: Thought question: why do public ciphers use only simple ops like shift
and XOR?
Date: Sat, 17 Apr 1999 02:22:42 GMT
On Fri, 16 Apr 1999 23:53:14 GMT, Terry Ritter <[EMAIL PROTECTED]> wrote:
> *I* think you are being selective in stating "the" point Schneier has
> made. While he may have conceded that no cipher is secure after long
> discussion, his point often is that cryptanalysis is necessary to know
> the strength of a cipher. Of course, the fact that he sells such
> services would have nothing to do with it.
Refresh my memory. What do you sell?
------------------------------
From: [EMAIL PROTECTED] (ybizmt)
Subject: Re: Thought question: why do public ciphers use only simple ops like shift
and XOR?
Date: Sat, 17 Apr 1999 02:28:52 GMT
On Fri, 16 Apr 1999 23:53:19 GMT, Terry Ritter <[EMAIL PROTECTED]> wrote:
> It is not provably better. And not provably better admits the
> possibility of contradiction. So we do not know. Which means that
> interpreting years of intensive analysis as strength is nothing more
> than DELUSION. Cryptanalysis of any length whatsoever provides no
> rational scientific indication of strength.
Nor is it intended to. Who has ever claimed that analysis equals
strength in any field? It is intended to make you more confident
that something is strong. No one is saying it proves strength.
Not at least trying cryptanalysis on a cipher is stupid which
I'm sure you agree with.
> In some cases this process is a deliberate attempt to make
> cryptanalysis seem more than it is, so that ciphers which have
> "passed" (whatever that means) will be accepted as "strong," which
> should never be done. We can see this in the path of the AES process,
> which, presumably, gets us a "strong" cipher. We see NO attempt to
> innovate constructions or protocols which give strength in the context
> of ciphers which may be weak. Yet you would have us assume that
> everyone knows that ciphers may be weak, and simply chooses to do
> nothing about it.
Nice rant. Where are you going with this and how does it sell your
product?
------------------------------
From: "Nick Strauss" <[EMAIL PROTECTED]>
Subject: Re: AES Competition
Date: Fri, 16 Apr 1999 19:38:18 -0700
Steven Alexander wrote in message ...
>Hmmmm.
>I'd say that the following are taken out:
>MARS
>TwoFish
>RUNDAEL
Why would you take these three out? In particular Rijndael, which seems to
offer some of the best performance on a variety of hardware and (unless I've
been working too hard of late) hasn't been shown to have any security
defects?
Mars and Twofish don't seem to be slouches in either security or performance
either!
Me picks, just for fun?
MARS
Rijndael
E2
RC6
Mabye Twofish, and I'd like to see Serpent as a finalist, just because its
another interesting variation.
--N
------------------------------
From: [EMAIL PROTECTED] (DJohn37050)
Subject: Re: AES Competition
Date: 17 Apr 1999 02:39:48 GMT
I agree with N.
Don Johnson
------------------------------
From: [EMAIL PROTECTED] (Erm Yankoil)
Subject: Re: How robust are pencil and paper cyphers?
Date: Sat, 17 Apr 1999 03:11:06 GMT
[EMAIL PROTECTED] (InEN97) wrote:
>It is my understanding that pencil and paper cyphers...
If you're interested in such things, Bruce Schneier describes an
interesting invention of his called "The Solitaire Encryption Algorithm"
here: http://www.counterpane.com/solitaire.html
--
"Erm Yankoil" better known as [EMAIL PROTECTED]
012 3456789 <- Use this key to decode my email address.
Fun & Free - http://www.5X5poker.com/
------------------------------
From: "R H Braddam" <[EMAIL PROTECTED]>
Subject: Re: Radiation/Random Number question
Date: Fri, 16 Apr 1999 21:58:54 -0500
Medical Electronics Lab wrote in message
<[EMAIL PROTECTED]>...
>R H Braddam wrote:
>> Can anyone here tell me if the Americium 241 (1 microcurie) source used
in
>> smoke detectors would cause soft (or hard) errors in chips if placed in
>> contact with RAM or ROM chips?
>
>Am241 has a 5 MeV alpha for a decay product. Range is about 5 cm in
>air, about 200 microns in plastic. Won't cause any problems at all :-)
>
Actually, I was hoping for (soft error) problems. I had read somewhere that
a few sheets of paper would stop alpha radiation. I suspected that the
encapsulation would block alpha particles, and that was the reason for the
next question.
>> What if the chips were obtained as dice, or as dice bonded to the bottom
>> half of the package and pin connections made... would the passivation
layer
>> block alpha radiation?
>
>Most of it. but it's about the most expensive way possible I can
>think of!
>
What would make it the most expensive way? I thought that obtaining ICs
before the final encapsualtion would be less expensive. Oh, well. The idea
was to place the Am241 close to the die in order to cause bit dropping or
picking, to generate random numbers directly rather than using a separate
detector. For that purpose the thinnest effective passivation layer would be
preferable, wouldn't it? Another responder indicated that cumulative effects
would destroy the chip too quickly anyway, so this appears to be an
unacceptable idea.
>> If radiation causes picking or dropping of bits in RAM or ROM chips and
>> doesn't cause catastrophic failure of the chip, wouldn't this be a
useable
>> bit source for desktop computers for generating random numbers?
>
>Not very feasible. A much simpler way is to amplify the signal
>off a smoke detector and use that for a random noise source. I'm
>submitting a paper to the CHES workshop on this, if you'd like a
>schematic as well as a paper I can send you what we've got. It
>will be submitted for refereeing next week ('cause that's the
>deadline!) but I don't know if it will be accepted. It passes
>DIEHARD and Diaphony at reasonable data rates (about 2kBytes/sec)
>so the basic idea appears to be sound. It will never be useful
>commercially tho, it's just too much fun :-)
>
I agree that starting with something that works already should be simpler.
The smoke detector board is kind of big, though. I was hoping to find a way
which would result in a smaller package.
I would be honored if you sent a schematic and the paper to me. I'd like to
try to build one for my own use. I will keep anything you send to me
completely confidential. That's not too hard where I live, it's a small
town.
In my opinion you should patent the device. It might not be commercially
useful for those who need a higher data rate, but 2kBytes/sec should be more
than adequate for personal use.
Thanks again for your response. I hope your paper is *very* well received.
If it results in a commercial product for end users I think it will be a
significant contribution to personal privacy.
You may reply to [EMAIL PROTECTED] if you wish.
Murphy's Law is the only sure thing in the Universe.
Rick
------------------------------
From: Boris Kazak <[EMAIL PROTECTED]>
Subject: Re: PGP HowTo
Date: Fri, 16 Apr 1999 20:30:47 -0400
Reply-To: [EMAIL PROTECTED]
Steven Alexander wrote:
>
> Substantiate your claim! You are becoming a pest. If PGP is broken, prove
> it! If SecureOffice is secure, prove it! What algorithm/s does
> SecureOffice use? Please tell me it isn't proprietary. Have you ever
> broken a cipher publicly? Why are you qualified to build a secure cipher?
=======================(irrelevant)
Dear Steve!
You probably just don't have enough cynicism to understand what is
really going on here. The guy who makes these postings IS NOT and
NEVER WAS Charles Booher.
By writing and distributing the SecureOffice Charlie Booher made
himself a target for a bunch of scoundrels who will stay at nothing
to get him silenced. Now, the technique of attributing outrageous
sentences to somebody who must be discredited is not exactly new.
A classical example is the ruse with "Protocols of the Elders of
Zion", faked by the Russian secret police in 1890-s and subsequently
used by Russian tzar to launch the Jewish pogroms and later by Hitler
to launch the Holocaust.
A recent example of this technique is the accusation of Los Angeles
police detective Mark Fuhrman, who was loudly and cynically accused of
being racist, doubt has been cast on his honesty in handling the
evidence, which in turn resulted in acquital of O.J.Simpson.
A guy(or a bunch) making these postings is clearly building up,
more precisely, faking some "evidence" which ultimately will be used
to lock Charlie Booher into a mental institution. Who is interested in
such an outcome - certainly not C.Booher himself. Are there people who
might be interested in silencing him - certainly.
And please don't tell me that such things cannot happen in America.
I come from Russia, I have seen people locked up with less evidence
than that; Americans, on their side, are very quick learners, so this
Russian method is almost certain to find a second home here.
Best wishes BNK
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: PGP=NSA (PGP 6 totally cracked by NSA!!)
Date: Sat, 17 Apr 1999 04:10:37 GMT
Thomas Pornin wrote:
> According to Charles Booher <[EMAIL PROTECTED]>:
> > The NSA also buys Ultra SPARCS by the truck load.
> I am not american but I think you should really complain: your taxes
> should be used for buying Alpha stations, that give a better ratio
> performance/price.
NSA, like any other relatively smart organization, buys the
equipment it needs, balancing *several* requirements, not just
whatever "performance/price" ratio you had in mind.
You can safely bet that they have a lot of x86 PCs and quite
a few supercomputers, too.
Computer acquisition is not a "no-brainer".
------------------------------
From: Boris Kazak <[EMAIL PROTECTED]>
Subject: Re: Thought question: why do public ciphers use only simple ops like shift
and XOR?
Date: Fri, 16 Apr 1999 21:16:02 -0400
Reply-To: [EMAIL PROTECTED]
Sundial Services 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." Most of these ops are
> readily reversible.
>
> About the only "original idea" I've seen, since reading discussions of
> older machines like SIGABA, is Terry Ritter's "Dynamic Substitution"
> patent. At least he is using a more complex transformation than 99.9%
> of the things I've seen ... since SIGABA ... and he's burying a lot more
> information than most designs do.
>
> 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.
==================
As layman to layman - the most obvious reason is that these simple
operations are easy to analyze. It is not by accident that the only
exception to this rule is IDEA, based on modular multiplication, and
this immediately brushes away a whole bunch of possible attacks.
Another observation - most published attacks against various ciphers
are essentially attacking not as much the cipher per se, as its key
schedule. It is not by accident that BLOWFISH is so steady, its key
schedule does not provide any opportunity for related-key attacks.
On the other hand, a recently published attack against IDEA makes
heavy use of the fact that its subkeys are produced just by 25-bit
circular shift. Use another key scheduling mechanism (same modular
multiplication which is akready present in the program), and this
attack will result in nothing.
As a layman, I experimented with modular multiplication mod 2^32-1
and mod 2^32+1, found the cycles produced by raising different
numbers to the subsequent powers, discovered methods of testing
numbers for having the multiplicative inverses, and finally wrote
a program for a cipher which I call LETSIEF (FEISTEL spelled backwards).
This program uses multiplication mod 2^32-1 as the combining operation
between L and R halves. The speed is fantastic - multiplication mod
2^32-1 is implemented in 3 processor instructions on a Pentium, an
array of 256 modular multipliers assures full plaintext dependency,
inverses also occupy an array of 256 elements, so the only difference
between encryption and decryption is that you take your multiplier
from a conjugate array. Key scheduling uses the same multiplication
routine which already exists in the program.
I am not going to post this program or to promote it in any way.
It serves my purposes, I am ready to give the code to anybody who is
interested, but nothing beyond that.
BTW, I also experimented with multiplication mod 2^64+1 and 2^64-1.
Unfortunately, I am not so great a programmer, and my computer has
no 64-bit registers. So beyond some basic knowledge, nothing yet did
come into practice (but the ciphers could be terrific!).
Best wishes BNK
------------------------------
** 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
******************************
