Cryptography-Digest Digest #104, Volume #9 Thu, 18 Feb 99 19:13:03 EST
Contents:
Re: Telephone Encryption ("Trevor Jackson, III")
Re: Randomness of coin flips (Patrick Juola)
Re: Telephone Encryption (R. Knauer)
Re: True Randomness (R. Knauer)
Re: Help! Cryptosystem needed. (Michael Kjorling)
Re: New high-security 56-bit DES: Less-DES (Bryan Olson)
Re: True Randomness (R. Knauer)
Re: newbie algorithim thoughts (Jason S Hackney)
Re: Randomness of coin flips (R. Knauer)
The Hunt Is ON !!! @ PAWS !!! (Richard Goldman)
Re: Bruce's Feb. "CRYPTO-GRAM" (John Savard)
----------------------------------------------------------------------------
Date: Thu, 18 Feb 1999 16:05:37 -0500
From: "Trevor Jackson, III" <[EMAIL PROTECTED]>
Subject: Re: Telephone Encryption
Paul Rubin wrote:
> In article <[EMAIL PROTECTED]>,
> R. Knauer <[EMAIL PROTECTED]> wrote:
> >>The chips are now called "Fortezza". They no longer have the
> >>"Law Enforcement Access Field" that was so controversial.
> >
> >Are there any commercial telephones being made with that technology?
>
> Fortezza is actually a pcmcia card. It's mostly been used in the
> Defense Messaging System for SBU (sensitive but unclassified)
> traffic, from what I understand. I thought it used the Capstone chip
> which is a successor to Clipper. I didn't realize it had no LEAF.
>
> Last year the Skipjack and KEA algorithms used in Capstone were
> declassified so it became ok to implement them in software or smart
> cards. This was apparently because the Fortezza cards were so
> expensive, they couldn't buy enough of them for the DMS.
>
> The whole point of Clipper for civilian use was the LEAF. So
> there's no particular reason to use it without the LEAF.
>
> If you're looking to buy high quality secure phones I probably can put
> you in touch with a guy who has been making some very nice ones at
> about $1000 each. Email me if you want this.
>
> If you're looking for something cheap for occasional use, try one
> of the software programs.
I'm interested in your secure phone contact. Please send details.
------------------------------
From: [EMAIL PROTECTED] (Patrick Juola)
Subject: Re: Randomness of coin flips
Date: 18 Feb 1999 13:07:43 -0500
In article <[EMAIL PROTECTED]>,
R. Knauer <[EMAIL PROTECTED]> wrote:
>On 18 Feb 1999 08:56:23 -0500, [EMAIL PROTECTED] (Patrick Juola)
>wrote:
>
>>Well, *IF* -- and I'm cheerfully hypothesizing in blissful ignorance
>>here -- *IF* Ms. So's coin flipping technique tends to put an even
>>number of flips on the coin, then she will observe that the bigrams
>>HH and/or TT tend to dominate over HT and TH. This means that
>>she'll see longer than expected runs.
>
>I fail to see how the regularity of having the "expected" amount of
>bias present is a measure of true randomness. It may be a measure of
>pseudo-randomness, but that is not appropriate to secure crypto.
It's not. But *failure* to have the expected amount of bias
present is almost certainly a measure -- and a mark -- of a lack of
randomness.
-kitten
------------------------------
From: [EMAIL PROTECTED] (R. Knauer)
Subject: Re: Telephone Encryption
Date: Thu, 18 Feb 1999 22:12:28 GMT
Reply-To: [EMAIL PROTECTED]
On Thu, 18 Feb 1999 19:33:46 GMT, [EMAIL PROTECTED] (Paul Rubin) wrote:
>If you're looking to buy high quality secure phones I probably can put
>you in touch with a guy who has been making some very nice ones at
>about $1000 each. Email me if you want this.
My interest is only passing - I wanted to see where the state of the
art was today.
>If you're looking for something cheap for occasional use, try one
>of the software programs.
I suppose you could build a single board computer from industrial
grade parts and implement the software on it in a dedicated fashion.
Put it in a very small brief case and it would look very cool,
especially with some randomly blinking lights and maybe a small
display panel spitting out messages like "secure uplink engaged now"
or some such techno babel.
It sure as hell would impress the ladies, eh. Used to be you could
attract turned-on women with just a Captain Midnight Decoder Ring, but
women are getting much more demanding these days.
Bob Knauer
"The first principle of a civilized state is that power is
legitimate only when it is under contract."
--Walter Lippmann
------------------------------
From: [EMAIL PROTECTED] (R. Knauer)
Subject: Re: True Randomness
Date: Thu, 18 Feb 1999 22:26:25 GMT
Reply-To: [EMAIL PROTECTED]
On Thu, 18 Feb 1999 11:52:34 -0800, Michael Sierchio <[EMAIL PROTECTED]>
wrote:
>Okay, so where are we? There's a self-referential problem if
>you define true randomness (TR) as that which has no regularity --
>you can't test for it, because passing the test means failure,
>and failing the test means nothing. TR isn't an engineering
>topic, is it?
You can specify the generator for true random numbers. That is an
engineering problem.
>Are we still talking about the usefulness of "random" numbers
>for cryptographic purposes? Then I propose that TR is useful
>only as a concept, and that we find PR (probable randomness).
True randomness is very much a useful, practical concept in crypto,
especially for the OTP cryptosystem.
>There are numerous physical systems that exhibit chaotic
>behavior -- in which a knowledge of the current state is
>of little-to-no predictive value in determining future states.
The problem I have with chaos is that it is classical and not quantum
in nature. That means that you have no way of proving that the output
of a TRNG based on chaos is truly random based on tests of the output
itself. That does not mean it is not crypto-grade random. But you
cannot prove that by testing the output. So you are left with a
quandry.
I still believe that the proper way to test a keystream generator is
to use it to cipher test messages and then subject those ciphers to
actual attacks like a Bayesian inference attack or other known methods
for attacking stream ciphers. If you can quantify the amount of
information leaked by the cipher, then you have demonstrated its
strength experimentally without having to resort to testing the
keystream itself. If it leaks more than is acceptable, then do
something to strengthen the protocol - like compression or
pre-encryption.
>It is possible to exploit the chaotic zone and generate somewhat
>"random" bits -- in the sense that these bits exhibit the independence
>criterion. They are probably not equiprobable, but deskewing
>can help with that.
The problem as I see it is you don't know the level of randomness of
the chaotic process, and there is no way to test it directly for a
finite keystream. Since I presume you are generating the output
algorithmically, or from an actual physical process that can be
modelled algorithmically (like the weather), then it is not
indeterminant. Quantum process, on the other hand, are completely
indeterminant, like radioactive decay.
Bob Knauer
"The first principle of a civilized state is that power is
legitimate only when it is under contract."
--Walter Lippmann
------------------------------
From: [EMAIL PROTECTED] (Michael Kjorling)
Subject: Re: Help! Cryptosystem needed.
Date: Thu, 18 Feb 1999 20:00:47 GMT
Reply-To: [EMAIL PROTECTED]
=====BEGIN PGP SIGNED MESSAGE=====
Hash: SHA1
Does it matter what algorithm is used in this case? I'd say this is more of an
implementation question. If you want to implement Blowfish as a "streaming"
cipher, encrypting data virtually on-the-fly as it goes out and decrypt as it
comes in, Blowfish would be very well suited for this.
The key setup is rather slow (521 iterations of 16 rounds each), but once the
key has been set up it is rather fast. So, for handling large volumes of data,
this could be the cipher of choice.
The fact that it is unpatented and royalty-free, and has a variable key
length, makes me feel confident about implementing it. I am going to in one of
my security products...
//Michael
On Sun, 14 Feb 1999 09:23:35 -0600, "Steve Sampson" <[EMAIL PROTECTED]>
wrote:
>Because he wants an end-to-end system, not a file that
>was encrypted, and then sent via FTP...
>
>UBCHI2 wrote
>>Why isn't blowfish suitable for your needs?
>
=====BEGIN PGP SIGNATURE=====
Version: PGPfreeware 5.5.3i for non-commercial use <http://www.pgpi.com>
Comment: PGP 6.0.2i executables: coming soon to a server near you
iQA/AwUBNsrfpiqje/2KcOM+EQK0pQCgzwIHQ/+ytCU92/Mn1DFyD7qrWLcAoJJk
qRlcyfQjjjB9CUpoBtKL1us/
=+U1J
=====END PGP SIGNATURE=====
_________________________________________
Mann mu� nicht Gro� sein, um Gro� zu sein
=========================================
Remove the x's and replace .ru with .se
in e-mail address to reply
=========================================
PGP Key ID : 0x8A70E33E
Fingerprint: 95F1 074D 336D F8F0 F297
6A5B 2AA3 7BFD 8A70 E33E
http://certserver.pgp.com:11371/pks/lookup?op=get&search=0x8A70E33E
The above mail should not be
considered mine if the PGP signature
cannot be verified with the above key
(which information is included in
each and every of my Usenet posts.)
------------------------------
From: Bryan Olson <[EMAIL PROTECTED]>
Subject: Re: New high-security 56-bit DES: Less-DES
Date: Thu, 18 Feb 1999 14:30:29 -0800
[EMAIL PROTECTED] wrote:
> Bryan Olson wrote:
> > More or less. Compression doesn't help against known plaintext
>
> Yes, and it does not help even against ciphertext-only attack -- see
> http://www.mcg.org.br/unicity.htm, with a Huffman coding example.
Of course you know I've seen it. In your post of 16 Jan 1999 you asked
if I could refute a proof you use in that document. On Jan 19, I
responded:
| Fair enough. The first major error is the incorrect assertion
| of how Shannon defined unicity distance. Shannon in fact defines
| it as "the number of intercepted letters" (page 692) such that the
| equivocation of the key becomes nearly zero. Ed's text assumes
| the analyst has one or two 8-byte blocks that decrypt into
| 8-byte English strings. He the claims a unicity distance less
| than the amount of intercepted text, which is wrong since the
| unicity distance is, by definition, the amount of intercepted text.
I never saw a reply, and the "unicity.htm" document still asserts:
: Shannon [Sha49] defined "unicity distance" (hereafter, "n") as the
: least amount of plaintext which can be uniquely deciphered from the
: corresponding ciphertext -- given unbounded resources by the attacker.
That's false, but you did add,
: In few words, "unicity" is the least message length that can be
: uniquely deciphered.
Which is basically true, provided we understand that remaining key
entropy must be nearly zero for a solution to qualify as "uniquely
deciphered". Unfortunately, the definition you actually use is the
false one.
Both of us are referring to:
[Shannon, Claude E. "Communication Theory of Secrecy Systems". /Bell
Systems Technical Journal/, vol. 28, pp. 656-715, 1949.]
There are, incidentally, a number of other errors. The unicity distance
of English without any key is zero. Proof: see Shannon's proof in the
same paper that the equivocation of a cryptogram is never greater than
the equivocation of the key. Thus the point at which the equivocation
becomes zero is at zero letters.
We cannot distinguish the correct DES key based on recognizing the
first three letters of a trial decryption. For a randomly chosen
ciphertext block, we should be able to find about four billion DES
keys that decrypt our ciphertext block to a candidate plaintext
beginning with the ASCII characters "The".
If the plaintext language allowed us to distinguish the correct key
with just one block of DES ciphertext (as does known plaintext), this
does not speed up exhaustive attack significantly over, say, random
ASCII. The unicity distance of random ASCII under DES is about seven
blocks, but we don't need to trial decrypt all seven with each key.
Only one in 256 random blocks is ASCII. The expected number of trial
decryptions is about,
___inf
2^55 * \ 1/256^i = 2^55 * 256/255.
/__
i = 0
Back to Less-DES...
> HOWEVER, please read my full paragraph above and the mcg-talk archives as
> provided. Indeed, any method in isolation is weak -- e.g., can you use only
> S-boxes in block-ciphers?
I'm not sure what you're arguing. I recommended one specific, simple,
technique that gives the first block the same security as the others,
at the same cost in ciphertext expansion and no change in computation.
> >and
> > a 64-bit XOR block makes the receiver's job harder. A random pad
> > in the first block provides uniformity with the other blocks.
>
> This is a common misconception, in two counts:
>
> 1. A random pad has 8 bits/byte of entropy and sticks out like a sore
> random-thumb among a necessarily lower-entropy message -- since **any**
> plaintext encoding must be reversible and known to the attacker.
>
> 2. A random pad in the first block will NOT affect the other blocks since DES
> works **per block**.
No misconception in what I wrote. In the known plaintext attack, the
analyst tries encrypting the known first block with all DES keys.
He'll get an average of two matches to the first 56-bit ciphertext
block, and these are easily checked against the next block. This
attack doesn't work against the other blocks, since they're each
padded with n bits of DES output unknown to the attacker - he'd have
to try all keys against all possible paddings. Putting an n bit
random pad in the first block makes it resist this attack just as
well as do the other blocks. If you know some attack that's better
than this one, please do tell.
--Bryan
------------------------------
From: [EMAIL PROTECTED] (R. Knauer)
Subject: Re: True Randomness
Date: Thu, 18 Feb 1999 23:00:21 GMT
Reply-To: [EMAIL PROTECTED]
On 18 Feb 1999 20:20:29 GMT, [EMAIL PROTECTED] (Coen Visser)
wrote:
>Well a Martin-Lof test can be very practical, for example (p.129) the test on
>the ratio of one's in a bitstring can be transformed into a Martin-Lof test.
Yes, but that applies to Kolmogorov complexity. Crypto-grade
randomness does not take those considerations into account. One
glaring reason is that the M-L test you cited is for rejecting
strings, whereas in random number generation for crypto no strings are
rejected.
The specification for a TRNG is that it must be capable of generating
all possible finite strings equiprobably, and that includes strings
which are "regular" as well as strings that are "irregular", or
"complex". There is no uniform distribution of Kolmogorov random
numbers L(x) = 2^{-2l(x) - 1} (see p. 129, Def. 2.4.1) in crypto. It
was in that sense that I made the statement that M-L tests for
randomness are not effective for crypto-grade randomness.
The problem is that the definition of Kolmogorov randomness is
postulated a priori, and M-L tests are developed to disclose it by
rejecting those that do not comply. But Kolmogorov randomness is not
applicable to crypto, so M-L tests are not applicable to crypto
either.
If I am mistaken on this, please point it out to me. I plan to study
this matter in terms of the uniform Bernoulli process (p=1/2) - since
that is the model for sequences generated from a fair coin toss. But I
expect to run into the same problem, namely that the distribution is
taken on L(x) and not N itself completely.
>What I meant is that is difficult (impossible) to use statistical
>tests to *prove* a bitstring random, because you need to test all known
>and unknown statistical properties.
Shades of Godel, Turing and Chaitin all rolled into one, eh.
>Maybe its a good idea to strife for a weaker definition of
>randomness than the mathematically sound one.
Kolmogorov randomness is "mathematically sound" because it leads to
models of induction/inference, and is independent of the
representation to within an additive constant of O(1). But that is not
useful for crypto.
>One that is still usefull
>for cryptography. Such a definition could take into account:
>- degree of equiprobability
>- finiteness
>- degree of uncertainty (unpredictability of next bit)
>- influence of parameters (keys)
We have a working specification for a crypto-grade random number
suitable for the (proveably secure) OTP cryptosystem. It is based on
the specification for a True Random Number Generator (TRNG):
A TRNG must be capable of generating all possible finite sequences
equiprobably. The term "equiprobably" takes into account
"independence" and "equidistribution".
That covers all your criteria above except the last, which is not
applicable since there is no parameters with a TRNG.
>Note that these are properties of a RNG rather than of a random number
>itself.
We agreed a long time ago (slightly over a year ago to be more exact)
that one cannot characterize a crypto-grade random number itself - one
can only characterize the generator. That is why a crypto-grade random
number is one which is produced by a TRNG, which in turn is specified
as it is above.
>The mathematical definition of randomness, be it Martin-Lof's or
>the one originating from Kolmogorov complexity, does not give us methods
>to determine the degree of randomness of a bitstring in practice.
I would add the kind of pseudo-randomness originating from stochastic
considerations.
I truly wish everyone participating in these discussions could see
that as clearly as you and I (and a few others) see it. It is at the
very heart of (strong) crypto that one cannot algorithmically
characterize the randomness of a bitstring itself.
>(That should go into a FAQ someday.)
I have been calling for that for months now. But then we would not be
able to debate those who still cling to the false notion that
statistical pseudo-randomness is the same as crypto-grade randomness.
Bob Knauer
"The first principle of a civilized state is that power is
legitimate only when it is under contract."
--Walter Lippmann
------------------------------
From: Jason S Hackney <[EMAIL PROTECTED]>
Subject: Re: newbie algorithim thoughts
Date: Thu, 18 Feb 1999 15:00:39 -0500
> Read in the users passphrase...
> take each character's ascii value and then generate a fibonacci sequence from
> it (i.e. 56.. 56+1 = 57.. 56+57 = 113 57 + 113 = 170, 113 +170= 183) until you
> get a prime number. After this is all done for each character, multiply the
> first two numbers together, and then xor the whole plaintext by this number.
> The take the next two numbers and xor the previously xor'd data with this
> number, etc.. till you've used all your numbers.. obviously there'd be a case
> if the passphrase was an odd length... but basicall the decryption would be the
> reverse process..
I'm new here as well.
It sounds to me like what you are proposing would make a good ratchet. A one-way
algorithm. I know that these are relatively easy to design and relatively
difficult to break.
Anyone...please feel free to shoot me down on that one. Like I said, I am new as
well.
Jason
------------------------------
From: [EMAIL PROTECTED] (R. Knauer)
Subject: Re: Randomness of coin flips
Date: Thu, 18 Feb 1999 23:16:23 GMT
Reply-To: [EMAIL PROTECTED]
On 18 Feb 1999 13:07:43 -0500, [EMAIL PROTECTED] (Patrick Juola)
wrote:
>>I fail to see how the regularity of having the "expected" amount of
>>bias present is a measure of true randomness. It may be a measure of
>>pseudo-randomness, but that is not appropriate to secure crypto.
>It's not. But *failure* to have the expected amount of bias
>present is almost certainly a measure -- and a mark -- of a lack of
>randomness.
I believe that only holds for strings that are a priori random
according to those tests, which leads to a circular agrument. The
reason for that is that you are insisting on using the term "almost
certain". For other strings that are not a prioi random according to
those tests (e.g., "regular" strings), that "almost certain" turns
into a probability that is far from "almost certain".
For a uniform distribution like that of a TRNG - one which includes
all possible finite sequences equiprobably, both regular and irregular
- the best you can do is come up with a probability that lack of bias
is a measure of randomness.
As mentioned in another post, I intend to study this in terms of the
uniform Bernoulli Process, which does have such strong convergent
properties as you allude to. But I suspect it only applied to the
uniform distribution of irregular strings, and excludes regular
strings like those produced by a TRNG. Stay tuned.
Bob Knauer
"The first principle of a civilized state is that power is
legitimate only when it is under contract."
--Walter Lippmann
------------------------------
From: Richard Goldman <[EMAIL PROTECTED]>
Subject: The Hunt Is ON !!! @ PAWS !!!
Date: Thu, 18 Feb 1999 15:28:17 -0800
Reply-To: [EMAIL PROTECTED]
The Barbary Coast Armchair Scavenger Hunt and Trivia Contest is on at
PAWS. It takes place on Sunday, March 14th, 1999 on the internet from
your home from 12 til 4pm. Challenges are published on The Hunt website,
http://www.unexpected.com every 30 minutes for four hours. Your team
will compete with other teams by solving these obscure brain teasers and
challenges to win fabulous prizes while raising money for Pets Are
Wonderful Support. Registration is $15.00 per person with no maximum
number of participants per team, 100% of all registration fees goes
directly to PAWS. The more people on your team, the more likely you
will be to answer challenges correctly and win fabulous prizes. Check
out The Hunt website at http://www.unexpected.com for sample
challenges and lists of prize donors. Register your team early online
or at (415)-863-3506, as this event will fill up quickly. Remember the
more people that register on a team, the more money you can raise for
PAWS and have a good time doing it!
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: Bruce's Feb. "CRYPTO-GRAM"
Date: Fri, 19 Feb 1999 00:02:48 GMT
[EMAIL PROTECTED] (JPeschel) wrote, in part:
>> [EMAIL PROTECTED] (John Savard) enigmatically writes:
>>He names other names in that issue too, and those are names one is
>>less likely to have heard before...
>What point, if any, are you making?
Nothing too terrible. Just that while naming the names of some
companies producing cryptographic snake-oil, while it may indeed be
quite helpful to some, isn't really revealing anything surprising.
However, there was another item in that same issue which produced some
hard facts - including the names of two individuals - backing up what
was previously only a rumor (and one I had tended to disbelieve). It's
here, therefore, to me that there were some surprises.
John Savard
http://members.xoom.com/quadibloc/index.html
------------------------------
** 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
******************************
