Cryptography-Digest Digest #344, Volume #10 Fri, 1 Oct 99 12:13:03 EDT
Contents:
Re: Ritter's paper
Re: NEMA, Swiss cipher machine
Re: Glossary of undefineable crypto terms (was Re: Ritter's paper) (Patrick Juola)
RC5 Hardware? (=?iso-8859-2?Q?=C8=AB=C0=BA=C1=B5?=)
Re: ECDL and distinguished points (John Sager)
Re: Decryption --Help!!! (sha99y00000)
Re: RSA encryption algorithm. (Keith A Monahan)
Re: SNAKE Web Page (Peter Gunn)
Re: Irish schoolgirl wins European Young Scientist Award (Dave Hazelwood)
Re: Example of a one way function? (Tom St Denis)
Re: Random number generation (Paul Koning)
Re: Are small block sizes less secure? (DJohn37050)
Re: Compress before Encryption (Tim Tyler)
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] ()
Subject: Re: Ritter's paper
Date: 1 Oct 99 12:51:08 GMT
Johnny Bravo ([EMAIL PROTECTED]) wrote:
: 256 bits is not 4.5 times as secure as 56 bits. It is exactly 115,792,089,
: 237,316,195,423,570,985,008,687,907,853,269,984,665,640,564,039,457,
: 511,950,319,091,712,000 times as secure. This is a bit more than one step
: beyond DES.
You've made many good points. It is true that the AES candidates are
highly secure ciphers, and that each additional bit in the key doubles the
time required to crack a cipher by brute force.
I simply point out why some people might want to go even further: after
all, the predecessor to DES, LUCIFER, already had a 128-bit key and a
128-bit block size. Of course, outrageous conclusions, like calling the
AES a scam, aren't 50% right. But that isn't always the meaning of the
phrase "half right": I'm simply noting that even Mr. Scott didn't start
from premises which were completely false.
John Savard
------------------------------
From: [EMAIL PROTECTED] ()
Subject: Re: NEMA, Swiss cipher machine
Date: 1 Oct 99 13:08:01 GMT
Douglas A. Gwyn ([EMAIL PROTECTED]) wrote:
: [EMAIL PROTECTED] wrote:
: > ... I think that this needs to be avoided: and one way to help
: > to avoid it is simply to avoid the use of the word 'rotor' to describe,
: > when discussing a cipher machine, any kind of gear, cam, or pinwheel, or
: > indeed any other item but a _wired_ rotor.
: Unfortunately it doesn't really help. Indeed, wired rotors
: have also frequently been called "wheels". Basically, from
: the cryptanalyst's viewpoint, it is the periodicity that is
: interesting, not the construction of the equipment.
Yes, but I would presume it is of some relevance how the periodicity is
combined with the plaintext stream.
This is what distinguishes a rotor machine from most other cipher
machines.
In a Hagelin lug and pin machine, the pinwheels produce a sequence of bits
with a long period, which the cage then, by its lugs, encodes by means of
an OR function to a displacement; this displacement, once produced, is
applied to the plaintext by shifting a reversed alphabet.
In a Lorenz Schlusselzusatz, two banks of pinwheels produce bits that are
applied by an XOR to a stream of teleprinter characters.
But in a rotor machine, while the mechanical rotor displacements are
applied directly by a Caesar substitution - twice, once added, once
subtracted - the plaintext is also constantly being put through one
scrambled alphabet after another.
The PURPLE stepping-switch machine, choosing completely unrelated
alphabets from a list, takes the unique feature of a rotor machine even
further, and is susceptible to an isomorph attack as well. (Thus, although
it doesn't have any kind of "rotor" in its construction, at least it is
*related* to rotor machines.)
Of course, by noting how the plaintext is transformed as the
distinguishing feature, I might come to the bizarre conclusion that
SIGCUM, a telecipher machine that produced a stream of bits to XOR with
the plaintext by means of wired rotors, is "not" a rotor machine. Of
course it still _is_ a rotor machine, but one of a special sort: the
unique transformation characteristic of that type of machine is performed
on a variable that produces the keystream rather than on the plaintext
stream itself.
Naturally it is the mathematical, rather than the physical, nature of what
goes on in a cipher machine that is important for characterizing it. But
wired rotor machines are distinguished from other known designs by their
use of multiple mixed alphabets in successive encipherment stages. This
cannot be entirely without significance.
John Savard
------------------------------
From: [EMAIL PROTECTED] (Patrick Juola)
Subject: Re: Glossary of undefineable crypto terms (was Re: Ritter's paper)
Date: 1 Oct 1999 08:59:36 -0400
In article <[EMAIL PROTECTED]>, Douglas A. Gwyn <[EMAIL PROTECTED]> wrote:
>"Trevor Jackson, III" wrote:
>> Also Known As the Karnak Atack. You hold the cipher text up to your
>> forehead and guess the plaintext. There is no possible cryptologic
>> defense against someone who can guess your message. A ouija board is a
>> tool to assist in such guessing.
>
>Well, yes, there is a defense. In a true "Ouija" attack, a correct
>guess can be *verified* against the intercepted ciphertext. But OTP
>is immune to this, so it is an example of an Ouija-resistant system.
Huh? How do you verify *anything* against the cyphertext?
Furthermore, it's very easy to verify plaintext against the real world.
-kitten
------------------------------
From: =?iso-8859-2?Q?=C8=AB=C0=BA=C1=B5?= <[EMAIL PROTECTED]>
Subject: RC5 Hardware?
Date: Fri, 01 Oct 1999 13:18:11 GMT
Has anybody seen a RC5 hardware implementation?
As for me, not yet.
If they don't usually make it, why is that?
--
Ben Hong
Future Systems, Inc.
Phone : +82-2-578-0581 (ext. 533)
Fax : +82-2-578-0584
Email : [EMAIL PROTECTED]
------------------------------
From: [EMAIL PROTECTED] (John Sager)
Subject: Re: ECDL and distinguished points
Date: 1 Oct 1999 14:19:44 GMT
In article <[EMAIL PROTECTED]>, [EMAIL PROTECTED] (jerome) writes:
: On 29 Sep 1999 13:43:08 GMT, John Sager wrote:
: [snip]
:
: > One could
: >reduce it to, say, 5 minutes but the storage & comparison server has to
: >have that much more storage capacity for all the extra points stored.
: >Plus there is all that extra network traffic.
:
: it was what i meant by 'big computer' (aka a lot of memory and
: centralized so no network traffic). my question was badly posed.
: let me retry: suppose i store all the points (instead of 1 in 2^30)
: and try to match them.
:
: 1. am i right to think that the collisions are more probable ? if so, how
: much more probable ?
: 2. this require more memory and increase the match time. but if we forget the
: memory to consider only the time, is the tradeoff interesting ? i.e. the
: time saved by a better collision probability is greater that the time
: loosed by a bigger matching ?
In a practical sense, it's a bad use of computing resource. for every
distinguished point computed, the match engine has to search for
a matching point then store the point. All the searches will fail until
the problem is solved (you only need one match, though there is a very
low probability that the first match may fail to allow the result to be
computed). If you make *every* point a distinguished point, then the search
algorithm has to be highly optimised, as well as the point compute algorithm.
Plus you have to be prepared to store 4E14 points, or perhaps even two or
3 times that.
--
John
--
Sorry about the address.
This is me, not BT.
------------------------------
Date: Fri, 24 Sep 1999 13:49:40 +0100
From: sha99y00000 <[EMAIL PROTECTED]>
Subject: Re: Decryption --Help!!!
If you're writing a program, write one to do the trigrams for you. Then
you can have a more reliable frequency chart to play with. If you know
what kind of person and period the piece was written, then you can
produce a frequency chart from similar works.
Below is the list that I found in Helen Fouche Gaines book:
'The ninety-eight most frequent English trigrams, combining a count of
20,000 trigrams by Fletcher Pratt, in "Secret and Urgent," suppose not
to include overlaps between words, and 5,000 by Frank R. Fraprie,
including overlaps.
THE 1182
ING 356
AND 284
ION 252
ENT 246
FOR 191
TIO 188
ERE 173
HER 179
ATE 165
VER 159
TER 157
THA 155
ATI 148
HAT 138
ERS 135
HIS 130
RES 125
ILL 118
ARE 117
CON 114
NCE 113
ALL 111
EVE 111
ITH 111
TED 110
AIN 108
EST 106
MAN 101
RED 101
THI 100
IVE 96
REA 95
WIT 93
ONS 92
ESS 90
AVE 84
PER 84
ECT 83
ONE 83
UND 83
INT 80
ANT 79
HOU 77
MEN 76
WAS 76
OUN 75
PRO 75
STA 75
INE 73
WHI 51 * This is what is in the book though most prob. 71
OVE 71
TIN 71
AST 70
DER 70
OUS 70
ROM 70
VEN 70
ARD 69
EAR 69
DIN 68
STI 68
NOT 67
ORT 67
THO 66
DAY 65
ORE 65
BUT 64
OUT 63
URE 63
STR 62
TIC 62
AME 61
COM 61
OUR 61
WER 61
OME 60
EEN 59
LAR 59
LES 59
SAN 59
STE 59
ANY 58
ART 58
NTE 58
RAT 58
TUR 58
ICA 57
ICH 57
NDE 57
PRE 57
ENC 56
HAS 56
WHE 55
WIL 55
ERA 54
LIN 54
TRA 54 '
All the best with your program
sha99y
------------------------------
From: [EMAIL PROTECTED] (Keith A Monahan)
Subject: Re: RSA encryption algorithm.
Date: 1 Oct 1999 14:40:37 GMT
Check out http://www.shoup.net/ntl
NTL stands for Number Theory Language and let's you define variables
of type ZZ which allow very very large integers. The limitation on the
size of the integers is by memory alone.
It's a C++ class and they have overloaded the standard operations like
add, mult, subt, mod, etc. I used this to implement a small RSA encryption
program recently.
Keith
Stephen M. Gardner ([EMAIL PROTECTED]) wrote:
: Jeremy Botha wrote:
: > Hi all.
: >
: > My problem is that I'm trying to code this in C/C++, and encryption /
: > decryption requires *huge* numbers. I've tried long ints, long long ints,
: > and finally in a fit of desperation, doubles. doubles seem to work okay,
: > apart from the irritating fact that they loose precision, so when I decrypt
: > the cypher it doesn't return to plaintext.
: None of these will work. You especially don't want doubles! That precision
: you lose is absolutely necessary. There are a number of alternatives. You
: could get Dr. Mike's
:
:book,(http://www.amazon.com/exec/obidos/ASIN/1884777694/qid%3D938731501/002-9296106-1692859)
: he shows you how to implement multiprecision math in C or you could use one of
: the multiprecision libraries (usually written in assembler for efficiency) that
: are available on the web. Don't waste time with the native C/C++ types, they
: do not contain enough bits to do RSA keys of reasonable size (>512).
: --
: Steve Gardner Technical Staff Member 1320 Systems Engineering
: ALCATEL USA
: 1225 N. Alma Road Tel: 972-996-5888
: Richardson Tx. 75081-2206 http://ctnwww.aud.alcatel.com/~gardsm/
: You who choose to lead must follow,
: But if you fall you fall alone,
: If you should stand then who's to guide you?
: If I knew the way I would take you home.
: "Ripple" -- The Grateful Dead
------------------------------
From: Peter Gunn <[EMAIL PROTECTED]>
Subject: Re: SNAKE Web Page
Date: Fri, 01 Oct 1999 14:19:50 +0100
[EMAIL PROTECTED] wrote:
> On Thu, 30 Sep 1999 20:59:41 +0100, Peter Gunn
> <[EMAIL PROTECTED]> wrote:
[snip]
>
> >
> >Here is some thinking out loud...
> >
> >1) Using a larger g, perhaps > SQRT(max modulous) as you suggested
> >earlier would seem to go a long way towards stopping this, but would I
> >have problems finding a single g that is a valid egenerator for a
> table of
> >large primes... how do you work that out anyway??
>
> For a prime q of the form 2p+1 then generators are quite common, there
> are PHI(q-1) = PHI(2p) = PHI(p) = p-1 of them.
>
> An element g will be a generator modulo q iff g^p = -1 (mod q).
>
> Note that g=4 will never be a generator modulo q because
> g^p = (2^2)^p = 2^(2p) = 2^(q-1) = 1 (mod q) by Fermat's Little
> Theorem. But this need not be a problem since all you really need is
> an element that generates a large prime-order subgroup modulo q.
>
> Since all elements modulo q=2p+1 have order of either 1, 2, p or 2p,
> and the only elements with order 1 or 2 are 1 and -1 = q-1 (mod q),
> then choosing any other element, apart from 1 and -1, as the basis for
> exponentiation will result in a subgroup whose order is a multiple of a
> large prime factor. So should be okay.
>
> In the context of SNAKE this means that g should be chosen so as not to
> be congruent to 1 or -1 for all primes in the array.
ok, no negative numbers in SNAKE, so
SQRT(max modulous) < g < max modulous
should always be ok (max modulous always huge of course :-)
> >2) Perhaps I could just ban all values g^n ?? for g==4 this would mean
> >I lost 25% of possible values, but it would be pretty easy to implement
> >the check (just look at least significant bits). But what else would
> this
> >affect??
>
> Seems a bit drastic. Not very elegent :-(
>
> >Perhaps another value 4 < g < 256(?) might work and not lose too many
> >values?
>
> No. Any other value in that range is still susceptable to the
> adversary being able to generate a g^n < Qi.
I meant that if I chose (for instance) g==256 then I could just ban
all values g^n < Qi... and lose 1 in 256 numbers rather than one in four,
but you are right this is *very* ugly.
>
> The reason I suggested choosing a g > SQRT(max[Qi]) is so that the only
> g^n < Qi is for n=1, so that you only have to check that
> Vi, Wi != g.
Yes, this is neat.
>
> >3) Perhaps there is some value in changing the verification procedure??
> >Instead of sending the plain values for verfiers R and S, I could
> >send E[P](R) and E[P](S)... this would mean that the impersonator
> >would have to check each guessed K' value against E[P'](S) and I cant
> >immediately see how he could do this??
>
> As I see it, the adversary doesn't make any use of R and S until he is
> offline (he can just send any old value for E[P](S) in step (2)). Once
> offline, the first thing he does is guess P. This immediately gives
> him values for R and S, call them R' and S', which he can plug into the
> key derivation function and obtain, as before, a guessed K, call it K',
> so that he can now check to see if E[K'](S') is the same as he received
> in step (3). It seems highly probable that a wrong guess for P will
> give a different result.
>
> >Im also open to ideas ;-)
>
> I'll let you know if I have any :-)
>
> Seriously though, one idea might be to use a "random" g of some kind.
> But this is straight from the top of my head, and so I don't know how
> this might be done or what weaknesses it may introduce.
Right, how about using a value for g based on R??
say g = SQRT(max modulous) + (R mod SQRT(max modulous))
I guess I just have to try and defeat any attacks as they are discovered
since there is no way to prove that all possible attacks have been defeated.
So, Im thinking that I will adjust the SNAKE web page to just state
that g must be in range.... SQRT(max modulous) < g < max modulous
until Ive had a chance to think about the implications of allowing a value
for g based on R. I will also specifically state that Vi, Wi != g must be
checked.
ttfn
PG.
------------------------------
From: [EMAIL PROTECTED] (Dave Hazelwood)
Subject: Re: Irish schoolgirl wins European Young Scientist Award
Date: Fri, 01 Oct 1999 15:03:25 GMT
Yeah...but obviously a kid with potential don't you think? I bet she
has a lot of standing job offers and scholarships already.
"Michael Scott" <[EMAIL PROTECTED]> wrote:
>According to a report on Irish radio, the schoolgirl in question, Sarah
>Flannery, has herself found an "attack" on her own scheme.
>
>
>She is only a kid, and the whole thing got hyped up beyond all reason.
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: Example of a one way function?
Date: Fri, 01 Oct 1999 15:01:30 GMT
In article <qS1J3.501$[EMAIL PROTECTED]>,
"Boris Kolar" <[EMAIL PROTECTED]> wrote:
>
> Tim Tyler <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> > Boris Kolar <[EMAIL PROTECTED]> wrote:
> > : Roger Carbol <[EMAIL PROTECTED]> wrote in message
> > :> I. Michael Mandelberg <[EMAIL PROTECTED]> wrote:
> >
> > :> > Can someone point me to a one-way-function that is typically
used
> > :> > for encryption?
> > :>
> > :> Multiplication.
> >
> > : Of course multiplication is a one-way function, but It's not a
very
> > : conveniant one.
> >
> > Multiplication is a one-way function? I'd have thought it was
> > generally eminently reversible.
>
> Multiplication (in the field of integers) is believed to be one-way:
> 1) The easy way: multiply two integers (preferably primes)
> 2) The hard way (invertion): given integer x find integers (a,b),
such
> that a*b=x
Other then RSA however there is very little to exploit. Any scheme
using common factors (like one might in discrete log systems) can be
broken in polynomial time.
> >
> > I think you need to invoke complex numbers, or modulo arithmetic,
> > or *something* if you want to claim multiplication as a one-way
> > function.
>
> No. Multiplication of complex numbers is easily invertible.
If the numbers are irrational it should be as difficult to solve as
factoring (either way).
Tom
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Paul Koning <[EMAIL PROTECTED]>
Subject: Re: Random number generation
Date: Fri, 01 Oct 1999 11:00:41 -0400
"j.w.altena" wrote:
>
> At Statistics Netherlands we would like to have to our disposition about
> 10E9 random identifying numbers with a length of 10 (decimal) positions.
> These numbers should preferably not be generated all at the same moment, but
> the set should be extendable in steps. We think we can use encryption for
> the generation of these numbers. An idea is to take the numbers 1 to n in
> the first step and encrypt them. In the next step n+1 to m is encrypted and
> so on. As an additional requirement we would like the encrypted numbers to
> be numbers (and not letters or other characters) as well.
I think you need to describe a bit more what properties are
required. It might help to read (a) Knuth volume 2, (b) the
Yarrow paper by Scheier et al.
If these are identifying numbers, why wouldn't 1..n be good enough?
Too predictable?
If you worry about the possibility of being able to predict the
next number given the previous bunch, then an LFSR won't do.
Encrypting 1..n would but only so long as you succeed in keeping
the key secret. (I suppose you could encrypt K times with K keys,
each held by a separate party.)
The cryptographic PRNGs don't have that issue, but they do have
another one: you only have probabilistic assurance that the
numbers generated are unique. Especially once you take them mod 10^10,
the fact that you have 10^9 of them means you may have a fair
chance of duplication. (Then again, that's your field, I flunked
that course... :-) )
paul
------------------------------
From: [EMAIL PROTECTED] (DJohn37050)
Subject: Re: Are small block sizes less secure?
Date: 01 Oct 1999 15:58:04 GMT
There are 2 types of attacks, key attacks and block attacks. Smaller blocks
allow better block attacks.
Don Johnson
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: Compress before Encryption
Reply-To: [EMAIL PROTECTED]
Date: Fri, 1 Oct 1999 15:43:14 GMT
Douglas A. Gwyn <[EMAIL PROTECTED]> wrote:
: Tim Tyler wrote:
:> Since so much crypto-research goes on behind closed doors, it may
:> eventually emerge (when the technique becomes more widespread), that
:> it was in fact invented years ago - but never escaped from government
:> custody.
: I'm sure that precompression is mentioned in several places
: in the open literature.
Indeed. However is precompression that fails to have error correction
and consequently offer clues to the attacker that they have found a
correct key mentioned?
: The term "one to one" has a technical meaning different from the way
: D.Scott uses the term, so it is not used that way in the literature.
It seems to me that he is using the term in the same way that everyone
else uses it. What is the "technical meaning" of which you speak?
: I think the plain fact is that the small amount of structure
: from the compression header is generally not considered sufficient
: to exploit, given that a cipher is already infeasible to brute-force
: even in a known-plaintext attack.
It's trivially true that if you're cypher is already totally secure then
adding more security won't help.
However, why have less security than is easily possible? Who are
you to say that the system is /so/ secure that adding more security is
pointless?
: Therefore nobody other than D.Scott has spent much time worrying about
: this aspect. The gain in security from squelching the source statistics
: is so significant that it dominates the other issue.
Sequlching the source statistics is desirable; but simultaneously
introducing an insecurity whereby an automated search through the
space of the keys has an increased probability of identifying the
plaintext automatically is surely something to be avoided.
D.Scott has identified a (pretty obvious) way of doing this; and built
what currently seems to be the world's first compression program designed
to compromise the security of the resulting message as little as possible.
So far from this group I've seen little but negative comments. People
have claimed that the feature is useless, or that it doesn't increase
the security of systems which are subject to known plaintext attacks -
or even that compression is pointless in terms of security.
As far as I can see all these technical points are wrong. Employing
correct compression technology is the right thing to do. It does help
with security issues. Why use encryption technology that compromises
security when D.Scott's compression is now available for download?
If I were D.Scott I would find this hostility bewildering: don't
you understand the security implications properly? Are you part of
a NSA conspiracy designed to keep people using a technique with
unnecessary security problems?
--
__________
|im |yler The Mandala Centre http://www.mandala.co.uk/ [EMAIL PROTECTED]
You have junk mail.
------------------------------
** 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
******************************
