Cryptography-Digest Digest #873, Volume #13 Mon, 12 Mar 01 14:13:01 EST
Contents:
Re: Potential of machine translation techniques? (Mok-Kong Shen)
Re: Popularity of AES (Dan Hargrove)
Re: Really simple stream cipher ("Paul Pires")
Re: OverWrite: best wipe software? (William Hugh Murray)
Re: Zero Knowledge Proof (Neil Couture)
Re: Dayton's Code Breakers (Jim Haynes)
Re: Quantum Computing & Key Sizes ([EMAIL PROTECTED])
Re: Super strong crypto ("Douglas A. Gwyn")
Re: Super strong crypto ("Douglas A. Gwyn")
Re: Noninvertible encryption ("Douglas A. Gwyn")
Re: Digital enveloppes (Tony L. Svanstrom)
Re: Potential of machine translation techniques? (Joe H. Acker)
Re: Zero Knowledge Proof ("Paul Pires")
Re: Exportable key lengs & Mush algorithm (Stefek Zaba)
Re: Quantum Computing & Key Sizes ([EMAIL PROTECTED])
Re: Zero Knowledge Proof (Richard Wash)
Re: theory edge mailing list (Quisquater)
----------------------------------------------------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Potential of machine translation techniques?
Date: Mon, 12 Mar 2001 18:44:19 +0100
"Joe H. Acker" wrote:
>
> Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
>
> > "Douglas A. Gwyn" wrote:
> > >
> > > No, you'd be better off with a code system.
> >
> > It is meant to be a parallel supplementary path. It
> > could help encryption. A new language implies also a
> > new vocabulary, hence it is (much) more than a code
> > system.
>
> If you mean just a new vocabulary but no changes in morphosyntax, you
> have a code book that translates each word of the pt language into a ct
> language. However, some regularities at word and sentence level can
> still be exploited. For a completely different language, you'd need a
> different grammar as well. In WWII, it was a reasonable assumption that
> the dialects used by the native speakers were not well known or secret
> to German linguists and cryptanalysts. But as the Indian languages did
> not contain enough military vocabulary, they used codebooks as well.
> Here's a sample (taken from Wrixton 1989, 1992, 1998):
>
> TERM COMANCHE MEANING COMMANCHE (transcribed)
> enemy enemy tu-wa-ho-na
> machine gun sewing machine techa-keena
> soldier red-stomach ex-sha-bah-nah
>
> But: This does only make cryptanalysis harder, if the language is
> unknown or not exlored well enough and the code is secret to the
> attacker. So your artificial languages have to be secret. But if you can
> keep an artificial language secret like a key, you can use a complete
> codebook as well. However, if the code does map to words of the pt
> language, it's less secure than an artificial language if the artificial
> languages has different letter, digram, trigram, etc. frequencies than
> the pt language. But you can also chose a code that has different
> frequencies than the pt language. But anyway, if the code really is
> secret, it doesn't matter because you don't even need to encrypt it. You
> just add encryption for the very likely case that the code is partially
> known. But if it is not secret at all, I'd guess it can only improve
> security by changing pt frequencies of any kind. In this case, I'd say
> "flattening the frequencies" by homophonic substitution like discussed
> in the other thread might be the best code.
>
> Regarding codebooks, I have two questions:
>
> (1) To eliminate regularities at word or sentence level, the code does
> not only have to do word substitution but also mix up the word order
> based on a key. How do you do that cryptographically secure? I'd like to
> use a conventional block cipher or secure hash for that.
>
> (2) You'd want to create a codebook on the fly based on a key. How do
> you do that?
>
> Here's what I mean by question (2): Suppose you have a dictionary D_1
> and another dictionary D_2. You have a key K for a conventional block
> cipher. Now you want to map each entry of D_1 uniquely to D_2 using K.
> The inverse operation should be as hard as possible without K, but easy
> with K.
>
> I'm especially interested in the case D_1 = D_2, i.e. I'd like to take a
> large dictionary and map entries from it to other entries of it and vice
> versa. How can I use a conventional block or stream cipher or hash
> function to do that securely? Seems I need to use the cipher to yield
> dictionary indices between 1..i, but how do I do that?
An arbitrary bijective mapping of D1 to D2 can be effected
by doing a pseudo-random permutation of D2 (that originally
correspond 1-1 to D1) using a PRNG seeded by a secret 'key'.
Does that answers your questions?
The grammar of the artificial language gives additional
complexity to the opponent. As said, the intention is
a parallel path to encryption. There is nothing against
the texts in the artificial language being further
encrypted by an encryption algorithm (including eventual
use of homophones), if desired.
M. K. Shen
------------------------------
From: [EMAIL PROTECTED] (Dan Hargrove)
Subject: Re: Popularity of AES
Date: 12 Mar 2001 18:06:28 GMT
[EMAIL PROTECTED] (John Savard) wrote in
<[EMAIL PROTECTED]>:
>On Mon, 12 Mar 2001 09:33:29 +0100, Mok-Kong Shen
><[EMAIL PROTECTED]> wrote, in part:
>
>>Does anyone know why AES is not
>>on the list? Thanks.
>
>Could be because the AES spec is not yet finalized and official, so
>the best they could have done would be to put Rijndael on the list.
AES is included with the new version of PGP. There must be some
specifications for it.
Dan
------------------------------
From: "Paul Pires" <[EMAIL PROTECTED]>
Subject: Re: Really simple stream cipher
Date: Mon, 12 Mar 2001 10:03:51 -0800
Paul Crowley <[EMAIL PROTECTED]> wrote in message
<snip>
> Entirely agreed! In my case, Scott has actually proposed fixes to my
> cipher that would address the problems he found, but I'm still very
> wary of proposing a new version until I'm sure I've rooted out the
> deep problems with the cipher.
I think the part people skip is in fact, very important but I
need to get a little Zennish to get it accross. All that we invent,
discover and design exists in perfection BEFORE our creative
act. Design isn't changing the world, it is changing us and our
own perceptions. The sculpers quote comes to mind, "The form
is already in the stone...Just remove that which is not the form."
The biggest thing I learned from pancho's attack was that
there was an undocument self-confusion function in my brain.
I saw the same thing he did. Many times. Each time I saw
it I said to myself, "Oh don't do that". Then one time I peeked
at it and for some reason thought that it wasn't a problem,
saw how it improved the performance and embraced it
as brilliance.
It doesn't take time to learn the lesson, it takes time stop
looking at the code and figure out what defective internal
process caused it so that learning can take place. At least
that's the way it works for me.
Paul
------------------------------
From: William Hugh Murray <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Crossposted-To: alt.hacker
Subject: Re: OverWrite: best wipe software?
Date: Mon, 12 Mar 2001 18:07:16 GMT
Mok-Kong Shen wrote:
> Benjamin Goldberg wrote:
> >
> [snip]
> > If I've got data on a floppy, and I want it securely erased, I copy the
> > stuff I want to save to a new floppy, and burn the old one. Floppies
> > are cheap. The cost of buying new floppies is lower than the security
> > risk of downloading binaries from your website.
>
> Removable media, since they are now all quite cheap, should
> be physically destroyed for preventing recovery. For hard
> disk drives there are firms specialized in recovering deleted
> data.
Yes, there are but hard drives are cheap too. The first hard drive I ever
purchased cost me $3K- for 10Megs. The first one I ever sold was thousands
of dollars per meg and was the size of a refrigerator. Today I can buy
100Gigs for the same price with a computer thrown in. How cheap must a drive
be for one to recommend its destruction? Seems to me we have passed the
threshold. If the value of the residual data is so high that someone might
be willing to pay a lab to recover it, then a few whacks with a sledgehammer
or running it over once or twice with one's SUV seems like a good
investment. Make the calculation in terms of the replacement cost of the
drive, not its original purchase price.
> According to posts in the group long back, overwriting
> a couple of times isn't secure. I remember also reading a
> newspaper article saying that a firm succeeded to recover
> most of the informations stored on hard drives of a lab
> that were demaged by fire.
>
> M. K. Shen
------------------------------
From: Neil Couture <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Subject: Re: Zero Knowledge Proof
Date: Mon, 12 Mar 2001 18:23:43 GMT
I never red the book Applied Cryptography by Schneier, ( sorry ! i red
Menezes, Stinson and a few books on number theory, ... and of course Secret
and lies from Schneier ), does he talk about ZN proof in his book?
Mok-Kong Shen wrote:
> > Gustavo Brown wrote:
> >
> > Can you tell me where to find info about Zero Knowledge Proof, and
> > its relationship with Cryptography.
>
> The stereotype answer is to look into textbooks, e.g. that
> of Schneier.
>
> M. K. Shen
------------------------------
Subject: Re: Dayton's Code Breakers
Reply-To: [EMAIL PROTECTED]
From: [EMAIL PROTECTED] (Jim Haynes)
Date: Mon, 12 Mar 2001 18:25:45 GMT
If you want to look into this further, here are some of Desch's patents.
All the U.S. patents are on-line at www.uspto.gov; but for these old ones
you can only search by patent number.
2,403.852 Electronic device... 1946
2,399,473 Electronic device... 1946
2,401,621 Electronic accumulator
2,404,697 Calculating device
2,419,485 Electronic device 1947
2,425,307 Communication system
2,432,608 Multianode gas-filled...
2,451,812 Electron tube variable impulse...
2,462,613 Communication system 1949
2,467,257 Electronic remote control
2,556,614 Electronic impulse counting 1951
2,595,045 Calculating machine 1952
2,598,764 Electron tube counting device
2,644,087 Electronic impulse generator 1953
2,644,110 Electronic counter
2,644,111 Electronic counter
2,644,112 Electronic counter
2,717,334 1955
2,871,408 Electronic counter 1959
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Quantum Computing & Key Sizes
Date: 12 Mar 2001 10:31:59 -0800
[EMAIL PROTECTED] (Bill Unruh) writes:
> Who knows. Quantum Computers do not exist. Their speed is thus not even
> speculative. As I said, you need about a 1 million bit computer to
> factor a 1000 bit number.
Where did you get this figure? I am not a physicist, but according to
http://xxx.lanl.gov/ps/quant-ph/9802065, the memory space needed is
proportional to log N, i.e. proportional to the length of the modulus.
So I would assume it would be on the order of thousands of qubits, not
a million.
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: Super strong crypto
Date: Mon, 12 Mar 2001 18:20:45 GMT
Mok-Kong Shen wrote:
> "Douglas A. Gwyn" wrote:
> > Mok-Kong Shen wrote:
> > > I am afraid to define and qualtify 'propagation of
> > > information' is a task that is practically imfeasible in
> > > the rigorous sense (which a formal treatment requires),
> > > otherwise one could as well also decide whether a given
> > > bit source is perfectly random.
> > I don't understand your reasoning at all.
> Sorry, I had a typo: 'qualify' should read 'quantify'. Is
> that clear to you now?
No, that didn't bother me. But I don't follow your reasoning.
How would a theory of information propagation through a system
allow one to decide whether a given bit source is perfectly
random? That doesn't seem right to me.
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: Super strong crypto
Date: Mon, 12 Mar 2001 18:14:56 GMT
Bryan Olson wrote:
> If you have some result showing Rijndael is flawed, or
> showing your scheme is strong, that would be significant.
> Hypothesizing Rijndael is weak and conjecturing that your
> scheme would fix the weakness is not even in the direction
> you stated this thread seemed to be about.
That isn't what I was doing.
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: Noninvertible encryption
Date: Mon, 12 Mar 2001 18:25:37 GMT
"Henrick Hellstr�m" wrote:
> Why not? Maybe it was intended to be used as an OTP.
It wouldn't seem reasonable to encrypt a OTP key.
------------------------------
Subject: Re: Digital enveloppes
From: [EMAIL PROTECTED] (Tony L. Svanstrom)
Date: Mon, 12 Mar 2001 18:44:04 GMT
Tom St Denis <[EMAIL PROTECTED]> wrote:
> "br" <[EMAIL PROTECTED]> wrote in message news:[EMAIL PROTECTED]...
> > What I have to do to patent it?
>
> Why not share your idea first.
Because then he can't patent it...
/Tony
------------------------------
From: [EMAIL PROTECTED] (Joe H. Acker)
Subject: Re: Potential of machine translation techniques?
Date: Mon, 12 Mar 2001 19:40:34 +0100
Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
> An arbitrary bijective mapping of D1 to D2 can be effected
> by doing a pseudo-random permutation of D2 (that originally
> correspond 1-1 to D1) using a PRNG seeded by a secret 'key'.
> Does that answers your questions?
Not entirely. I was thinking about that but I don't know how to do it.
Suppose I use a 128 bit block cipher as PRNG but only have 2^16 entries
in my dictionary. How do I map from the 128 bit to 16 bit without
collisions? Is it safe to just use the first 16 bit of the PRNG output?
In practise, I have an arbitrary size dictionary that always has less
entries than the 128 bit output can address. How would this be solved?
BTW, you could create a context-free grammar for your artificial
language pseudo-randomly based on a key as well...
Regards,
Erich
------------------------------
From: "Paul Pires" <[EMAIL PROTECTED]>
Subject: Re: Zero Knowledge Proof
Date: Mon, 12 Mar 2001 10:44:21 -0800
Neil Couture <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> I never red the book Applied Cryptography by Schneier, ( sorry ! i red
> Menezes, Stinson and a few books on number theory, ... and of course Secret
> and lies from Schneier ), does he talk about ZN proof in his book?
Yep. (Applied Cryptography) He he even supplies drawings for members
of the crayon crowd like me. Section 5.1
Paul
>
>
>
> Mok-Kong Shen wrote:
>
> > > Gustavo Brown wrote:
> > >
> > > Can you tell me where to find info about Zero Knowledge Proof, and
> > > its relationship with Cryptography.
> >
> > The stereotype answer is to look into textbooks, e.g. that
> > of Schneier.
> >
> > M. K. Shen
>
------------------------------
From: [EMAIL PROTECTED] (Stefek Zaba)
Subject: Re: Exportable key lengs & Mush algorithm
Date: 12 Mar 2001 18:40:26 GMT
In sci.crypt, Randy Langer ([EMAIL PROTECTED]) wrote:
> Two questions for the group:
> 1) What is tha actual key length restriction for export now? I've heard
> every possible stoty on this now (40 bits, 56, 128, unlimited), and no
> compelling reason to believe one over the others.
Ass-U-ming you're talking software, the closest correct answer is "unlimited",
either (1) *after* you've received a classification from the BXA, (2) once
you've just *submitted* a classification request *if* you're exporting to
end-users in the European Union + 8 further Favoured Nations, or (3) if you
make the source code publicly available, and you've notified the BXA of its
availability no later than when you export.
But it's not as simple as that. Rather than take as authoritative anything
you read here, go to the source:
http://www.bxa.doc.gov/Encryption/Default.htm
Read the guidance notes, phone the listed contacts for clarification, get
your company's tame legal types to help you do the compliance thing in the
way most consistent with your responsibilities as a US-based (I assume!)
corporate and with your business model. Your responsibilities for your
company's livelihood would make it rather poor judgment to base your
compliance advice on something you think you saw here on Usenet...
Stefek
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Quantum Computing & Key Sizes
Date: 12 Mar 2001 10:56:46 -0800
Tom McCune <[EMAIL PROTECTED]> writes:
> In article <[EMAIL PROTECTED]>, [EMAIL PROTECTED] wrote:
> >
> >These kinds of equivalence calculations require making assumptions on
> >the type of attack used against the public key algorithm. Quantum
> >computers would provide for different kinds of attacks and so the
> >equivalence would not hold.
>
> Are these different kinds of attack theoretical possibilities only at this
> point, or are there good reasons to believe they are probable? Any
> reasonable implication as to how key sizes with such newly available attacks
> would relate to current attacks? Such as 16k QC (new attack) equating to 4k
> "conventional" attacking? I hope that question makes sense.
The new QC-based attack on factoring and discrete logs is called
Shor's algorithm, and there has been a great deal of theoretical
analysis on it. Nevertheless, because quantum computers don't exist
for other than a trivial number of bits, there is no way to know for
sure if they will actually be able to attack large problems.
Broadly speaking, the number of steps to factor a 16K bit key would be
on the order of 16,000 ^ 3, or about 4 trillion. This is a very small
work factor compared to attacks we consider with ordinary computers,
perhaps equivalent to an RSA key of 200-250 bits. However it is
impossible to say whether QCs will operate anywhere near as fast as
present-day computers in terms of cycle times.
The bottom line is that to be conservative, quantum computers must be
considered to make the RSA, DSS and DH keys used by PGP to be useless.
> I should have phrased that better. Would this be a matter of breaking a
> 2048 bit key in an hour, and a 4096 bit key in 8 hours, or more like
> breaking a 2048 bit key in a week, and a 4096 bit key in 2 months?
It depends on the cycle time of the QC. If you had nanosecond cycle
times you could conceivably break keys of this size in under an hour.
If you had one-second cycle times it could take centuries. It's just
not possible to say now how fast QC's will work, or if they will work
at all.
------------------------------
From: Richard Wash <[EMAIL PROTECTED]>
Subject: Re: Zero Knowledge Proof
Date: 12 Mar 2001 14:02:28 -0500
"Gustavo Brown" <alegus#QUIT_THIS#@adinet.com.uy> writes:
> Hi:
>
> ��� Can you tell me where to find info about Zero Knowledge Proof,
> and its relationship with Cryptography.
>
> What I need is some info concerning how Zero Knowledge Proof is used
> within Cryptosystems, etc
Zero Knowledge Proofs are a very interesting topic.
The original paper on Zero Knowledge Systems (zks) is
"The Knowledge Complexity of Interactive Systems"
By Goldwasser, Micali, and Rackoff
@inproceedings{gmr,
author = "S. Goldwasser and S. Micali and C. Rackoff",
title = "The Knowledge Complexity of Interactive Systems",
booktitle = "Proceedings of the 17th Annual ACM Symposium on the
Theory of Computing",
year = "1985",
pages = "291-304",
}
A good place to look for more information on Zero Knowledge Proofs is
in the cryptography textbook
Cryptography: Theory and Practice
By Douglas Stinson
I found this reference very useful for learning about ZKS.
ZKS are frequently used as authentication mechanisms in cryptographic
systems. A good reference is a paper by Schnorr:
@article{schnorr,
author = "C. Schnorr",
title = "Efficient Signature Generation for Smart Cards",
journal = "Journal of Cryptology",
year = "1991",
volume = "4",
pages = "161-174",
}
Also, look at the sections on "Zero Knowledge Proofs of Knowledge" and
"Zero Knowledge Proofs of Identity" in Schneier's "Applied
Cryptography".
Finally, I recommend a search through an article listing of the
Lecture Notes in Computer Science for "zero knowledge". You will come
up with a large number of papers on the topic.
Hope this Helps,
Rick Wash
------------------------------
From: Quisquater <[EMAIL PROTECTED]>
Subject: Re: theory edge mailing list
Date: Mon, 12 Mar 2001 20:10:15 +0100
Very interesting list indeed. A lot of problems and people, and problems
between people and people between problems. You also need
to understand how to use kill files and everything then is OK.
The moderator needs to know what it is moderation :-)
There are no enough words in english to explain what I mean.
A good experiment for the Rabin-Maurer system (more random noise
in a day you can memorize in a life). :-)
There are competition and parallel lists, dissidence and so: it's life
(you know, my list is better because we have more members ...:
membership is a very important problem in NP-complete instances).
A life experiment in NP-complete problems, where NP sometimes
means No Pertinent, sometimes No Problem. Is spam a NP-complete problem?
Last question: classical signature (by hand) is more watermarking or more
digital signature?
------------------------------
** 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
******************************
