Cryptography-Digest Digest #731, Volume #13 Thu, 22 Feb 01 00:13:01 EST
Contents:
Re: question1,2,2a,3,4,5,5a,5b,5c,6 (Jerry Coffin)
Re: My encryption system..... (Jerry Coffin)
Re: The Key Vanishes: Scientist Outlines Unbreakable Code, Read it and
([EMAIL PROTECTED])
Re: New unbreakable code from Rabin? (Bill Unruh)
Re: New unbreakable code from Rabin? (John Savard)
Re: PGP Public Keys (John Savard)
Re: New unbreakable code from Rabin? ([EMAIL PROTECTED])
Re: Question about password hashing and hash chaining (Sundial Services)
Re: The Key Vanishes: Scientist Outlines Unbreakable Code, Read it and (Sundial
Services)
Re: Given any arbitrary numbers a and b. (Benjamin Goldberg)
FS: Koblitz, a course in number theory and cryptography (TheBassCannon)
Re: Given any arbitrary numbers a and b.Can I ALWAYS find a (Roger Schlafly)
Re: The Key Vanishes: Scientist Outlines Unbreakable Code, Read it and Weep Boys
(Harvey Taylor)
Re: Is there an algorithm to sequentially enumerate all transcendental (Vaughan
Pratt)
Re: New unbreakable code from Rabin? ("Trevor L. Jackson, III")
----------------------------------------------------------------------------
From: Jerry Coffin <[EMAIL PROTECTED]>
Subject: Re: question1,2,2a,3,4,5,5a,5b,5c,6
Date: Wed, 21 Feb 2001 17:17:07 -0700
In article <96v8fu$7sek$[EMAIL PROTECTED]>,
[EMAIL PROTECTED] says...
[ ... ]
> 1.Do you have to be a good cryptanalyst before you can call yourself a good
> cryptographer?
This has certainly been argued quite effectively. I'm not sure every
good cryptographer has also been a cryptanalyst, but offhand I can't
think of many (at least recently) who haven't been either.
> 2.Do you learn by practicing with breaking codes? Can you break codes
> "theoretically"?
Just about the ONLY way to learn to break codes seem to be practicing
-- there are lots of smart people who know all the right kinds of
things, but never do manage to get at all good at it.
> 2a.Where can you find material to work on? (if you need to do so, but I
> strongly believe you do)
Fortunately, there's NO shortage of sources. Typing "encrypt" into
Google yields over 350,000 hits. I couldn't give an exact
percentage, but at a guess, over half the programs I've seen people
release purporting to do wonderfully secure encryption, at least half
are badly broken.
> 3.What classic textbooks are a good source of practice problems?
The Codebook is a decent source of practice problems. I'd also
consider the Military Cryptanalysis and Military Cryptanalytics
series quite good -- the Zendian problem comes with particularly
strong recommendations.
> 4.If you really want to crack difficult chipers mustn't you possess
> excellent programming tools/skills?
Not necessarily, though it obviously doesn't hurt anything.
> 5.My user name is the encryption of my dog's name. Isn't this a rather
> stupid problem?
If you mean asking somebody to break it, then yes.
> Anyway, does it make sense to ask you what my dog's name is?
Not really.
> Will your answer tell me if you are a good cryptanalyst (I'm sure you'll say
> "no"!)? DO you need to know the algorithm that I used to encrypt it?
> 6. Am I the only one that doesn't particularly love "applied cryptography,
> 2nd ed."?
It depends. Various ciphers have been and can be broken without
knowing the algorithm up-front. Knowing the algorithm mostly makes
it much quicker and easier to break, as a rule. Most attacks could
probably be invented using only ciphertext, but unless the cipher is
_really_ weak, one would probably have to collect statistics on LOTS
of ciphertext to even get started.
As far as telling us your name encrypted with a particular algorithm
goes, you generally need quite a bit more text than that to attack
even a very simple cipher -- for example, if I say that "J" encrypts
to "Y", it would be easy to invent MANY different ciphers that happen
to meet that. Now, if I add the fact that "K" encrypts to "Z", and
"L" to "A", it wouldn't take much for most people to figure out the
rest.
OTOH, most things you'd generally think of as a real cipher (rather
than just minor obfuscation) will take quite a bit more text than
that to figure out -- for a simple cipher, a few dozen to a few
hundred bytes is typically enough, while one that's reasonably close
to secure might involve terabytes or more.
Books: I recommend _Handbook of Applied Cryptography_, by Menezes,
Van Oorschot and Vanstone, ISBN 0-8493-8523-7 as one of the best
references available today. It's also available freely online,
though I don't have a URL handy.
--
Later,
Jerry.
The Universe is a figment of its own imagination.
------------------------------
From: Jerry Coffin <[EMAIL PROTECTED]>
Subject: Re: My encryption system.....
Date: Wed, 21 Feb 2001 17:25:33 -0700
In article <#pkb2AFmAHA.279@cpmsnbbsa07>, [EMAIL PROTECTED] says...
[ ... ]
> multiple depth: You really need to learn the lingo, there's no such thing as
> depth in ciphers, except for maybe the depth of despair when you realize
> that your "unbreakable" cipher is actually worthless
To be entirely fair, though it seems to be totally UNrelated to his
use of the term, "depth" does have a specific meaning when applied to
ciphers: it's how often a particular key is used to encrypt different
messages.
--
Later,
Jerry.
The Universe is a figment of its own imagination.
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: The Key Vanishes: Scientist Outlines Unbreakable Code, Read it and
Date: 22 Feb 2001 00:33:42 GMT
The assertion that this approach "changes the ground rules"
because the "random stream of numbers vanishes" seems a little
suspect.
In any private-key stream encryption system -- including this one --
the communicating parties can choose to either retain, or to destroy,
information needed to re-generate at a future date the keystream used
to encrypt and decrypt a given message.
In a conventional system the key itself would be sufficient
information, and hence is quite compact; in the proposed
unbreakable system sufficient information would be the entire
keystream actually used to encrypt the message -- much less
compact, but still very practical to retain since it is only the
size the message.
So there is no "change in the ground rules" with respect to
agency-imposed requirements to escrow or retain keys --
just a larger amount of data needs to be escrowed or retained.
Steve
------------------------------
From: [EMAIL PROTECTED] (Bill Unruh)
Subject: Re: New unbreakable code from Rabin?
Date: 22 Feb 2001 00:40:13 GMT
In <3a944af9$[EMAIL PROTECTED]> [EMAIL PROTECTED] writes:
>but a transient (and large so it can't be stored) public pool
>of random data (to be used as session keys) seems to have its
>uses.
This makes no sense. To be public, it has to be stored for a while. If
it can be stored for a while, it can be stored indefinitely. To base an
encryption scheme on "haw much data can my opponent store" seems to be
much more questionable than to base it on "how much can my opponent
compute".
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: New unbreakable code from Rabin?
Date: Thu, 22 Feb 2001 00:44:13 GMT
On Wed, 21 Feb 2001 11:25:57 +0100, Mok-Kong Shen
<[EMAIL PROTECTED]> wrote, in part:
>Thanks. I have two more questions: (1) Is it the secret key
>of the index generator that prevents an eavesdropper from
>getting the key stream? But then in an 'absolute' (maybe
>pedantic) sense the security of that generator would have
>to be considered.
You raise an interesting point.
Let us suppose that the index generator had just a 10-bit key. Then an
eavesdropper, knowing its algorithm, could just save 1000 times as
much of the enormous random keystream as the two legitimate
participants to then test at his leisure.
So the index generator must have a sufficiently large key that _the
space of keystream bits possibly used as key_ is "too big to save" in
the same way as the total random keystream is.
As long as you have to save *all the bits* to test different index
generator keys, it wouldn't matter that the index generator was a
cryptanalytically-poor PRNG, though.
The main problem with this scheme is that the difficulty of recording
this massive random keystream is, at best, comparable to a very weak
public-key system in terms of the difference in work factors between
the legitimate participants and the attacker. Think, for example, of
using dye-based photographic methods (as used for blueprints and
microdots - unlike normal photography, which involves large crystals
that produce 'grain') instead of magnetic recording.
John Savard
http://home.ecn.ab.ca/~jsavard/crypto.htm
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: PGP Public Keys
Date: Thu, 22 Feb 2001 00:36:43 GMT
On Wed, 21 Feb 2001 07:48:36 -0600, John Atkins
<[EMAIL PROTECTED]> wrote, in part:
>What kind of MIME encoding is used to encode PGP keys? If I wanted to
>decode all the information about a PGP key, how would I do it? Ex:
>Decoding this:
>
>-----BEGIN PGP PUBLIC KEY BLOCK-----
>Version: PGP Desktop Security 7.0.3 Evaluation
>
>mQGiBDqR984RBADxMxoPw7hkRdoGU3Wuzm6FshV50SFIUdcXgpWSLmkPiAvtXhcL
Well, the characters represent six bits each, using the same Base64
encoding as MIME does. PGP documentation would outline the format of
the block itself.
John Savard
http://home.ecn.ab.ca/~jsavard/crypto.htm
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: New unbreakable code from Rabin?
Date: 21 Feb 2001 19:51:15 -0500
Bill Unruh <[EMAIL PROTECTED]> wrote:
> In <3a944af9$[EMAIL PROTECTED]> [EMAIL PROTECTED] writes:
>>but a transient (and large so it can't be stored) public pool
>>of random data (to be used as session keys) seems to have its
>>uses.
> This makes no sense. To be public, it has to be stored for a while.
No ... it can be publicly transmitted as it is generated and never stored.
The background black body radiation at such and such right ascension
and such and such declination, tomorrow night at midnight UT is
a publicly accessible bit of data (for those with radio telescopes in
the proper hemisphere). There is a lot of random stuff (I believe the
NY Times article made reference to having a satellite generate and
broadcast a stream of random data - a stream of so much data that only
a small portion could be stored - I would not trust that, though).
If there were 2^1024 different keys of random data generated every week
no one could store that week after week.
The question is whether one can find or generate so much random junk
(and publicly broadcast it as it is generated) that a week's worth (say)
cannot be stored.
IF you can do that it could be used.
------------------------------
Date: Wed, 21 Feb 2001 18:30:32 -0700
From: Sundial Services <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Subject: Re: Question about password hashing and hash chaining
And at the risk of stating the obvious: be sure that there is
absolutely no way to circumvent your system's security. For example, by
determining the location of the password field, calculating a value to
put into it, replacing the original value with the imposter, and
replacing the original value to hide the traces.
This is often a fatal weakness of password security, analogous to
unscrewing the bolts that hold the lock in place, opening the door,
robbing the house, and reinstalling the lock on the way out! It's often
easier than you think.
> > (5) As a test for the correct passphrase, would this suffice: Create a
> > hash of
> > the ciphertext, encrypt the hash and store it. To test, create the hash of
> > the ciphertext, decrypt the stored hash and compare the results...?
>
> Yes that is sufficient to verify that he correct passphrase has been
> entered. However to make it harder to perform dictionary attacks you should
> add a salt in there somewhere, so you compute has(salt, passphrase) and
> verify.
> Joe
==================================================================
Sundial Services :: Scottsdale, AZ (USA) :: (480) 946-8259
mailto:[EMAIL PROTECTED] (PGP public key available.)
> Fast(!), automatic table-repair with two clicks of the mouse!
> ChimneySweep(R): "Click click, it's fixed!" {tm}
> http://www.sundialservices.com/products/chimneysweep
------------------------------
Date: Wed, 21 Feb 2001 18:35:07 -0700
From: Sundial Services <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Subject: Re: The Key Vanishes: Scientist Outlines Unbreakable Code, Read it and
I'm rather puzzled by the hooplah on this (although it's a great piece
of journalistic copy). It's basically a one-time-pad encipherment that
assumes that the two parties can simultaneously receive the same key
stream, i.e. from an orbiting sattelite. Certainly this type of a
system is provably and obviously secure ... IF the sun doesn't throw any
sunspots at exactly the wrong time, Murphy's Law does not happen and so
on. In fact I would be very surprised if it is not already in-use
somewhere.
>[EMAIL PROTECTED] wrote:
>
> The assertion that this approach "changes the ground rules"
> because the "random stream of numbers vanishes" seems a little
> suspect.
>
> In any private-key stream encryption system -- including this one --
> the communicating parties can choose to either retain, or to destroy,
> information needed to re-generate at a future date the keystream used
> to encrypt and decrypt a given message.
>
> In a conventional system the key itself would be sufficient
> information, and hence is quite compact; in the proposed
> unbreakable system sufficient information would be the entire
> keystream actually used to encrypt the message -- much less
> compact, but still very practical to retain since it is only the
> size the message.
>
> So there is no "change in the ground rules" with respect to
> agency-imposed requirements to escrow or retain keys --
> just a larger amount of data needs to be escrowed or retained.
>
> Steve
--
==================================================================
Sundial Services :: Scottsdale, AZ (USA) :: (480) 946-8259
mailto:[EMAIL PROTECTED] (PGP public key available.)
> Fast(!), automatic table-repair with two clicks of the mouse!
> ChimneySweep(R): "Click click, it's fixed!" {tm}
> http://www.sundialservices.com/products/chimneysweep
------------------------------
From: Benjamin Goldberg <[EMAIL PROTECTED]>
Crossposted-To: sci.math
Subject: Re: Given any arbitrary numbers a and b.
Date: Thu, 22 Feb 2001 02:23:21 GMT
jtnews wrote:
>
> Since my previous post seemed to be not to clear
> to some people. Let me restate the problem another
> way which I hope will be simpler to understand.
>
> Given any arbitrary numbers a and b where a and
> b are NOT the same number.
>
> Can I ALWAYS find a transcendental number
> between a and b?
Sure.
Define p = Pi-3 (or any other transcendental between 0 and 1).
Then your result is
(p*(b-a)+a)
For some values of a, b, p, this result is not transcendental. If you
run into this problem, simply choose another transcendental value
between 0 and 1 for p.
Examples where p=Pi-3 fails:
a = 0, b = 1/(Pi-3)
a = 3-Pi, b = 4-Pi
If a and b are known to *not* be transcendental, this method never
fails.
If a and b are allowed to be transcendental, then you need to find a way
to test if (p*(b-a)+a) is transcendental, so you can try again with a
new value for p.
--
A solution in hand is worth two in the book.
------------------------------
From: [EMAIL PROTECTED] (TheBassCannon)
Date: 22 Feb 2001 02:39:09 GMT
Subject: FS: Koblitz, a course in number theory and cryptography
For Sale:
A Course In Number Theory and Cryptography
Second Edition
Neal Koblitz
Good condition, Paid $40 at Borders, Best Offer
Michael
------------------------------
From: Roger Schlafly <[EMAIL PROTECTED]>
Crossposted-To: sci.math
Subject: Re: Given any arbitrary numbers a and b.Can I ALWAYS find a
Date: Wed, 21 Feb 2001 18:51:03 -0800
Benjamin Goldberg wrote:
> > Given any arbitrary numbers a and b where a and
> > b are NOT the same number.
> > Can I ALWAYS find a transcendental number
> > between a and b?
> Sure.
> Define p = Pi-3 (or any other transcendental between 0 and 1).
> Then your result is
> (p*(b-a)+a)
That works fine if a and b are not transcendental. If one or both are,
then replace a and b with nontranscendentals between a and b.
------------------------------
From: Harvey Taylor <[EMAIL PROTECTED]>
Subject: Re: The Key Vanishes: Scientist Outlines Unbreakable Code, Read it and Weep
Boys
Date: Wed, 21 Feb 2001 21:49:11 -0800
[several folks wrote several things...]
I don't wish to bicker about copywrite.
>[...]
>The sender of a message and its recipient agree to start plucking a
>sequence of numbers from that string. They may agree, for example, to
>send a message, encoded with any of today's publicly available
>encryption systems saying "start" and giving instructions on capturing
>certain of the random numbers. As they capture the numbers, the sender
>uses them to encode a message, and the recipient uses the numbers to
>decode it.
>[...]
>
It seems to me, that seeing as everyone will have access to the
'endless' random bitstream, the security of the system reduces to
the security of the start message described above. Yes?
<l8r>
-het
--
"90 percent of _everything_ is crap." -Sturgeon's Law
Harvey Taylor mailto:[EMAIL PROTECTED] http://www.pangea.ca/~het
------------------------------
From: [EMAIL PROTECTED] (Vaughan Pratt)
Crossposted-To: sci.math
Subject: Re: Is there an algorithm to sequentially enumerate all transcendental
Date: 22 Feb 2001 04:02:17 GMT
In article <970n3o$[EMAIL PROTECTED]>,
Dave Seaman <[EMAIL PROTECTED]> wrote:
>In article <[EMAIL PROTECTED]>,
>Trevor L. Jackson, III <[EMAIL PROTECTED]> wrote:
>>Are there any non-diagonalization proofs?
>
>There are at least two, but both involve things that are more
>high-powered than diagonalization.
>
>One is the measure-theoretic proof. [...]
>
>Another comes from the Baire Category Theorem: [...]
I see the relevance to sci.math, but why does sci.crypt care?
Well, whatever. Here's a proof from logic. Every dense countable
linear order without least or greatest element is order isomorphic to
the rational line (or as a logician would put it, the first-order
theory of dense linear orders without endpoints is
aleph_0-categorical). The real line forms a dense linear order that is
sup-complete (every subset bounded from above has a sup or least upper
bound). The rational line is not sup-complete (the set of rationals
less than pi has no rational sup) and hence is not order isomorphic to
the real line. Hence the reals cannot be countable.
This leaves open the question of whether there is any alternative to
diagonalization that is just as elementary. Here's a proof I thought
of just now (which is no indication of novelty) whose deepest property
of the reals is that any cut in the real line is closed on one side and
open on the other.
Assume an enumeration x0,x1,... of the reals, and start with any finite
open interval, call it (x,x'). Step 1: Of the reals in the interval,
let x_i be the earliest in the enumeration, and shrink the interval to
(x_i,x'). Step 2: Let x_j be the earliest in (x_i,x') and further
shrink to (x_i,x_j). Alternate steps 1 and 2 for ever.
At every finite stage there remain infinitely many reals in the current
interval. Hence throughout the process both boundaries make continual
progress in advancing towards each other. But by countability every
real remaining in the interval must eventually be pulled out of it by
this process. The limit of this process therefore determines a cut in
the real line both sides of which are open (there is no greatest real
to the left of the cut and no least real to the right). But this is
impossible since any cut in the real line must have exactly one side
closed.
Vaughan Pratt
--
My mind and my body keep playing tricks on each other.
When I tell them to cut it out, they just say "Who are you?"
------------------------------
From: "Trevor L. Jackson, III" <[EMAIL PROTECTED]>
Subject: Re: New unbreakable code from Rabin?
Date: Thu, 22 Feb 2001 04:50:14 GMT
[EMAIL PROTECTED] wrote:
> If there were 2^1024 different keys of random data generated every week
> no one could store that week after week.
Do you have any idea how big 2^1024 is? There are about 2^263 particles in
the universe. If you count all of the photons there are about 2^273. If you
take the observable universe and divide it into the tiniest bits of space
possible (distinguishable positions) there are only about 2^700 places for
things to be.
2^1024 of _anything_ would require a larger universe. Much larger.
------------------------------
** 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 by posting to sci.crypt.
End of Cryptography-Digest Digest
******************************
