Cryptography-Digest Digest #67, Volume #13 Wed, 1 Nov 00 11:13:01 EST
Contents:
Re: Give it up? (Tom St Denis)
Re: Give it up? (Pascal JUNOD)
Re: BENNY AND THE MTB? (SCOTT19U.ZIP_GUY)
Re: BENNY AND THE MTB? (Richard Heathfield)
Re: 3-dimensional Playfair? (Sundial Services)
Re: frequency analysis (Sundial Services)
Re: Is RSA provably secure under some conditions? (Shai Halevi)
Re: BENNY AND THE MTB? ([EMAIL PROTECTED])
Re: frequency analysis (Richard Heathfield)
Re: BENNY AND THE MTB? (Tim Tyler)
----------------------------------------------------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: Give it up?
Date: Wed, 01 Nov 2000 13:00:56 GMT
In article <[EMAIL PROTECTED]>,
[EMAIL PROTECTED] wrote:
> Tom St Denis <[EMAIL PROTECTED]> wrote:
>
> : I just want to stress "leave security to the components designed for
> : security".
>
> Where security considerations are relevant, they can impact the
design of
> practically every component in a system.
>
> I don't think you can usually isolate security considerations in
> (say) a cipher system.
>
> What is your idea of a component in a secure system whose design is
> *not* impacted by security considerations?
A compression codec for example does not increase security (it can
reduce it however).
My point is I am friggin tired of hearing about "super bijective
codecs" and "super-duper padding". Either find proof that they enhance
security or post on comp.compression.
This is sci.crypt not "sci.post.whatever.you.want.crypt"
Tom
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
Date: Wed, 01 Nov 2000 14:22:52 +0100
From: Pascal JUNOD <[EMAIL PROTECTED]>
Subject: Re: Give it up?
> This is sci.crypt not "sci.post.whatever.you.want.crypt"
That's funny to read this from you...
A+
Pascal
--
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
* Pascal Junod, [EMAIL PROTECTED] *
* Laboratoire de S�curit� et de Cryptographie (LASEC) *
* INR 313, EPFL, CH-1015 Lausanne, Switzerland ++41 (0)21 693 76 17 *
* Place de la Gare 12, CH-1020 Renens ++41 (0)79 617 28 57 *
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
------------------------------
From: [EMAIL PROTECTED] (SCOTT19U.ZIP_GUY)
Subject: Re: BENNY AND THE MTB?
Date: 1 Nov 2000 13:14:08 GMT
[EMAIL PROTECTED] (Richard Heathfield) wrote in
<[EMAIL PROTECTED]>:
>"SCOTT19U.ZIP_GUY" wrote:
>>
><snip>
>>
>> They are still laughing when they get the first message to
>> decyrpt. Since it is only a byte long. Some of the boys don't
>> even want to try to turn the quantum computer on. One byte they
>> say. How many possible messages could that decrypt to.
>
>2^CHAR_BIT
>
>In other words, usually 256.
>
>
No much much nore than 256. As a matter of fact I enclosed
a dump of the "one byte" file the 8 bits which does contain
only 256 states. But becuse Matts code was used you can decrypt
it with several keys and given your ability level it is highly
unlikely that even after thousands of deccryptions with Matts
code that any two will match. I understand your problem and those
of most people like you. You've never been really exposed to a
truely biejective compression encryption program before. But
here you have something you can test for your self very easly.
David A. Scott
--
SCOTT19U.ZIP NOW AVAILABLE WORLD WIDE
http://www.jim.com/jamesd/Kong/scott19u.zip
Scott famous encryption website **now all allowed**
http://members.xoom.com/ecil/index.htm
Scott LATEST UPDATED source for scott*u.zip
http://radiusnet.net/crypto/ then look for
sub directory scott after pressing CRYPTO
Scott famous Compression Page
http://members.xoom.com/ecil/compress.htm
**NOTE EMAIL address is for SPAMERS***
I leave you with this final thought from President Bill Clinton:
------------------------------
Date: Wed, 01 Nov 2000 14:16:55 +0000
From: Richard Heathfield <[EMAIL PROTECTED]>
Subject: Re: BENNY AND THE MTB?
Tim Tyler wrote:
>
> Richard Heathfield <[EMAIL PROTECTED]> wrote:
> : "SCOTT19U.ZIP_GUY" wrote:
>
> :> They are still laughing when they get the first message to
> :> decyrpt. Since it is only a byte long. Some of the boys don't
> :> even want to try to turn the quantum computer on. One byte they
> :> say. How many possible messages could that decrypt to.
>
> : 2^CHAR_BIT
>
> : In other words, usually 256.
>
> A better upper bound would be 2^KEY_BIT - i.e. approx 2^128 in this
> context.
>
> This figure may contain a few duplicated messages under different keys.
(That's what I like about Mr Scott. Despite his best efforts, useful
information sometimes results from his articles.)
Now, Mr Tyler, you have succeeded in engaging my interest. Please
remember that, although I like to flatter myself that I am quite bright,
I am nevertheless no mathematician - and that, as you know, is a great
defect. I am of the rather simple-minded and foolish opinion that one
octet (if we can both use that word unambiguously?!) can contain any one
of 256 different possible values. Now, I am quite prepared to accept
that there may well be a 128-bit key lurking in Bob's drawer, which he
can apply to this octet in, no doubt, arcane and mystical ways, but I do
not understand how Alice's octet can communicate anything to Bob except
in the following ways:
256 different bit patterns
fact of transmission
time/date of transmission
pattern of prior and subsequent transmissions
similar traffic-related information
I think we have to disregard all of those except the first, since we
cannot objectively and portably discuss the other ways (or am I wrong
about that?).
So we have 256 different bit patterns. We have a 128-bit key. Now, if
we're discussing just one algorithm, then as I see it there are only 256
ways to combine the key with the octet - one for each combination in the
octet. Now, I can see that there are 2^(128+8) possible bit patterns
resulting from a combination of the key and the byte, but since Alice
and Bob have (presumably) agreed the key between them in advance, the
key is fixed, and therefore all but 256 of these combinations cannot
apply.
Therefore, only 256 messages can be communicated from Alice to Bob. Of
course, great meaning might be ascribed to each one - there may be a
world of difference between the semantics of 10001101 and the semantics
of 10001110; this is effectively a 256-entry codebook - but I do not see
how it is possible for more messages to be communicated to Bob from this
single octet.
One thought occurred to me, which is that the messages are actually
pre-constructed into the key - but this seems a little too unwieldy to
be useful.
So, Mr Tyler - I recognise you to be a regular contributor to this
newsgroup, and a man who is capable of stringing together entire
paragraphs of highly useful, informed, and intelligible information,
without feeling the need to resort to expletives and oddball accusations
of deceit and incompetence. Since I cannot conclude from this profile
that you are necessarily mistaken, it follows that I am probably
mistaken, and must have misunderstood something. I would, therefore,
appreciate enlightenment from you (or from some other comparably clueful
and polite source of information) with regard to this messagespace
question.
--
Richard Heathfield
"Usenet is a strange place." - Dennis M Ritchie, 29 July 1999.
C FAQ: http://www.eskimo.com/~scs/C-faq/top.html
K&R Answers: http://users.powernet.co.uk/eton/kandr2/index.html
------------------------------
Date: Wed, 01 Nov 2000 07:25:56 -0700
From: Sundial Services <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Subject: Re: 3-dimensional Playfair?
For a very fascinating take on this topic and more, by someone who knew
all too well what was at stake, I heartily recommend "Between Silk and
Cyanide," now available in paperback.
The author was responsible for furnishing secret code-systems to what
the British -thought- were their agents in occupied countries. They
were originally given codes based on memorized poems. It turns out that
nearly every one of them was immediately captured and that the Germans
were playing a deception scheme on the British that dwarfed the commonly
known "double cross." The author realized it. His is a tale of real-
world ciphering, and administrative politics, in time of war.
>Daniel wrote:
> The idea of a Playfair was that there was this single key to be
> learned by heart. Everything else could be done by hand. This way an
> agent didn't have to carry "extra material" which would make him even
> more vulnerable...
------------------------------
Date: Wed, 01 Nov 2000 07:34:07 -0700
From: Sundial Services <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Subject: Re: frequency analysis
Certainly this is a good example of a fairly-simple program that can be
applied to "hand" cryptosystems such as monoalphabetic. But the
strategy could be improved upon considerably through the use of a
computer (especially a modern PC) and the aforesaid dictionary file.
The program you created so-far is a pattern matcher that "hits" upon an
exact-match and nothing more; and that automates the techniques that
people would use and nothing more.
A more interesting program would read the 45,000 word dictionary and
build a letter-probability tree (of which the familiar ETAOIN... is
essentially the list of first-letter probabilities only. It would be
quite difficult for a human to work out all that, but the computer can
do it in a millisecond.
It can then explore the cipher entirely by automation, selecting the
most probable substitutions, comparing against the dictionary to see if
the text has become more-probable or less-probable, using guesses if the
number of possible words falls below a certain threshhold, and so forth.
Such a program, if fully developed, could very likely crack any mono
cipher, knowing nothing but the ciphertext and the fact that it is mono,
in a second or three.
Just like a computer program can try to bludgeon its way through a game
of chess.
Now -that- would be an informative program to do!
>Richard Heathfield wrote:
>
> Richard Heathfield wrote:
> >
> > JPeschel wrote:
> > >
> > > [EMAIL PROTECTED] writes:
> > >
[...]
> Okay, that's it. I'd appreciate the opinions of the clueful on whether
> this is any use for elementary cryptanalysis, or whether it should be
> relegated to rec.puzzles.
>
> --
> Richard Heathfield
> "Usenet is a strange place." - Dennis M Ritchie, 29 July 1999.
> C FAQ: http://www.eskimo.com/~scs/C-faq/top.html
> K&R Answers: http://users.powernet.co.uk/eton/kandr2/index.html
------------------------------
From: Shai Halevi <[EMAIL PROTECTED]>
Subject: Re: Is RSA provably secure under some conditions?
Date: Wed, 01 Nov 2000 09:37:18 -0500
David Wagner wrote:
> [...]
> What's _really_ noteworthy (IMHO) is the following feature of their
> system. They use a description of the hash function in the system,
> and not just to implement the hash function: in fact they take the
> description of the hash function, which is just a bit-string, and
> hash it, a very weird-looking thing to do!
> [...]
Right. The central feature of proofs in the random-oracle model, is the
assumption that "the only thing an adversary can do with the code of the
hash function, is to run it". Once you make this assumption, pretty much
everything else follows. Hence, the only way to get a counter example
such as the one in CGH is to "do something else with the code".
Our experience from everyday life, tells us that usually there isn't
much else you can do with such code. Sure, you can take the code, view
it as a bit string, and hash it, or do whatever, but that will not give
you anything particularly useful. Problem is, we do not understand this
phenomena. Why is it that for "natural" systems, seems like the only
sensible thing to do with the code is to run it? What property do
"natural" systems have, that renders any other form of processing the
code useless for an adversary.
I am not very optimistic about our ability to find answers for these
questions. My feeling is that answering them would require a far deeper
understanding of the nature of computing than what we currently have.
Also, science is full of surprises: it may turn out that this intuition
that we have about "natural" systems is wrong, and there is a different,
more useful, way to use the code.
In the mean time, my personal interpretation of proofs of security in
the random oracle model is that such system is secure, unless:
(a) the underlying assumption (e.g. factoring) is wrong,
(b) there is a flaw in the specific hash function that is used, or
(c) someone finds an attack that uses the hash function code in any way
other than just running it.
-- Shai
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: BENNY AND THE MTB?
Date: Wed, 01 Nov 2000 14:37:46 GMT
Whether you like it or not, no matter how good your bijective compressor
with any AES or your own scott19 cipher...you are still dependent on a
PK cryptosystem like RSA to cover your tracks...Try and answer that
one...If MTB can lick your RSA key and get your session key...your
cipher is worthless...no matter how good it is... Well start thinking
about that then...
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
Date: Wed, 01 Nov 2000 15:07:41 +0000
From: Richard Heathfield <[EMAIL PROTECTED]>
Subject: Re: frequency analysis
Sundial Services wrote:
>
> Certainly this is a good example of a fairly-simple program that can be
> applied to "hand" cryptosystems such as monoalphabetic.
Yes. I thought I'd start gently. That you say it is a "good" example is
encouraging. :-)
> But the
> strategy could be improved upon considerably through the use of a
> computer (especially a modern PC) and the aforesaid dictionary file.
Right. This is very definitely a first cut.
>
> The program you created so-far is a pattern matcher that "hits" upon an
> exact-match and nothing more; and that automates the techniques that
> people would use and nothing more.
This is true - I was trying to leave enough human interaction to make
the program (a) simple to write (after all, it's a first exploration
into generalised cryptanalytic programs - the only such programs I have
written before have been designed specifically to crack a given
ciphertext, and as such were not generally useful), and (b) interesting
*to use* - it takes most of the donkeywork out of solving, say, a
puzzzzzzzzzzzle-magazine cryptogram, without doing the whole thing for
you and thus removing every last vestige of human skill from the
process. (BTW most people probably would not have pattern dictionaries
when doing this by hand, but I guess your point is that *cryptographers*
would!)
Still, you're quite right - onward and upward...
>
> A more interesting program would read the 45,000 word dictionary and
> build a letter-probability tree (of which the familiar ETAOIN... is
> essentially the list of first-letter probabilities only. It would be
> quite difficult for a human to work out all that, but the computer can
> do it in a millisecond.
Well, ETAOIN might be the result of a dictionary frequency analysis, or
it might not. In fact, it just occurred to me that I can find out very
quickly... brb...
> freq
Ch Count %age Ch Count %age
e 42687 11.739 p 10063 2.767
i 31448 8.648 m 9803 2.696
s 29638 8.151 h 7808 2.147
a 28961 7.965 b 7368 2.026
r 27044 7.437 y 6004 1.651
n 26973 7.418 f 4924 1.354
t 24598 6.765 v 3971 1.092
o 21588 5.937 k 3209 0.883
l 19470 5.354 w 3073 0.845
c 15001 4.125 z 1631 0.449
d 13849 3.809 x 1053 0.290
u 11713 3.221 j 727 0.200
g 10338 2.843 q 682 0.188
:-)
As you can see, RedHat's /usr/dict/words has a rather different story to
tell. This is, of course, because it gives disproportionate weight to
letters in words which, in English, are used infrequently.
Interestingly, however, 'e' still wins hands down. (On second thoughts,
perhaps it's not that interesting!)
Having said that, I do know what you're driving at. For version 2, I was
contemplating performing a probabilistic analysis of monographs,
digraphs, trigraphs and, perhaps, tetragraphs, based on probabilities
derived from as much English text as I can get my hands on (God bless
the World Wide Wait^WWeb) - and of course storing these probabilities in
an external file, for maximum flexibility.
> It can then explore the cipher entirely by automation, selecting the
> most probable substitutions, comparing against the dictionary to see if
> the text has become more-probable or less-probable, using guesses if the
> number of possible words falls below a certain threshhold, and so forth.
> Such a program, if fully developed, could very likely crack any mono
> cipher, knowing nothing but the ciphertext and the fact that it is mono,
> in a second or three.
Absolutely. It would also be great fun to write, and might even become
useful to cryptanalysts (and, at the same point, the program would cease
to be interesting for puzzlers - but that's okay, because they can use
version 1.)
>
> Just like a computer program can try to bludgeon its way through a game
> of chess.
>
> Now -that- would be an informative program to do!
That was indeed the way I planned to go. (Well, pretty much, anyway.)
Thank you very much for your comments. Much appreciated.
--
Richard Heathfield
"Usenet is a strange place." - Dennis M Ritchie, 29 July 1999.
C FAQ: http://www.eskimo.com/~scs/C-faq/top.html
K&R Answers: http://users.powernet.co.uk/eton/kandr2/index.html
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: BENNY AND THE MTB?
Reply-To: [EMAIL PROTECTED]
Date: Wed, 1 Nov 2000 15:31:33 GMT
Richard Heathfield <[EMAIL PROTECTED]> wrote:
: Tim Tyler wrote:
:> Richard Heathfield <[EMAIL PROTECTED]> wrote:
:> : "SCOTT19U.ZIP_GUY" wrote:
:> :> They are still laughing when they get the first message to
:> :> decyrpt. Since it is only a byte long. Some of the boys don't
:> :> even want to try to turn the quantum computer on. One byte they
:> :> say. How many possible messages could that decrypt to.
:>
:> : 2^CHAR_BIT
:>
:> : In other words, usually 256.
:>
:> A better upper bound would be 2^KEY_BIT - i.e. approx 2^128 in this
:> context.
:>
:> This figure may contain a few duplicated messages under different keys.
: Now, Mr Tyler, you have succeeded in engaging my interest. [...]
: So we have 256 different bit patterns. We have a 128-bit key. Now, if
: we're discussing just one algorithm, then as I see it there are only 256
: ways to combine the key with the octet - one for each combination in the
: octet. [...]
Not so. Could it be that you are aauming that a 8 bit cyphertext need map
to an 8 bit plaintext? It need not - and indeed in Matt's code, it
typically does not - an 8-bit byte cyphertext typically maps to a much
longer plaintext.
I don't think "256 messages" comes into it. The interceptors have
received a *particular* byte. They are not considering what messages
could be transmitted by *any* single byte value, but the message that is
*actually* transmitted by one specific byte - the one they have
intercepted.
There are probably almost as many possible messages that could be
represented by that single bye as there are keys; since almost every
key is likely to lead to a different message.
--
__________ Lotus Artificial Life http://alife.co.uk/ [EMAIL PROTECTED]
|im |yler The Mandala Centre http://mandala.co.uk/ Hat: Baldness cure.
------------------------------
** 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
******************************
