Cryptography-Digest Digest #857, Volume #10 Thu, 6 Jan 00 19:13:01 EST
Contents:
Re: frequency analysis with homophones (Mok-Kong Shen)
Re: Please Comment: Modified Enigma (John Savard)
Re: frequency analysis with homophones (John Savard)
Re: Unsafe Advice in Cryptonomicon (Andrew Woodward)
Re: How to pronounce "Vigenere"? (Dan Day)
Re: Anagram (Dan Day)
Re: Please Comment: Modified Enigma ([EMAIL PROTECTED])
Re: Please Comment: Modified Enigma ([EMAIL PROTECTED])
Re: Wagner et Al. (lordcow77)
Re: AES wise? (Albert Yang)
Re: Square root attacks against DSA? (DJohn37050)
Re: Truly random bistream (Scott Nelson)
Re: MARS (Albert Yang)
Re: How about this for a "randomly" generated bitstream? (Guy Macon)
----------------------------------------------------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: frequency analysis with homophones
Date: Thu, 06 Jan 2000 22:14:07 +0100
r.e.s. wrote:
>
> I posted this problem in a couple of *.math groups about a week ago,
> but so far there has been no "solution".
>
> The context is cryptanalysis of a substitution cipher which we
> suppose to be "monoalphabetic" and "homophonic". Specifically,
> for any given letter of plaintext -- suppose there are I different
> such letters -- any one of J different ciphertext symbols is
> substituted at random. We envision this as a table-lookup in which
> row(i) of the table contains the J possible substitutes for letter(i)
> of the plaintext alphabet, and we suppose the I plaintext letters
> (rows) occur with probabilities p(i), i=1..I.
Do you mean each of the I letters is mapped to J letters and J
is a constant? That wouldn't give you a good homophone substitution.
The higher frequency letters of the I letters should have
proportionately more substitutes than the low frequency one such
that the entire set of the output letters have more or less equal
frequencies. Because of the discrete nature you can't arrange to
have exact equality of output frequencies. Nor is this necessary
in practice, since your frequency data are normally obtained from
some 'representative' text file but you particular piece of message
to be encrypted may more or less deviate from that in frequencies
anyway.
To achieve the said 'approximate' equality of output letter
frequencies is not difficult. It only involves some trial-and-error
computation work.
If instead of 'monoalphabetic' you employ 'polyalphabetic'
homophonic substitutions and the number of columns of the
substitution table is large enough, you might in my humble view
even relax to some extent the frequency equality requirement of
each column.
M. K. Shen
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: Please Comment: Modified Enigma
Date: Thu, 06 Jan 2000 14:27:23 GMT
Paul Crowley <[EMAIL PROTECTED]> wrote, in part:
>I'm working on an alternative, currently called "Mirdek".
After looking at Solitare again, it occurred to me that instead of
just scrambling the deck a little bit, by a counted cut, one could do
a complete columnar transposition of a deck with little more trouble,
and the operation would even *look* like playing Solitare.
Thus, I've been thinking of a key generation method that would, like
yours, use only the standard 52 cards and no jokers, but its
elementary step would operate like this:
Step 1: From the prepared deck (the order of the cards in it is the
key), turn up, and deal out face up in a row, successive cards until
the total of the cards (A=1, J=11, Q=12, K=13) is 8 or more.
Step 2: If the last card dealt out in Step 1 is a J, Q, or K, take its
value, otherwise take the total of the values of the cards dealt out
in Step 1. (This gives a number from 8 to 17.) In the next row, deal
out that many cards from the top of the deck.
Step 3: Deal out the rest of the deck under that row, in successive
rows that begin on the left, and end under the lowest card in the top
row, the next lowest card in the top row, and so on, in rotation. A
red card is lower than a black card of the same denomination, and when
there are two cards of the same color and denomination, the first one
in the row is considered lower.
Step 4: Take the cards dealt out in Step 3, and pick them up by
columns, starting with those under the lowest card in the row dealt
out in Step 2. The top card in the column is to be on the bottom of a
pile of face up cards, and the first column picked up is to be on the
bottom of the re-assembled deck.
Step 5: Place the cards dealt out in Step 2 (the last one on the
bottom) in face-up form on top of the re-assembled deck, and then the
cards dealt out in Step 1, again, the last one on the bottom of a face
up pile put on top of the re-assembled deck.
Step 6: Turn the deck of cards over to face-down position to repeat
Step 1.
After doing this three times, obtain a keystream digit as follows:
Looking at the cards from the top of the deck, ignore all J, Q, and K
cards; take the first other card, from A to 10, and count down that
many cards to find a card from A to 10. Do the same from the bottom of
the deck. The last digit of the sum of the values of those two cards
is the keystream digit.
This way, people don't have to memorize a bridge ordering of the
suits, and they use a straddling checkerboard to allow false addition
to apply the key, instead of trying to do Vigenere or modulo-26
arithmetic in their heads. (I'm trying to make it more secure and
easier to do at the same time.)
The method of transposition used is the one given by General Luigi
Sacco, that breaks up a block into uneven units, and which perhaps has
some advantages over ordinary columnar transposition.
Of course, some of the rules used mean that there are biases in the
transposition; if every card had a distinct value, the order of the
columns would be slightly more random, and the rule intended to limit
the row size to 17 instead of 21 makes 11, 12, and 13 more likely row
lengths. Note that Step 4 is set up to make the scrambling invertible,
so I did accept some good advice from Bruce Schneier's Solitare.
The thorough transposition should allow a keying procedure that is
somewhat simpler than that used with Solitare. But using the order of
letters in a word, while throwing away their identities, would make
the required keyphrase longer, so this will still take some thought.
John Savard (jsavard<at>ecn<dot>ab<dot>ca)
http://www.ecn.ab.ca/~jsavard/crypto.htm
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: frequency analysis with homophones
Date: Thu, 06 Jan 2000 14:30:19 GMT
[EMAIL PROTECTED] (David Wagner) wrote, in part:
>This suggests defining a `Measure of Similarity' between s and t by
>computing (say) a chi-squared test of similarity for the distributions
>D(u) = Prob[su] and D'(u) = Prob[tu], and then trying to group the
>ciphertext symbols into equivalence classes that maximize the total
>measure of similarity.
Yes, this is the key step to attacking homophonic ciphers by frequency
analysis, even if the similarity might be measured by eye instead of
mathematically in most cases.
John Savard (jsavard<at>ecn<dot>ab<dot>ca)
http://www.ecn.ab.ca/~jsavard/crypto.htm
------------------------------
From: [EMAIL PROTECTED] (Andrew Woodward)
Subject: Re: Unsafe Advice in Cryptonomicon
Date: 06 Jan 2000 21:47:32 GMT
>Steve K wrote:
>In the situation, though, I would be >most concerned about someone >making a
>very high definition recording the >RF noise with a *really good* set
>of detector circuits, each >custom-tuned to listen to individual
>components: the serial bus and >motherboard cache would be good
>targets. Of course, the process of >recovering the actual data being
>processed would be far from easy, >in the case mentioned, and I can
>believe that the morse trick would >work if nobody had published it...
>
>Dang.
>:o))
It may not be tuning that is necessary but timing. Although, that might be
what you are talking about. If you know when the screen buffer is being read
you might be able to work backwards in time as data travels through one
computer component at a time. This of course depends on if only one component
at a time is actually making noise, I'm more of a programmer than an engineer
so I don't know if that is true.
This broader kind of Van Eck phreaking could be combated against as well by
having all of your data encrypted constantly, even if it is just extra noise,
or by using obscure programs with weird data formats.
Andrew
Student
Baltimore MD
------------------------------
From: [EMAIL PROTECTED] (Dan Day)
Subject: Re: How to pronounce "Vigenere"?
Date: Thu, 06 Jan 2000 21:53:34 GMT
On Tue, 4 Jan 2000 00:29:08 -0500, [EMAIL PROTECTED] (Michael Groh)
wrote:
>I know this is a silly question, but I don't speak French and I'm giving
>a paper that references the Vigenere cipher. I've never heard this name
>pronounced, having only read about it in many different sources.
Hell, I have that same problem with a lot of words in English (and
English is my first language). That's the problem with doing a lot
of reading in my younger years -- I was first introduced to many words
via print, not speech.
I still recall the day when I first discovered that the written "chaos"
and the spoken "kay'os" were the same word...
--
"How strangely will the Tools of a Tyrant pervert the
plain Meaning of Words!"
--Samuel Adams (1722-1803), letter to John Pitts, January 21, 1776
------------------------------
From: [EMAIL PROTECTED] (Dan Day)
Subject: Re: Anagram
Date: Thu, 06 Jan 2000 22:03:39 GMT
On Tue, 04 Jan 2000 00:33:34 -0600, "John E. Gwyn" <[EMAIL PROTECTED]>
wrote:
>at a time, but probably you're just asking for a single random
>shuffle. That's not hard:
> input in array string[1..N]
> for i from 1 to N-1
> j = random integer in range [i,N]
> swap string[i] and string[j]
> output in array string[1..N]
You want "from 1 to N" in that "for" loop, not "N-1".
For a demonstration that your method doesn't give the desired
results, consider a 100 character string. The only chance
that string[100] has of being moved out of its original
location is if any of the first 99 swaps happen to "hit" it
in the "j = random" line.
The probability of any one pass through the loop "hitting"
string[100] are 1/100. The probability that all 99 passes
"miss" string[100] are (1-1/100)^99, or 0.3697.
In other words, your method would leave the final character
in a 100 character string right where it began 37% of the time.
Needless to say, a proper shuffle would only have a given character
end up where it started 1% of the time in a 100 character string.
--
"How strangely will the Tools of a Tyrant pervert the
plain Meaning of Words!"
--Samuel Adams (1722-1803), letter to John Pitts, January 21, 1776
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Please Comment: Modified Enigma
Date: Thu, 06 Jan 2000 22:18:40 GMT
First, I already build the proposed 'machine', which was somehow
timeconsuming and you better make the paper circles 10cm in
diameter and be *precise*. You then rotate the circles around
a pin on a paper sheet. It is obviously more simple to use an encoding
scheme with a very limited number of letters like arabic/greek/latin..
(drawing 26 equal sectors onto the rotor is already difficult..)
Also, I did not use the original engima 'reflector', as it seemed to
be too complex/errorprone to me. I did not think about the
cipherletter-never-plainletter issue, but this is a good justification
to be lazy :-))
>A key determines which of the
> set of plates out of a large number are to be used.
This seems to be an inferior concept compared to mine, as you greatly
limit the number of rotor permutations. One traitor who supplies the
disks and General Hayden will successfully apply his acres of computing
power..
If you want to give tools to your troops, better give them a plug-wired
rotor or metallic disks with equal sectors that can be labelled in the
field.
Also, this makes life more comforable for the poor cipher boy who has to
carry the equipment :-)
>Shortly afterwards, however,
> the Chinese government banned its use, for pretty the same reason as
> underlying nowadays key-escrows, Wassenaar Agreement etc., (which can
> thus be said to have a fairly long historical justification).
Maybe they had doubts about it's strength.. (see abovbe)
Regarding the PalmPilot-Argument: If you are *super-paranoid* you may
fear the electromagnetic emanations of your 'Pilot being monitored..
I guess our friends at NSA already looked at supra-cooled antennas and
SQUIDs... And please do not dream the dream of LCD drivers being
undetectable.
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Please Comment: Modified Enigma
Date: Thu, 06 Jan 2000 22:19:28 GMT
First, I already build the proposed 'machine', which was somehow
timeconsuming and you better make the paper circles 10cm in
diameter and be *precise*. You then rotate the circles around
a pin on a paper sheet. It is obviously more simple to use an encoding
scheme with a very limited number of letters like arabic/greek/latin..
(drawing 26 equal sectors onto the rotor is already difficult..)
Also, I did not use the original engima 'reflector', as it seemed to
be too complex/errorprone to me. I did not think about the
cipherletter-never-plainletter issue, but this is a good justification
to be lazy :-))
>A key determines which of the
> set of plates out of a large number are to be used.
This seems to be an inferior concept compared to mine, as you greatly
limit the number of rotor permutations. One traitor who supplies the
disks and General Hayden will successfully apply his acres of computing
power..
If you want to give tools to your troops, better give them a plug-wired
rotor or metallic disks with equal sectors that can be labelled in the
field.
Also, this makes life more comforable for the poor cipher boy who has to
carry the equipment :-)
>Shortly afterwards, however,
> the Chinese government banned its use, for pretty the same reason as
> underlying nowadays key-escrows, Wassenaar Agreement etc., (which can
> thus be said to have a fairly long historical justification).
Maybe they had doubts about it's strength.. (see abovbe)
Regarding the PalmPilot-Argument: If you are *super-paranoid* you may
fear the electromagnetic emanations of your 'Pilot being monitored..
I guess our friends at NSA already looked at supra-cooled low-noise,
high-gain antennas and SQUIDs...
And please do not dream the dream of LCD displays being
undetectable.
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: lordcow77 <[EMAIL PROTECTED]>
Subject: Re: Wagner et Al.
Date: Thu, 06 Jan 2000 14:38:13 -0800
On a properly administered Windows NT system, to say nothing of *nixes,
a trojan will not have the access rights neccesary to modify system
files, access files which the ACLs forbid, enter the memory space of
another process, or intercept system messages or events not intended
for it. It's a pretty difficult task to get a NT system that secure,
especially if you have any type of reasonable server install, but it's
entirely doable in a day or two (unless you burn disk images onto CD
<grin>).
* Sent from RemarQ http://www.remarq.com The Internet's Discussion Network *
The fastest and easiest way to search and participate in Usenet - Free!
------------------------------
From: Albert Yang <[EMAIL PROTECTED]>
Subject: Re: AES wise?
Date: Thu, 06 Jan 2000 22:52:05 GMT
I can think of at least one clear reason; and that is the fact that if
you have purely dependent S-boxes, then you might have a biased in the
strength of the algorithm in terms of what key is used because the
S-boxes produced might not efficiently or optimally diffuse in a
non-linear fashion. If that then becomes true, then you're algorithm is
not as strong all across the keyspace. That would then mean you "might"
have weak keys. That then would be bad.
Albert
------------------------------
From: [EMAIL PROTECTED] (DJohn37050)
Subject: Re: Square root attacks against DSA?
Date: 06 Jan 2000 22:57:23 GMT
Attack the r value using Pollard rho, which can then be used to discover the
private key from s.
Don Johnson
------------------------------
From: [EMAIL PROTECTED] (Scott Nelson)
Subject: Re: Truly random bistream
Reply-To: [EMAIL PROTECTED]
Date: Thu, 06 Jan 2000 23:16:36 GMT
On Thu, 06 Jan 2000 20:08:15 GMT, Bob Silverman <[EMAIL PROTECTED]> wrote:
>In article <[EMAIL PROTECTED]>,
> [EMAIL PROTECTED] wrote:
>> TohuVohu <[EMAIL PROTECTED]> wrote:
>> It /may/ not be impossible. It's just that nobody knows whether it's
>> possible or not.
>>
>> : Isn't radioactive decay "random" enough for this.
>>
>> Perhaps, perhaps not. It depends on your "this" - since the original
>> poster did not specify an application and instead asked after a
>"truly"
>> random bitstream
>
>Yep! There is also the question of how to define "random enough".
>
>- an entity whose existence some regard in much the same
>> light as they would a perpetual motion machine.
>
>Yep!
>
>
>> Even if radioactive decay /were/ perfectly random,
>
>Some physicists (John Wheeler for example) have presented arguments
>which suggest that time itself is quantized (the minimum unit of time
>is the time for light to cross the Planck length). Under this
>circumstance it is impossible to get a 'truly' random *continuous*
>distribution. One can only get an approximation.
>
>> there is no known way
>> of amplifying it to a macroscopic scale while demonstrably avoiding >
>>every possibility of non-random influence from the
>
>Indeed. Seeing common sense prevail is so refreshing!
>
>The time between decay events is NOT a uniform random variable. It
>follows an Erlang distribution (Exponential waiting time). Now if
>you want to use this as a source for a UNIFORM (Bernoulli bit stream)
>one must introduce a transformation. There are then two sources of
>possible error: [maybe more?]
>
>(1) We can not measure the time between events sufficiently accurately.
>(2) We can not compute the non-linear transform with "true" [i.e.
>infinite) precision.
>
>Both introduce bias that forces a deviation from "true" uniform
>randomness.
Consider a conventional method for distilling randomness from
radio-active decay. Pick a convenient time interval,
like 1 second, and count the number of ticks in that interval.
Then count the number of ticks in the next time interval compare.
If there are more events during the first interval,
call that a 1, if there a fewer, it's a 0.
If they're equal, then discard both measurements
and try again.
Since most sources of error are present in both
measurements, they cancel and produce 0 bias.
The only things for which that is not true are
those which change over time;
The radioactive source "slows down", there is ware
on the detector, the universe is expanding, etc.
While it's true that these things introduce
bias, from a practical standpoint, it's negligible.
And if that bias isn't low enough for you,
then you can further process the data digitally,
and make it as low as you like.
Scott Nelson <[EMAIL PROTECTED]>
------------------------------
From: Albert Yang <[EMAIL PROTECTED]>
Subject: Re: MARS
Date: Thu, 06 Jan 2000 23:33:04 GMT
I agree with you. Mars I don't trust in terms of security; so right off
the bat they are out in my book. RC6 is clean, and easy to remember,
but it doesn't fit well in things like smartcards etc... And also, when
you get off the 32 bit platform, it's performance drops dramatically.
Twofish and Rijndael both are close to RC6 in terms of speed, and both
fit in 8 bit devices well. Rijndael is based off square, and fairly
new, so that's what I think it might have against it, otherwise a great
algorithm. Twofish seems a bit complex. Serpent is slow compared to
the twofish and rijndael. But it's overly conservative, which is a good
thing in the crypto world IMHO, and so it has a chance based on it's
security margain. Also, those 3 are all free, which means I can use it
without royality, which makes me smile.
The strong points of each:
RC6 ~ small compact code, difficult to screw up, has a well analysed
pedigree (RC5) and is fairly fast in 32 bits.
Twofish ~ Fast, and VERY flexible, fits in everything.
Rijndael ~ Fast, good use of primatives, and higly parallelable, and
probably very easy to migrate to a 64 bit version very efficiently.
Serpent ~ Well understood, very conservative, great safety margain.
Again, I personally don't see Mars having any advantage over the others
here.
Albert
------------------------------
From: [EMAIL PROTECTED] (Guy Macon)
Subject: Re: How about this for a "randomly" generated bitstream?
Date: 06 Jan 2000 18:55:10 EST
In article <[EMAIL PROTECTED]>, [EMAIL PROTECTED] (Tim Tyler) wrote:
>
>Scott Nelson <[EMAIL PROTECTED]> wrote:
>: On 05 Jan 2000 21:35:17 EST, [EMAIL PROTECTED] (Guy Macon) wrote:
>
>:>I know hardware, and I am very confident that I can achieve a 99.X%
>:>[99.9? 99.99? 99.999?], and that I will never be able to prove 100%.
>:>Folks who know crypto better than I do tell me that they can not prove
>:>that 99.X% is good enough for certain crypto uses.
>:
>: 99.999999999999% is pretty easy to achieve if you're willing
>: to spend some time collecting and hashing the data.
>
>Such figures appear fantastic to me - at least when cryptographic
>application is being discussed.
>
>If the oppenent can get any access to the stream it is immediately
>non-random, since given "n" bits of the stream, the opponent can predict
>the net and previous bits.
>
>Similarly you have to guard against the opponent being able to influence
>the generated stream, since if he can gain access he can /easily/
>substitute a pseudo-random stream with a very low entropy content that
>nevertheless passes all the best tests for randomness available.
>
>Any figure put on the entropy content of a stream intended for
>cryptographic purposes should figure this sort of thing into the
>equation somewhere, IMO - at the very least as a measure of confidence
>in the entropy figure.
>
>Can you be 99.999999999999% confident that your opponent has not
>surreptitiously substituted his own PRNG for your own system of hashes?
>
>If not how can you claim with any certainty that you have an entropy
>content of 0.99999999999999? Is it not possible that you're hypnotised,
>in the presence of a magician, or that your assistant is an enemy agent?
As a hardware engineer, it is my practice to attempt to quantify such
things, and I did run the numbers and the estimated chance of all of
the things you mentioned and more. I am very confident that I can
achieve a bit stream that is between 99.9% and 99.999% random.
These are real numbers from someone who is experienced in these sort
of calculations and estimations, and I stand by my estimate.
------------------------------
** 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
******************************
