Cryptography-Digest Digest #364, Volume #11 Sun, 19 Mar 00 12:13:01 EST
Contents:
Re: recognizing English text (ca314159)
Crypto books ("version_x")
Re: Card shuffling (Tim Tyler)
Re: Card shuffling (Jim Reeds)
Re: Crypto books (TomGelin)
Re: how to introduce hs students to cryptography (TomGelin)
Re: SHA-1 as a stream cipher (Michael K)
Re: sci.crypt Cipher Contest (Nick Tamer)
Re: recognizing English text ([EMAIL PROTECTED])
Re: Looking for a special one way function (David A. Wagner)
Re: Card shuffling ("Amical")
Re: new Echelon article (David A. Wagner)
Voynich: plain text or code ? (ca314159)
Re: NIST, AES at RSA conference (D. J. Bernstein)
Re: Improvement on Von Neumann compensator? (Scott Nelson)
Re: Card shuffling (DMc)
----------------------------------------------------------------------------
From: ca314159 <[EMAIL PROTECTED]>
Subject: Re: recognizing English text
Date: Sun, 19 Mar 2000 12:37:23 GMT
Samuel Paik wrote:
>
> Eric Lehman wrote:>
> > I'd like to write a program that takes a block of ASCII characters and
> > decides whether or not the block is a snippet of English text. For
> > example:
> >
> > j2fk@30v0$ -> output "no"
> > ke to writ -> output "yes"
> >
> > My program need not be perfect, of course, but I'd like it to be pretty
> > good. Any thoughts about how I could go about this? Is a hairy heap of
> > horrific heuristics unavoidable?
>
> Here's an idea: build a high order context model (say order 5 or so)
> and use this to estimate the entropy of the text. If it is too high,
> call it not english. See _Text Compression_ by Bell, Cleary, and Whitten
> or _The Data Compression Book_ by Nelson and Gailley.
> --
> Samuel S. Paik | http://www.webnexus.com/users/paik/
> 3D and multimedia, architecture and implementation
> You dont know enough about X86 or kernel architectures to argue with me.
> - <38b2dc12$0$[EMAIL PROTECTED]> "Leon Trotsky" to Terje Mathisen
'Text Compression' is a good book. I think I remember it has some
examples of generating pseudo-text. As a way of testing a model,
it should be able to generate pseudo-text that looks similar to
what one wants to spot. I've seen source code on the web for
generating english pseudo texts at some of the AI/speech sites,
Carnegie Mellon,...
http://www.google.com/search?q=generating+pseudo+text&sa=Google+Search
news:comp.speech
--
http://www.bestweb.net/~ca314159/
------------------------------
From: "version_x" <[EMAIL PROTECTED]>
Subject: Crypto books
Date: Sun, 19 Mar 2000 21:11:56 +0800
i'm trying to get started in cryptography and have am looking for books
which would suit a beginner,
i have already bought Applied Cryptography by bruce s. but have found it
pretty hard going, understading wise.
is anyone aware of any books which are more beginner oriented or should i
try and stick with applied cryptography.
rees.
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: Card shuffling
Reply-To: [EMAIL PROTECTED]
Date: Sun, 19 Mar 2000 13:41:56 GMT
Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
: Tim Tyler wrote:
:> Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
:> : The new problem is now how to 'measure' randomness and that
:> : involves further the (difficult) problem of defining 'randomness'.
:> : Of course, we want something that is 'practical' not the stuffs of
:> : the pedantic people who demand (absolute) perfectness. But I am
:> : yet ignorant of anything that could be useful in that direction.
:>
:> Knuth made serious attempts to both formally define randomness, and to
:> present statistical tests that attempted to measure deviations from it,
:> in TAOCP v.2.
:>
:> These seem applicable to shuffling - since a good shuffle represents a
:> sequence where at any point the next card in the deck is chosen at random
:> from those not yet dealt.
:>
:> There are various ways of turning the information in a shuffled pack into
:> a what would be a genuinely random sequence - *if* the shuffle was a
:> random permutation in the first place.
: My reading of Knuth's book is certainly not deep. But I am fairly
: sure that he doesn't give a (practical) 'measure' of 'randomness'.
: There are a number of tests described. But there is no single
: numerical value that can be computed and taken as the (standard)
: measure of 'randomness' comparable to the measures obtained
: in physics.
You /could/ define a quantity representing the shortest program in a
specified language that produced the sequence - and call the ration
of the length of this program to the length of the sequence a measure
of the randomness, with respect to that language.
The problem with such a metric is that it's *totally* impractical to
compute - due to a combination of vast resources required and the halting
problem.
Knuth's tests *are* practical - in that you can actually perform them.
If you want a single figure that detects every type of deviation from
randomness, you *still* have to work with respect to some descriptive
language - since what is random from one POV may be ordered from another
one - and calculation of your metric /very/ rapidly becomes intractable.
: If I use a very poor PRNG to obtain a permutation according to the
: method of Durstenfeld, is that permutation 'random' or not? [...]
Not.
--
__________
|im |yler The Mandala Centre http://www.mandala.co.uk/ [EMAIL PROTECTED]
Talk is cheap - but using a modem can get expensive.
------------------------------
From: [EMAIL PROTECTED] (Jim Reeds)
Subject: Re: Card shuffling
Date: Sun, 19 Mar 2000 13:48:30 GMT
In article <[EMAIL PROTECTED]>, Mok-Kong Shen <[EMAIL PROTECTED]>
writes:
|> ... However, if one person on a specific session of the game
|> shuffles a deck, could we say how well (effective) that deck
|> has been shuffled?
You might as well ask how to tell if one particular page
of a one-time-pad is effective. Or even, how effective
the first line of digits on the page are. Or even, how
random the first digit is? You are asking, in effect,
if one can tell if the digit '6' is as random as the digit
'7'. (Some people would say 'no'.) In the binary case, you
are asking, can one tell if the bit '0' (when used as
an XOR key) is as effective as the bit '1'? Sci.crypt is
the right forum to answer this question, as it comes up about
twice a week here.
I think the sensible question is: does the method of production
of these objects (bits, digits, one time pads, permutations)
come close to producing uniformly distributed items?
And to make 'come close' precise, one should consider how
much of a sample size would be needed to distinguish between
the actual distribution and the desired uniform distribution.
--
Jim Reeds, AT&T Labs - Research
Shannon Laboratory, Room C229, Building 103
180 Park Avenue, Florham Park, NJ 07932-0971, USA
[EMAIL PROTECTED], phone: +1 973 360 8414, fax: +1 973 360 8178
------------------------------
From: [EMAIL PROTECTED] (TomGelin)
Subject: Re: Crypto books
Date: 19 Mar 2000 13:56:38 GMT
Try Aegean Park Press, they have a whole series on classic cryptography. You
kind of started to run berfore you could crawl. Applied Cryptography is an
explanation of algorithms for various encryption processes. If you don't
understand base 2 you will have a problem with most of the explanations. Most
of the algorithms utilize a bit shifting, permutating, compression, expansion,
modulo, S-box, and EOR (exclusive or) process. Not real difficult to understand
but almost humanly impossible to utlize. You need a computer to implement any
of the encryption processes. Classical Cryptography utlizes substitution and
transposition in multiple fashions. It's a good place to start for the basics.
There is an organization called the ACA (American Cryptographic Association)
http://www.und.nodak.edu/org/crypto/crypto/ go there for more info.
------------------------------
From: [EMAIL PROTECTED] (TomGelin)
Subject: Re: how to introduce hs students to cryptography
Date: 19 Mar 2000 14:07:03 GMT
If you can review Bruce Schneiers book Applied Cryptography you'll get a great
deal of information with regard to computer encryption process. There are many
algorithms utilized in various encryption methods. A good place to start is
analyzing the 16 rounds of the DES (Data Encryption Standard). Studying the
Feistel network is excellent for understanding algorithms. You may want to
cover some of the old classical cryptographic methods. A book by Helen Fouche
Gaines is probably the best price wise that you can purchase. Also try
contacting the American Cryptographic Association
http://www.und.nodak.edu/org/crypto/crypto/. Good Luck. You can e-mail me at
[EMAIL PROTECTED]
------------------------------
From: Michael K <[EMAIL PROTECTED]>
Subject: Re: SHA-1 as a stream cipher
Date: Sun, 19 Mar 2000 09:23:56 -0500
Thanks!
Mike
(Yes, 160 bytes not bits. oops.)
On Sun, 19 Mar 2000 00:12:24 -0800, "Steve A. Wagner Jr."
<[EMAIL PROTECTED]> wrote:
>this question has been posted recently by someone else. you suggest
>using sha in ofb mode. output feedback where any algorithm keeps
>encrypting its state and uses that to xor with the plaintext.
>
>here's a better way:
>1. begin with a 20byte riv.
>2. hash=sha(riv+key)
>3. ciphertext=[xor hash with first plaintext block (20 bytes)]
>4. hash=sha(ciphertext+key)
>
>5. and so on until end of file.
>
>--SAW
>
>Michael K wrote:
>
>> Does anyone have any thoughts on using SHA-1 as a stream cipher?
>>
>> I'll clarify...
>>
>> Lets say you have a block of data to encrtypt....
>>
>> D = data to encrypt
>> K = hash of user input password
>>
>> DO
>> -------------------------------------------
>> xor the next 160 bytes of D with K (one byte at a time)
>> -------------------------------------------
>>
>> then...
>>
>> K = hash of K
>>
>> LOOP (until data is completely encoded)
>>
>> Any thoughts/ideas would be great.
>>
>> Thanks,
>>
>> Mike K
------------------------------
From: Nick Tamer <[EMAIL PROTECTED]>
Subject: Re: sci.crypt Cipher Contest
Date: Sun, 19 Mar 2000 15:28:11 +0100
Why "Math RiZK" ? Because at the end you find the Key
;-)
Quisquater wrote:
> Maybe it's time to see at
>
> http://cryptonessie.org
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: recognizing English text
Date: 19 Mar 2000 14:18:45 GMT
In a previous article, ca314159 <[EMAIL PROTECTED]> writes:
> 'Text Compression' is a good book. I think I remember it has some
> examples of generating pseudo-text. As a way of testing a model,
> it should be able to generate pseudo-text that looks similar to
> what one wants to spot. I've seen source code on the web for
> generating english pseudo texts at some of the AI/speech sites,
> Carnegie Mellon,...
You are absolutely right. So if the model is used for looking for plain text
as part of a brute force/related key attack, you must make sure that the
model is not included in the cipher algorithm. If it is, decryption will
always result in english pseudo text regardless of which key you are using.
E.g. our SpellMaker component encodes plain text (at least partly) with this
effect. If you are trying to decode such code without the correct dictionary,
you will need to apply a grammar control and a frequency analysis of words to
spot english text.
----- Posted via NewsOne.Net: Free Usenet News via the Web -----
----- http://newsone.net/ -- Discussions on every subject. -----
NewsOne.Net prohibits users from posting spam. If this or other posts
made through NewsOne.Net violate posting guidelines, email [EMAIL PROTECTED]
------------------------------
From: [EMAIL PROTECTED] (David A. Wagner)
Subject: Re: Looking for a special one way function
Date: 19 Mar 2000 06:14:16 -0800
In article <8aocs6$ql1$[EMAIL PROTECTED]>, <[EMAIL PROTECTED]> wrote:
> Assume f is the one way function, the computation cost of f is C.
> Xi+1 = f(Xi)
> Generally, compute Xn from X1 needs computation cost (n-1)C, which is in
> the order of O(n). Here is my question: Is there any one way function
> that can computer Xn from X1 at a cost of O(1) or O(lgn)?
Maybe, but if so, it's not collision-free.
See http://www.cs.berkeley.edu/~daw/my-posts/iterable-hash
If you'll accept a one-way function with a trapdoor, so that
anyone who knows the trapdoor can compute f^n() quickly (but
can also invert f()), yet without the trapdoor you can only
compute f() efficiently, consider squaring mod n, where n is
a RSA modulus.
------------------------------
From: "Amical" <[EMAIL PROTECTED]>
Subject: Re: Card shuffling
Date: Sun, 19 Mar 2000 15:03:27 GMT
Have you considered a Kendall test between the initial permutation
and the permutation after suffling ?
------------------------------
From: [EMAIL PROTECTED] (David A. Wagner)
Crossposted-To:
alt.politics.org.cia,alt.politics.org.nsa,talk.politics.crypto,alt.journalism.print,alt.journalism.newspapers
Subject: Re: new Echelon article
Date: 19 Mar 2000 06:31:13 -0800
In article <[EMAIL PROTECTED]>,
Douglas A. Gwyn <[EMAIL PROTECTED]> wrote:
> However, they *have* been tasked with helping protect the
> "information infrastructure", which is a legitimate national
> security interest that happens to contribute to our economic
> well-being as well as being of importance for other reasons.
It's a shame, given this mission, that the NSA has been such
a force for _in_security in, e.g., the design of the US cellular
telephony infrastructure. I think there is some reason to be
skeptical about the NSA's commitment to protecting information
infrastructure, given their past record.
------------------------------
From: ca314159 <[EMAIL PROTECTED]>
Subject: Voynich: plain text or code ?
Date: Sun, 19 Mar 2000 15:41:07 GMT
[EMAIL PROTECTED] wrote:
>
> In a previous article, ca314159 <[EMAIL PROTECTED]> writes:
> > 'Text Compression' is a good book. I think I remember it has some
> > examples of generating pseudo-text. As a way of testing a model,
> > it should be able to generate pseudo-text that looks similar to
> > what one wants to spot. I've seen source code on the web for
> > generating english pseudo texts at some of the AI/speech sites,
> > Carnegie Mellon,...
>
> You are absolutely right. So if the model is used for looking for plain text
> as part of a brute force/related key attack, you must make sure that the
> model is not included in the cipher algorithm. If it is, decryption will
> always result in english pseudo text regardless of which key you are using.
>
> E.g. our SpellMaker component encodes plain text (at least partly) with this
> effect. If you are trying to decode such code without the correct dictionary,
> you will need to apply a grammar control and a frequency analysis of words to
> spot english text.
I remember reading about a speech recognition experiment in
which children were trained to read spectrograms and say the
words in them. They did very well.
This suggests that converting the text to speech using a voice
synthesizer and then piping the speech through some thick foreign accent
flanging dynamic time warping algorithm or worse, to make it readable
only by some specially trained children might make an effective encryption.
Even better, have the whole plain text metaphorically (semantically)
encrypted so that it reads like a children's story and that will help
make the children's work alittle more pleasureable. Don't forget
to throw in a few puns and some esoteric references :)
Are neural-nets still notorious for not divulging what they've
learned ? Can you now ask a trained neural net to tell you some
statistical information it's learned, like digram frequencies
or do they still encrypt their learning in the net as a bunch
of undecipherable/seemingly meaningless node weights ?
I watched a computer technician fixing someone's PC. The person
said to the technician: "Wait, let me write down what you are doing
so the next time this happens I can fix it." He replied, "Don't
do that, I don't know what I'm doing yet. Wait until I'm done and then
I'll tell you what to do." (I have enough problems finding the
right plugs for the wires in my PC. They all seem to be hideously
encoded, three prong, left-handed, male to female,...
And software compatibility ! Now there's a code. Try cracking
MS's code.)
But similar with quantum computers it seems. You can't disturb it
while it's working. Only when the wavefunction collapses do you
get an answer (not necessarily the one you expected).
Back in the Expert System days, a bunch of people went through the
offices to download the expert's expertise. What a doomed project.
Not only because of job preservation, but even those who were willing,
couldn't put into simple terms their hard earned experience which
had been encoded into instincts that lay beyond words. Hard in, hard out.
Cryptography has that same sense of the economy, any winning
algorithm is short lived and compensated for. Something to do
with thermodynamics no doubt.
Maybe a fractal code, text embedded into a picture and you need
the right initial conditions to find it. Chaos theory: if you
don't know what the butterfly in Moscow is doing, you don't get
the message.
Strange how the body keeps all its signals in order, and can
recognize foreign genetic codes like viruses. Without effective
codes the body is doomed. Orthogonality. Discrimination without
prejudice.
What would the leviathans of politics be without their codes ?
The Voynich Manuscript (a language or a code ?):
http://search.yahoo.com/bin/search?p=voynich
------------------------------
From: [EMAIL PROTECTED] (D. J. Bernstein)
Subject: Re: NIST, AES at RSA conference
Date: 19 Mar 2000 15:37:03 GMT
Terry Ritter <[EMAIL PROTECTED]> wrote:
> If you get to decide that a cipher is no good unless it has
> mathematically proven security, you should apply that criteria to the
> other side as well, in which case there is no good cipher.
On the contrary. The Mauborgne cipher provably protects against
eavesdropping, given one key bit per message bit. Wegman-Carter MACs
provably protect against forgery, given just 128 key bits per message.
Why, then, does anyone bother with secret-key systems that aren't
provably secure? Because key bits are expensive---so expensive that we
are willing to abandon provable security for the sake of a shorter key.
Apparently that isn't a concern for you. You've made clear that you
don't care about cost. So you can have mathematically proven security.
---Dan
------------------------------
From: [EMAIL PROTECTED] (Scott Nelson)
Subject: Re: Improvement on Von Neumann compensator?
Reply-To: [EMAIL PROTECTED]
Date: Sun, 19 Mar 2000 16:14:43 GMT
On Fri, 17 Mar 2000 17:22:05 GMT, Tim Tyler <[EMAIL PROTECTED]> wrote:
>: Use Twofish to crypt the first 16 bytes with a fixed key.
>: XOR the output with the key and the next 16 bytes,
>: and crypt again. Repeat until all bytes are used.
>
>To clarify - you're describing a hash function - i.e. previous blocks
>are discarded, and only the final block is output?
>
Yes.
>And you're claiming this construct is "balanced" - i.e. for all possible
>inputs (with a size of some specified number of blocks), it produces
>all possible outputs with exactly equal frequency?
>
Yes.
>Can you demonstrate that - or explain why it might have this property?
>
Yes.
Since Twofish has a 1 to 1 mapping from the input to the output,
if it's fed all possible input texts for the last block,
it must produce all possible output texts. In other words,
the last block can cause the output to be any and every value.
Since the blocks are combined with another 1 to 1 function (XOR)
any previous block can change the output to any possible value
as well.
>*Any* cryptologically strong hash function need not exhibit the property
>in question.
>
It's certainly not a requirement, but it's not prohibited either.
And in the special case of hashing as a method for distilling
entropy from noise, it's not necessary for the hash function
to be cryptographically strong. Strong hash functions are
usually used, but for reasons unrelated to the distillation
of entropy.
>However *some* types of strong hash function /may/ offer it - though I
>don't personally know of any that do.
>
>: I don't think SHA1 has this property, but I do believe
>: it's flatter than a "random" hash would be. (a hash
>: that maps inputs to outputs at random).
>
>After briefly looking at it's innards, I can't see why it would be.
>
Because it's based on a cryptographic process which
is by necessity balanced.
>: But even with a "random" hash we'd expect all 2^160
>: possible input strings to hash to 2^160/e output strings
>: - a loss of less than 1.5 bits, or .991 "real" bits per
>: bit.
>
>Yes. I don't think the problem is a terribly practical one.
>
>Hashing a totally random stream does not generally produce another
>totally random stream, though.
That depends on what is meant by "totally" random.
An unbiased stream, correctly processed by a hash function
will result in another unbiased stream, so in that
sense, it is random.
However, the new stream obviously won't be unrelated to
the first stream, so in that sense, it's not random.
Scott Nelson <[EMAIL PROTECTED]>
- Don't forget to vote on sci.crypt.random-numbers
------------------------------
From: DMc <[EMAIL PROTECTED]>
Subject: Re: Card shuffling
Date: Sun, 19 Mar 2000 16:55:25 GMT
On Sun, 19 Mar 2000 11:42:40 +0100, Mok-Kong Shen
<[EMAIL PROTECTED]> wrote:
>>
>>DMc wrote:
>>
>>My understanding is Diconis theorized about the first seven
>>riffles starting with an ordered card deck. Many subsequent math
>>persons and card book authors decided this meant one has to riffle
>>a card deck at least seven times between deals to insure "real"
>>randomness. I call it the seven shuffle theory, and I think it
>>hogwash. I think Diconis would not agree with this bald extension
>>to his theory.
>
>Would a deck successively shuffled by seven persons have the
>same quality (some degree of satisfaction from the point of
>view of the players) independent of the persons doing the
>shuffling, i.e. whether these are veteran players or novices or
>young kids?
>
>I think one could plausibly entertain doubts to any positive answer
>to that.
>
First I visualize 2, 3, 4, 5, 6, or 7 players with a new card deck
just out of its box. Then 7 neighborhood children are invited in to
riffle that deck once each. Then an eighth child cuts the deck. Then
you, an eleventh through sixteenth person present, would plausibly
entertain doubts about this process. I think you are having me on.
Personally, I learned at an early age to put a new card deck on a
convenient flat surface and thoroughly mix the cards around. This
was before I could count to seven.
Seriously, I think you might see card deck randomness as one true
path only. I suggest it is the overwhelming multitude of possible
paths. What you might fruitfully do is figure out ways to riffle
and cut a card deck which produce non-random results.
[EMAIL PROTECTED]
------------------------------
** 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
******************************
