Cryptography-Digest Digest #781, Volume #10 Wed, 22 Dec 99 03:13:01 EST
Contents:
Re: Q: transcendental pad crypto ("almis")
Re: US Patent Office: How Stupid? Look Here... (Eric Smith)
Re: firmware encryption? ([EMAIL PROTECTED])
Re: Of one time pads, plaintext attacks, and fantasy (Steve K)
Re: Of one time pads, plaintext attacks, and fantasy (Paul Rubin)
Re: Of one time pads, plaintext attacks, and fantasy (Scott Nelson)
Re: firmware encryption? (Paul Rubin)
MARS ("William W. Joslin")
Re: random numbers straight out of MS BASIC (Raddatz Peter)
Re: US Patent Office: How Stupid? Look Here... (E. Y. Klormian)
Re: Synchronised random number generation for one-time pads ("Joseph Ashwood")
Re: DES as pseudo random number generator ("Trevor Jackson, III")
Re: Are thermal diodes as RNG's secure ("John E. Gwyn")
Re: DES key safety ("John E. Gwyn")
Re: compression & encryption ("John E. Gwyn")
Re: compression & encryption ("John E. Gwyn")
Re: decrypt method ("John E. Gwyn")
Re: Q: transcendental pad crypto ("John E. Gwyn")
----------------------------------------------------------------------------
From: "almis" <[EMAIL PROTECTED]>
Subject: Re: Q: transcendental pad crypto
Date: Tue, 21 Dec 1999 19:16:19 -0600
Gregory G Rose wrote in message <83p3v4$[EMAIL PROTECTED]>...
|In article <83ojjk$6eb$[EMAIL PROTECTED]>, Bob Silverman <[EMAIL PROTECTED]>
wrote:
|>Let me try to put an end to this nonsense before it goes any further.
|>
|>(1) There are very few numbers in mathematics that are actually KNOWN
|>to be transcendental. One can indeed construct infinitely many
|>transcendentals based on Liouville's theorem or from Thue's theorem.
|>But such numbers are USELESS for cryptographic purposes: they have
|>predicatable digit patterns and they are NOT normal numbers.
|
|Wow, that rarest of occurrences: a chance to tell
|Bob he should have done more research. :-)
|
|There is a paper by Josef Pieprzyk and others
|about using transcendental numbers for stream
|ciphers. A quick altavista doesn't find
|it. (Ha! Google presents me with a cached copy of
|a page that I "don't have permission to access":
|
|J. Pieprzyk, H. Ghodosi, C. Charnes, R.
|Safavi-Naini, Cryptography based on
|transcendental numbers, Information Security and
|Privacy, J. Pieprzyk and J. Seberry (Eds),
|Lecture Notes in Computer Science, Vol.1172,
|Proceedings, First Australasian Conference on
|Information Security and Privacy, ACISP'96,
|Wollongong, Australia, June 24-26, 1996, Springer
|1996, pp.96-107
|
|)
|
|Anyway, from memory now, any algebraic number
|raised to an algebraic power is transcendental. As
|far as the authors were concerned, the numbers
|were of cryptographic quality. So, for example,
|you could use sqrt(2)**sqrt(5). However, as usual,
|this is totally impractical, and anyway,
|effectively the key becomes the two numbers (2, 5)
|which still gives a limited search space.
|
|I agree with Bob's conclusion, which I paraphrase
|as "give up now".
|
|Greg.
|--
|Greg Rose INTERNET: [EMAIL PROTECTED]
|QUALCOMM Australia VOICE: +61-2-9181 4851 FAX: +61-2-9181 5470
|Suite 410, Birkenhead Point http://people.qualcomm.com/ggr/
|Drummoyne NSW 2047 B5 DF 66 95 89 68 1F C8 EF 29 FA 27 F2 2A 94 8F
There are two classes of trancendental numbers that are immune to
the LLL attack.
Class1: a^b where a in a positive integer (not 0 or 1),
and b is a real quadratic irrational.
Class2: a1^b1 * a2^b2 * ... *an^bn.
Such that ai not 0 or 1 and bi are algebraic and linearly independent over
the rationals.
Therefore; a 200 digit integer raised to the 200 digit prime root may be a
little harder
to guess than (2,5).
The problem is designing an efficient algorithm.
...al
------------------------------
From: Eric Smith <[EMAIL PROTECTED]>
Crossposted-To: talk.politics.crypto
Subject: Re: US Patent Office: How Stupid? Look Here...
Date: 21 Dec 1999 17:13:14 -0800
[EMAIL PROTECTED] (Ian Goldberg) writes:
> http://www.patents.ibm.com/details?&pn=US05443036__
> Method of exercising a cat
Filed in Nov. 1993???!!! When laser pointers first became available,
this was almost the first use for them that I found.
Admittedly, I wasn't doing it with the intention of exercising the cat;
it was for amusement (both mine and the cat's). But presumably the
cat did in fact get some exercise in the process.
So the question is: is there any *published* account of combined use of
laser pointers and cats, prior to Nov. 2, 1993?
Note that although the abstract says "to any other animal with a chase
instinct", the claims only specify "cat". Does this mean that using a
laser pointer to exercise a dog would not infringe?
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: firmware encryption?
Date: Wed, 22 Dec 1999 01:41:47 GMT
> Note that if someone really wants the code, they will attack the
hardware
> and get around the encryption. You really can't prevent this without
> making your device very expensive.
>
Can you expand on this? The processor (a Philips 89c51rc+) uses no
external memory, and incorporates standard lock bits to prevent flash
readback. The chip is about US$6 in quantity.
Dan
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: [EMAIL PROTECTED] (Steve K)
Subject: Re: Of one time pads, plaintext attacks, and fantasy
Date: Wed, 22 Dec 1999 02:01:35 GMT
On Wed, 22 Dec 1999 00:51:35 GMT, [EMAIL PROTECTED] wrote:
>Here's my confusion:
>Given that it is a random sequence of additives, how could you tell if a
>given sequence of ciphertext tranlated back to a given plaintext? And
>suppose it did, since its a contantly changing sequence, the particular
>additive that worked for say the first "C" in crocodile wouldn't be the
>same for the second.
>
>Am I missing something here? Or was this just one of those convient
>flights of fancy that make for a good story...if not a technically
>accurate one?
>
The missing link is the word "pseudo". The system used a fixed
process to crank out random-looking numbers from a given seed, in an
endless stream. This stream is supposed to "look" entirely random
(until it starts to repeat itself), but actually it is totally
structured.
The trick to analyzing such a cipher, is to subtract the known
plaintext from the ciphertext, and examine the key stream, to try and
figure out how it was generated. Not a trivial matter. It would help
to have a *lot* of known plaintext, taking up most of the original
message you are trying to break.
But is it possible? Definitely.
Steve K
---Continuing freedom of speech brought to you by---
http://www.eff.org/ http://www.epic.org/
http://www.cdt.org/
------------------------------
From: [EMAIL PROTECTED] (Paul Rubin)
Subject: Re: Of one time pads, plaintext attacks, and fantasy
Date: 22 Dec 1999 02:10:03 GMT
In article <83p7al$kut$[EMAIL PROTECTED]>, <[EMAIL PROTECTED]> wrote:
>Towards the end of "Cryptonomicon" by Stephenson (interesting
>novel by the way, anybody know of any others that use crypto as a plot
>device??)
There are quite a few. "The Key To Rebecca" (about cryptanalyzing
a book code to catch a spy) by Ken Follett is a fairly good one.
------------------------------
From: [EMAIL PROTECTED] (Scott Nelson)
Subject: Re: Of one time pads, plaintext attacks, and fantasy
Reply-To: [EMAIL PROTECTED]
Date: Wed, 22 Dec 1999 02:12:10 GMT
On Wed, 22 Dec 1999 00:51:35 GMT, [EMAIL PROTECTED] wrote:
>Towards the end of "Cryptonomicon" by Stephenson (interesting
>novel by the way, anybody know of any others that use crypto as a plot
>device??) there's a part in which one of the "heroes" describes
>how he broke a very complex system that was essentially a one-time pad
>(as I understand the term). The major breakthrough came when he planted
>some info and then waited for it to appear in an intercept.
>
>I know that in general, that was a technique sometimes used during
>wartime to break enemy ciphers. But the more I thought about it, I don't
>see how that would work with a one-time system.
>
>The system in question was based on generating a pseudo-random sequence
>(using a Riemann-zeta function) and then adding it mod(26) to the
>plaintext.
>
>In the text, he speaks of looking for the word CROCODILE, GOLD, FUNERAL
>and a few others.
>
>Here's my confusion:
>Given that it is a random sequence of additives, how could you tell if a
>given sequence of ciphertext tranlated back to a given plaintext? And
>suppose it did, since its a contantly changing sequence, the particular
>additive that worked for say the first "C" in crocodile wouldn't be the
>same for the second.
>
>Am I missing something here? Or was this just one of those convient
>flights of fancy that make for a good story...if not a technically
>accurate one?
>
That's not a one time pad, it's a pseudo one time pad.
pseudo random does not equal random. Or as I like to say,
pseudo one time pads offer pseudo security.
The Riemann-zeta function is a chaotic function.
Crypto systems based on chaotic functions have
historically been broken very quickly.
They generally don't make good random generators
for non-crypto applications either.
>=====
>PS: As I was typing this message, an idea come to me that I suppose
>might work.....
>
>1) Starting at the beginning of the ciphertext (or wherever) determine
>what sequence is neccesary to convert the character sequence to the
>suspected plaintext.
>
>2) work backwards and figure out the input seed to the zeta function
>required to produce the additive sequence found in step one.
>
>3) Apply the output of the function to the entire ciphertext and see if
>any sort of sensible plaintext results.
>
>if not then...
>4) step forward one character in ciphetext and start over.
>
>Sounds REALLY tedious!!
>
Well, yes, but tedious is something computers do really well.
If you only have try 72,057,594,037,927,936 times, then it's
essential broken given modern technology.
Scott Nelson <[EMAIL PROTECTED]>
------------------------------
From: [EMAIL PROTECTED] (Paul Rubin)
Subject: Re: firmware encryption?
Date: 22 Dec 1999 02:14:22 GMT
In article <83pa8r$msr$[EMAIL PROTECTED]>, <[EMAIL PROTECTED]> wrote:
>> Note that if someone really wants the code, they will attack the
>> hardware and get around the encryption. You really can't prevent
>> this without making your device very expensive.
>
>Can you expand on this? The processor (a Philips 89c51rc+) uses no
>external memory, and incorporates standard lock bits to prevent flash
>readback. The chip is about US$6 in quantity.
Generally it's possible to defeat those lock bits and similar devices
using standard semiconductor lab equipment (focused ion beams, etc).
Your average teenager probably won't have the skill or resources for
such attacks, but determined attackers will. Cable TV pirates do
stuff like that all the time. Look at some of Ross Anderson and
Markus Kuhn's papers on how to do it.
------------------------------
From: "William W. Joslin" <[EMAIL PROTECTED]>
Subject: MARS
Date: Tue, 21 Dec 1999 20:22:14 -0600
Can anyone tell me more about MARS algorithm... I know that it is a
finalist as an AES, but, tell me more about it...
------------------------------
From: Raddatz Peter <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Subject: Re: random numbers straight out of MS BASIC
Date: Tue, 21 Dec 1999 18:41:10 -0800
Tim Tyler wrote:
>
> Scott Nelson <[EMAIL PROTECTED]> wrote:
>
> : Note that the seed can't really be larger than the number
> : of states in the generator.
>
> That sounds pretty-much correct to me...
>
> : If the generator has a period of 2^24-1, then there can only be
> : 2^24-1 _unique_ seeds.
>
> ...while this seems to be a *little* bit of an over-generalisation.
>
> It seems quite possible to me for a RNG to have a period of (2^24) - 1 ...
> and yet have 2^128 different and "_unique_" seeds, each one of
> which produces a different cycle of this length.
>
> Perhaps my nitpicking does not apply to the M$ generator in question ;-)
> --
> __________
> |im |yler The Mandala Centre http://www.mandala.co.uk/ [EMAIL PROTECTED]
>
> A journey of a thousand miles begins with a cash advance.
I spent some time and re-ran my tests on MS BASIC RNG and must relent
that my first statements were incorrect... the cycle is 2^21 not 2^24
(my eyes are not the best anymore) still, if I generate 2 sboxes each
one contributing to the encryption then, in order to ensure that all
possible combos of the 2 boxes are exhausted then the attacker must make
a run against sb1,1 to sb2,1 and sb1,2 to sb2,1 etc. sb1,2097151 to
sb2,1 until
he reaches the true combo of, perhaps, sb1,547321 to sb2,501314. This
still means 1.3 e12 iterations if you introduce sb3 based on yet a diff.
seed the odds are getting out of hand because the attacker has to run
through 2 boxes completely and numerous times (sb1,1 - sb2,1 - sb3,1...
sb1,2 - sb2,1 - sb3,1 etc. you get the idea) before churning up the
right combo. (2*2^21+547321)(2^21+501314)*127500=~1.55 e18. Even at a
Gig/sec it would take 50 years. What makes it so impossible here is not
the entropy of 2^21 but the possible combos,... and that presupposes
that those "randomly" generated sequences are left as they turn up and
are not mixed around after generation. Maybe...
Peter Rabbit
------------------------------
From: [EMAIL PROTECTED] (E. Y. Klormian)
Crossposted-To: talk.politics.crypto
Subject: Re: US Patent Office: How Stupid? Look Here...
Date: Wed, 22 Dec 1999 02:40:16 GMT
[EMAIL PROTECTED] (Ian Goldberg) wrote:
>http://www.patents.ibm.com/details?&pn=US05443036__
>
> Method of exercising a cat
>
> A method for inducing cats to exercise consists of directing a beam of
> invisible light produced by a hand-held laser apparatus onto the floor
> or wall or other opaque surface in the vicinity of the cat, then moving
> the laser so as to cause the bright pattern of light to move in an
> irregular way fascinating to cats, and to any other animal with a chase
> instinct.
That doesn't sound like a legitimate patent because nothing was invented!
Someone simply found something cool to do with a laser pointer. I used a
laser pointer, a plumb bob, a protractor, and a compass to find a place to
mount my satellite dish. Do I deserve a patent for that?
(Yes, this is horribly off-topic.)
--
"E. Y. Klormian" is actually [EMAIL PROTECTED] (6720 981345).
0 1 23456789 <- Use this key to decode my email address and name.
Play Five by Five Poker at http://www.5X5poker.com.
------------------------------
From: "Joseph Ashwood" <[EMAIL PROTECTED]>
Subject: Re: Synchronised random number generation for one-time pads
Date: Tue, 21 Dec 1999 20:54:34 -0800
I know I'm more than a little late for the party, but I've been busy for a
few weeks.
"Tim Tyler" <[EMAIL PROTECTED]> wrote in message news:[EMAIL PROTECTED]...
> amadeus wrote:
>
> Then there's the issue that a known-plaintext attack reveals the key - and
> possibly allows inauthentic messages to be passed off as the real one.
That's where I beg to differ, although the security of OTP is generally
proven using XOR, there is no reason that one could not instead utilize
[insert your favorite cipher here] instead. In fact using a different cipher
could very well prove useful for this as it also eliminates an attack on the
plaintext (the bit-flip attack/problem). I see where this would be more
useful in the creation of stream ciphers, but it also applies to OTP.
Joseph
------------------------------
Date: Wed, 22 Dec 1999 00:26:11 -0500
From: "Trevor Jackson, III" <[EMAIL PROTECTED]>
Subject: Re: DES as pseudo random number generator
Scott Nelson wrote:
> "...a pseudo one time pad ..."
My attitude is similar to the farm hand who saw a giraffe at a circus. His quote was
"They
ain't no sech animal."
------------------------------
From: "John E. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: Are thermal diodes as RNG's secure
Date: Wed, 22 Dec 1999 01:09:23 -0600
Tim Tyler wrote:
> No hash is good enough to produce 128 bits of entropy from a biased
> source. I know of no practical way of getting 128 bits each with
> entropy 1.
That is logically equivalent to saying that you know of no way
to get a *single* bit "with entropy 1", which is no different
(so far as I can interpret your terms) than your original claim
that random bit generation was impossible.
------------------------------
From: "John E. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: DES key safety
Date: Wed, 22 Dec 1999 01:15:08 -0600
Paul Rubin wrote:
> Douglas A. Gwyn <[EMAIL PROTECTED]> wrote:
> >One question that would be nice to resolve is whether a single
> >64-bit block of corresponding plain and ciphertext always
> >determines a *unique* 56-bit DES key. (It's not obvious.)
> This is something that Deep Crack could determine in a few days.
I don't see how; it would have to crack 2^64 different inputs
to do it in the obvious way, which would take more than a few days.
- Douglas (not John)
------------------------------
From: "John E. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: compression & encryption
Date: Wed, 22 Dec 1999 01:38:38 -0600
Jerry Coffin wrote:
> Just for example, many compressors leave a signature at the beginning
> of their output. This is typically around 3 bytes or so,
> substantially smaller than a single block with nearly any reasonably
> recent block cipher of which I'm aware.
Say it is 24 bits out of 64 (DES). In principle, the attacker
needs to solve for only approximately 32 bits (56-24), due to
the additional constraints. Even if a 56-bit key search were
deemed not economically feasible, a 32-bit key search might be
cheap enough to put into practice. (How to use the constraints
to combine the unknowns [key bits] into a smaller set is not
something I am prepared to explain; maybe it's doable as a
large but affordable one-time computation, after which the
routine scanning of encrypted messages meeting that constraint
would be economical.
- Douglas (not John)
------------------------------
From: "John E. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: compression & encryption
Date: Wed, 22 Dec 1999 01:46:13 -0600
Ken Lamquist wrote:
> However, it is only a matter of time before breaking double DES
> becomes practical. Computing power has been growing at an exponential
> rate. In contrast, a scheme like double DES strengthens the
> encryption by a constant factor.
No, use comparable scales: In the search-number-of-key-bits
dimension, computing power increases linearly with time *if* it
indeed increases exponentially in terms of operation cycles.
------------------------------
From: "John E. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: decrypt method
Date: Wed, 22 Dec 1999 01:56:37 -0600
Steve Sharp wrote:
> I have an encrypted word, I also have the plain text of the same word.
> How does one go about finding the encryption method.
> I believe it's not DES but something like a bit shift or XORing.
> Is there a systematic way to figure out the encryption method ???
No. However, if the plaintext and ciphertext show some strong
relationship to each other, then there are a handful of well-known
encryption methods (e.g. Caesar substitution) that could be tried.
For most encryption schemes, solving your problem is harder than
finding the key for a given system, which is already too hard if
only about a word's worth of text is provided.
------------------------------
From: "John E. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: Q: transcendental pad crypto
Date: Wed, 22 Dec 1999 02:13:20 -0600
dls2 wrote:
> Again, how does one pick anything at random?
> Is any selection really random?
Sure; there are genuinely random processes galore.
But your question misses the point: the instruction
"pick a transcendental number at random" is flawed
because we only know the "names" of a handful of
transcendental numbers, fewer still whose binary
representations can be effectively computed to an
arbitrary number of places. These could be combined
in a few ways to produce other candidates, but the
actual key would be the original basic t.n.s and
the bits used to select a method of combining.
Basically, if we have an effective algorithm for
selecting a t.n. at random, we don't need to bother
with the t.n.
------------------------------
** 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
******************************
