Cryptography-Digest Digest #910, Volume #9 Mon, 19 Jul 99 15:13:03 EDT
Contents:
Re: How to crack monoalphabetic ciphers (Fiji)
Cluelessness Alert? I'm Not So Sure. (latest Crypto-Gram) (John Savard)
Re: another news article on Kryptos (Jim Gillogly)
Re: another news article on Kryptos (Mok-Kong Shen)
Re: Math, Math, Math (Medical Electronics Lab)
Re: A Good Key Schedule (wtshaw)
Re: randomness of powerball, was something about one time pads (John Briggs)
Ring multiplier for GF(2^n) math (Medical Electronics Lab)
Re: randomness of powerball, was something about one time pads (Mok-Kong Shen)
Re: Cluelessness Alert? I'm Not So Sure. (latest Crypto-Gram) (wtshaw)
Re: another news article on Kryptos (wtshaw)
Re: another news article on Kryptos (Jim Gillogly)
Re: Traffic Analysis (wtshaw)
why is it that nowadays people have to protect their conversations ("Markku J.
Saarelainen")
Re: A Good Key Schedule (John Savard)
Re: Q. Passphrase Key-Rate Authentication (John Savard)
----------------------------------------------------------------------------
From: Fiji <[EMAIL PROTECTED]>
Subject: Re: How to crack monoalphabetic ciphers
Date: Mon, 19 Jul 1999 11:04:23 -0400
> In article <7ml50h$lnd$[EMAIL PROTECTED]>,
> [EMAIL PROTECTED] wrote:
> > How do you crack a monoalphabetic cipher? Thru freqeuncy analysis?
> > What if the plaintext had been compressed before encryption?
>
> If you are trying to crack straight-forward monoalphabetic ciphers, yes,
> you would use single letter frequency analysis.
You would actually you digram and trigram frequency analysis on
non-compressed monoalphabetic ciphers too. Look at the example in "The
Codebreakers". Kahn walks one through an example of cracking a
monoalphabetic cipher in which one almost definitely needs to use digram
frequencies.
-Fiji
>
> If it was compressed, I would perhaps try digram and trigram frequency
> analysis. Digrams are two-letter combinations, trigrams are three
> letter combinations. Since compression works by substituting single
> characters for digrams, trigrams, and higher, this might work.
>
> > Would a PRNG passed thru a non-linear (say SAFER style) sbox be secure
> > (if the sbox were private)?
>
> Yes, you could do frequency analysis on this also, unless I severely
> misinterpreted this. However, it would now be a polyalphabetic cipher,
> like vigenere. Granted, it would be a pain to crack, but it is
> possible. The PRNG has a period which can be determined, though I
> forget the name of the algorithm to do it. The sbox will not hide this
> fact, so if you XOR the output of the PRNG fed through the sbox and the
> plaintext, you have a complex, though still trivial, XOR cipher.
>
> > Tom
> > --
> > PGP key is at:
> > 'http://mypage.goplay.com/tomstdenis/key.pgp'.
> > Free PRNG C++ lib:
> > 'http://mypage.goplay.com/tomstdenis/prng.html'.
> >
> > Sent via Deja.com http://www.deja.com/
> > Share what you know. Learn what you don't.
> >
>
>
> Sent via Deja.com http://www.deja.com/
> Share what you know. Learn what you don't.
>
>
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Cluelessness Alert? I'm Not So Sure. (latest Crypto-Gram)
Date: Mon, 19 Jul 1999 15:39:02 GMT
I certainly do agree that the military can safely allow public
information to be stored on web sites on commercial hosts. However, I
have noted that a lot of military sites are actually on U.S.
Government-owned machines in the .mil domain.
And it is difficult, particularly using common commercially-available
operating systems and Internet hosting software, to maintain the kind
of impregnable security needed for any system that also contains
sensitive information.
There are ways of making an Internet server essentially immune to most
kinds of hacking. Macintosh servers, not having a CLI, appear to be
quite secure. But there are other techniques, most of which require
custom software and even custom hardware.
For example, to take an idea from the telephone company, how about a
computer with two CPUs. CPU number 1 is connected to the hard drive
containing the software for the computer, and has read-write access to
all of RAM. CPU number 2 is the one connected to the network. It has
read-only access to the chunk of memory from which it runs programs.
But it has read-write memory for storing data, and read-only access to
a hard drive containing the web site it is to present to the Internet.
If it also has data to store, it gets write access to a hard drive for
that purpose. The access is determined by *hardwired connections*, not
by operating system privileges which can be subverted.
In most operating systems, either the Microsoft ones or the Unix
clones, networking is part of the operating system, and the TCP/IP
connection to the Internet is part of that network. It has to be
explicitly limited in its privileges, and if someone gets
Administrator privileges/root access, that can be overturned. That
shouldn't happen, but any bug in the OS is a possible back door.
Now, suppose instead that the OS didn't even HAVE networking in it.
The port connected to the Internet was something the OS didn't even
know about, and everything that port did was under the control of one
unprivileged *applications program*. Even if the OS didn't even have
security - say it was MS-DOS - with precautions against such attacks
as buffer overrun, an applications program with narrowly focussed
capabilities could be quite secure.
If one doesn't go to these kinds of lengths, though, while it is true
that constant vigilance and the use of more conventional security
methods (i.e. firewalls) can give "pretty good" security, I think the
Pentagon is entirely justified in taking the attitude that the kind of
*ironclad* security they need just isn't available if one connects to
the Internet. I'm quite sure that the NSA or whoever could come up
with a "super-firewall" that could act as a public web-site host, and
yet be updated from within a highly sensitive computer network, with
safety. But it would take technologies like the two-CPU sketch above,
which just aren't available off the shelf. And it's off-the-shelf
technologies that have been used for much of the military's Internet
presence.
So while it is true there is a way for the military to stay on-line
and maintain security, it is also true that that is not immediately
available. Taking some web sites off-line until the vulnerabilities
can be remedied isn't a silly policy, even if there may be some
individual examples of cluelessness where sites involving no exposure
are taken down.
John Savard ( teneerf<- )
http://www.ecn.ab.ca/~jsavard/crypto.htm
------------------------------
From: Jim Gillogly <[EMAIL PROTECTED]>
Subject: Re: another news article on Kryptos
Date: Mon, 19 Jul 1999 10:22:00 -0700
Mok-Kong Shen wrote:
>
> Douglas A. Gwyn wrote:
> >
> > http://www.washingtonpost.com/wp-srv/national/daily/july99/kryptos19.htm
>
> I have a (very very) stupid question:
>
> Jim Gillogly has "tried on the order of 20 billion trial decryptions
> spread over two dozen different systems with perhaps 5 or 10 variations
> each, on average". If there were much more candidate systems and (known
> and less well-known or unknown) variations being tried, couldn't it
> happen that a decryption of a sufficiently short ciphertext becomes
> ambiguous, i.e. there would be more than one readable probable
> plaintexts? How can one go about to exclude such a possibility?
There are 97 characters in this cryptogram. The chance of having it
decrypt to two totally different plausible plaintexts is negligible.
The precise value of "negligible" is left as an exercise for the reader,
but I'll point out that 20 billion isn't a very big number as key spaces
go, and one doesn't expect that it would take more than two or three
8-byte blocks to nail down a 56-bit DES key beyond a shadow of a doubt.
--
Jim Gillogly
Mersday, 26 Afterlithe S.R. 1999, 17:14
12.19.6.6.14, 12 Ix 2 Xul, Eighth Lord of Night
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: another news article on Kryptos
Date: Mon, 19 Jul 1999 19:39:35 +0200
Jim Gillogly wrote:
>
> There are 97 characters in this cryptogram. The chance of having it
> decrypt to two totally different plausible plaintexts is negligible.
> The precise value of "negligible" is left as an exercise for the reader,
> but I'll point out that 20 billion isn't a very big number as key spaces
> go, and one doesn't expect that it would take more than two or three
> 8-byte blocks to nail down a 56-bit DES key beyond a shadow of a doubt.
I believe what you said is true, since one knows (or it can be
assumed) that the encryption was done with some 'classical' (very
old) methods. However, recently in another thread I put up the
following question: If one XOR the plaintext M_r with n plausible
messages M_1, ... M_n and a keystream K, how likely is one to find
the true message M_r? I conjecture that perhaps an analogous situation
could be envisaged with the 'classical' methods.
M. K. Shen
was
------------------------------
From: Medical Electronics Lab <[EMAIL PROTECTED]>
Subject: Re: Math, Math, Math
Date: Mon, 19 Jul 1999 11:55:35 -0500
David A Molnar wrote:
> Random not quite related question : does anyone look at P-completeness
> with respect to cryptography? for instance, showing that algorithm X is/is
> not inherently sequential?
More at fluid dynamics for that. A lot of numerical analysis is aimed
at finding parallel algorithms from known sequential ones.
Patience, persistence, truth,
Dr. mike
------------------------------
From: [EMAIL PROTECTED] (wtshaw)
Subject: Re: A Good Key Schedule
Date: Mon, 19 Jul 1999 12:24:51 -0600
In article <[EMAIL PROTECTED]>, [EMAIL PROTECTED] () wrote:
>
> Then after taking enough key from the stream to set up one encipherment
> step, what should be done is to subject that piece of the key to a one-way
> hash function. In this way, breaking one step in the encryption always
> yields a key that provides no exploitable clue to the keys used for the
> other steps.
>
If both or several keys are generated at the beginning, and an adequate
hash is used, solving one part should not help in solving any more. If
properly chained, however, it should be unlikely that any one link is
solved alone.
--
When I talk about running the bases, it't not baseball.
------------------------------
From: [EMAIL PROTECTED] (John Briggs)
Subject: Re: randomness of powerball, was something about one time pads
Date: 19 Jul 99 13:28:25 -0400
In article <[EMAIL PROTECTED]>, fungus
<[EMAIL PROTECTED]> writes:
> [EMAIL PROTECTED] wrote:
>> A simple way to analyze this is to use colored dice (RGB). Throw them
>> 216 times. Ignore the combinations and inspect the payoff from each die
>> independently. The red die matches your selection 36 times. Ditto for
>> the green and blue die. Total payback in $108 against $216 in bets.
>>
>> The house wins. Big.
>
> Completely wrong analysis....
Correct analysis. Wrong game. On the other hand, it is the game that
was originally described. Just not the game that was originally meant.
In the real game, you get your stake back with any winning bet.
John Briggs [EMAIL PROTECTED]
------------------------------
From: Medical Electronics Lab <[EMAIL PROTECTED]>
Subject: Ring multiplier for GF(2^n) math
Date: Mon, 19 Jul 1999 12:38:00 -0500
Joe Silverman is presenting a paper at the
upcoming CHES conference in Worchester which
describes a fast way to multiply over GF(2^n).
It only works on Type I ONB field sizes, but
it is a polynomial basis, not an ONB.
I think it's really slick because it's twice
as fast as an ONB multiply and inversion only
takes 2 or 3 multiply times (equivelent).
For anyone who wants to play with Ring math
multipliers, you can find code which implements
everything in Silverman's paper at the bottom
of my web page (file "ring.c"):
http://www.terracom.net/~eresrch
Please let me know of any bugs so I can fix them!
Patience, persistence, truth,
Dr. mike
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: randomness of powerball, was something about one time pads
Date: Mon, 19 Jul 1999 20:13:50 +0200
Douglas A. Gwyn wrote:
>
> Unbounded or open-ended games often hold surprises. For example,
> suppose you're matching coins against the (fair) house and double
> your bet each time you lose, starting with a $1 bet the first play
> and each time you won the previous play. Note that each time you
> win the play, you are $1 ahead for that "run" (losing streak, win).
> Evidently, you can make an arbitrarily large amount of money if
> you keep playing. What (if anything) is wrong with this "system"?
Maybe I misunderstood. But doesn't the issue call into memory
the case where an ideal RNG can generate a sequence of 0's of
arbitrary length? There is a non-zero chance that the time point
of (huge) win is at infinity.
M. K. Shen
------------------------------
From: [EMAIL PROTECTED] (wtshaw)
Subject: Re: Cluelessness Alert? I'm Not So Sure. (latest Crypto-Gram)
Date: Mon, 19 Jul 1999 12:39:15 -0600
In article <[EMAIL PROTECTED]>,
[EMAIL PROTECTED] (John Savard) wrote:
>
> And it is difficult, particularly using common commercially-available
> operating systems and Internet hosting software, to maintain the kind
> of impregnable security needed for any system that also contains
> sensitive information.
>
There is almost a non-brainer solution to the whole mess we sed: As far as
I can tell, there is no dynamic writing to static media, i.e., read-only
CD rom. It seems that a harddrive could also be configured in this
manner, that is, read-only. In fact, an actual switch could eliminate a
write command from being possible when it was being accessed.
Enable writing to the special disk when updating the website, otherwise,
have it physically impossible to change the contents. This would mean
going offline to change the contents, or switching between similiar drives
to allow working on one while the other was web-connected. This is a
practical solution which adds physical security were it is needed. The
government and others should do obvious things of this sort, and quit
trying to be some sort of stupid victim.
--
When I talk about running the bases, it't not baseball.
------------------------------
From: [EMAIL PROTECTED] (wtshaw)
Subject: Re: another news article on Kryptos
Date: Mon, 19 Jul 1999 12:54:06 -0600
In article <[EMAIL PROTECTED]>, Mok-Kong Shen
<[EMAIL PROTECTED]> wrote:
> Douglas A. Gwyn wrote:
> >
> > http://www.washingtonpost.com/wp-srv/national/daily/july99/kryptos19.htm
>
>
> I have a (very very) stupid question:
>
> Jim Gillogly has "tried on the order of 20 billion trial decryptions
> spread over two dozen different systems with perhaps 5 or 10 variations
> each, on average". If there were much more candidate systems and (known
> and less well-known or unknown) variations being tried, couldn't it
> happen that a decryption of a sufficiently short ciphertext becomes
> ambiguous, i.e. there would be more than one readable probable
> plaintexts? How can one go about to exclude such a possibility?
>
The chances of having multiple somethings readable fall rather fast with
increases in ciphertext lengths for simple ciphers. Jim's problem is one
of kind, figuring out what simple cipher and key were used.
I figure he knows of lots of possibilities for ciphers, more than most of
us, but falls short of the numbers of them that are known to NSA. As far
kinds of ciphers and associated possible keystructures, there are many
more than any of us could ever describe, and heaven knows; I try to
describe lots of them to prove that to a lesser degree.
On the cipher-busting side, luck and labor are the twin secret agents one
is normally forced to conspire with to attempt to solve the unknown
cipher. Good Luck, Jim.
--
When I talk about running the bases, it't not baseball.
------------------------------
From: Jim Gillogly <[EMAIL PROTECTED]>
Subject: Re: another news article on Kryptos
Date: Mon, 19 Jul 1999 11:22:26 -0700
Mok-Kong Shen wrote:
>
> Jim Gillogly wrote:
> >
>
> > There are 97 characters in this cryptogram. The chance of having it
> > decrypt to two totally different plausible plaintexts is negligible.
> > The precise value of "negligible" is left as an exercise for the reader,
> > but I'll point out that 20 billion isn't a very big number as key spaces
> > go, and one doesn't expect that it would take more than two or three
> > 8-byte blocks to nail down a 56-bit DES key beyond a shadow of a doubt.
>
> I believe what you said is true, since one knows (or it can be
> assumed) that the encryption was done with some 'classical' (very
> old) methods. However, recently in another thread I put up the
> following question: If one XOR the plaintext M_r with n plausible
> messages M_1, ... M_n and a keystream K, how likely is one to find
> the true message M_r? I conjecture that perhaps an analogous situation
> could be envisaged with the 'classical' methods.
Same answer as in all the other threads. If the key is random and as
long as the ciphertext and the method is XORing it, then you can have
any number of plausible plaintexts. While theoretically it's mildly
interesting (the first time), in this case it's not relevant, since
Scheidt says in the new article that he and Sanborn wanted the cipher
to be solvable. This means it does not have a random key as long as
the plaintext.
--
Jim Gillogly
Mersday, 26 Afterlithe S.R. 1999, 18:15
12.19.6.6.14, 12 Ix 2 Xul, Eighth Lord of Night
------------------------------
From: [EMAIL PROTECTED] (wtshaw)
Subject: Re: Traffic Analysis
Date: Mon, 19 Jul 1999 12:59:40 -0600
In article <[EMAIL PROTECTED]>, Mok-Kong Shen
<[EMAIL PROTECTED]> wrote:
>
> I don't know. But I know an opposite case, i.e. sending no bits
> instead of a lot. Quite a long time ago an European physicist was
> dismissed from his job because he was suspected to be involved in
> illegal work since his telephone at home was never used for a
> sufficiently long period. I was told that he was later rehabilitated.
>
Superiors question silence, which seems intimidating to those that know
less than the people who work for them, and well, makes them feel inferior
rather than superior. Some work best when left alone. A good supervisor
knows when to wait.
--
When I talk about running the bases, it't not baseball.
------------------------------
From: "Markku J. Saarelainen" <[EMAIL PROTECTED]>
Subject: why is it that nowadays people have to protect their conversations
Date: Mon, 19 Jul 1999 13:26:29 +0000
... why is it that nowadays people have to protect their conversations
from CIA's eavesdropping .. .. of course, this is because of CIA's
economic and business intelligence program that started late 1980's
against its allies for the benefit of some specific industrial
enterprises and corporations .... when they were talking about changing
their mission, this new mission has been followed for many years already
... do not believe what you hear from the mass media, popular news
sources or from some officials ... they are running the cover story in
most cases .. there are currently many CIA intelligence operations going
on .. some are pretending to be promoting and developing specific sales
and marketing business / market intelligence software applications for
specific companies for the benefit of some other enterprises ...sources
and methods .....excellent ..... in addition, there are software
companies that are actively involved in some specific CIA covert actions
and operations .... also there are total ghost businesses and
development groups that are shadowing specific businesses for the
benefit of certain industrial groups .... just focus on ownership
structures ... investment bankers and some technology providers ...
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: A Good Key Schedule
Date: Mon, 19 Jul 1999 18:49:51 GMT
Mok-Kong Shen <[EMAIL PROTECTED]> wrote, in part:
>Could you elaborate a bit. I am sorry that I haven't captured yet
>the most essential aspect of your post.
Well, I'm talking about how to use a passphrase to generate keys.
If I'm generating keys for several different cipher steps, the fact
that these different steps are getting keys from the same source
creates a weakness: break one step, and you have a clue to the key
used by the others.
By using hash functions in the keying process, I prevent the
cryptanalyst from working backwards from one key to get the other
keys.
John Savard ( teneerf<- )
http://www.ecn.ab.ca/~jsavard/crypto.htm
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: Q. Passphrase Key-Rate Authentication
Date: Mon, 19 Jul 1999 19:01:16 GMT
[EMAIL PROTECTED] (Christopher) wrote, in part:
>Point is, after going through all this I'd like to be sure it is the owner
>of the keyring and not just someone that knows the passphrase. What would
>be an unobtrusive way to include the owner's typing style/characteristics
>in the outermost cipher (the one protecting the keyring).
There's a fundamental limitation of biometrics that works against
this. While a computer program can certainly compare a person's
typing style with a template, and produce a yes/no answer, that's
because it will apply tolerances in a fancy, almost intelligent
manner.
Any scheme of assigning a code to a particular typing style,
therefore, won't produce the same code each time that user types.
There is a method that *might* work, though.
Let's say that a typing style is a point in a five-dimensional space.
So you have five numbers. No matter how you pre-define zones for those
five numbers, a user's typing style may just happen to be on the
boundary between two zones, leading to his typing style having more
than one hash code.
But if you include the _least significant bits_ for each of those five
dimensions, then you are constructing a set of zones whose centering
is adapted to the individual user. Then, if you produce a hash of the
most significant bits _of the differences, along each dimension,
between the user's typing style and the corresponding entry in the LSB
vector_, you *can* generate a unique code that the user will, by his
typing, produce most of the time.
John Savard ( teneerf<- )
http://www.ecn.ab.ca/~jsavard/crypto.htm
------------------------------
** 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
******************************
