Cryptography-Digest Digest #763, Volume #11 Sat, 13 May 00 00:13:00 EDT
Contents:
Re: (May 11, 2000) Cipher Contest Update ([EMAIL PROTECTED])
Re: Question regarding authentication implementation (Abid Farooqui)
none ("kala marai")
Re: Two basic questions (Ricardo)
Re: Two basic questions (Ricardo)
Re: Two basic questions (Ricardo)
Using TEA in one-way hash function ("kala marai")
Re: How does one test an encryption algorithm? ("Scott Fluhrer")
Re: Using TEA in one-way hash function (Andru Luvisi)
Re: Prime Generation in C,C++ or Java (Bryan Olson)
Re: Deciphering Playfair (long) (UBCHI2)
Re: Prime Generation in C,C++ or Java (Bryan Olson)
Re: Key generation for lja1 (David A. Wagner)
Re: Key generation for lja1 (David A. Wagner)
----------------------------------------------------------------------------
From: [EMAIL PROTECTED]
Reply-To: [EMAIL PROTECTED]
Subject: Re: (May 11, 2000) Cipher Contest Update
Date: Fri, 12 May 2000 18:04:07 -0700
I do not agree with this definition of "breaking" a cipher. The stipulation that
there cannot be any attack faster than brute force is arbitrary. If brute force
attack takes N steps than any attack that takes N - epsilon, epsilon > 0 is
considered as "breaking" the cipher. I think a cipher should be considered
unbroken if recovering the plaintext is computationally infeasible.
If a cipher A with 128 bit key can be deciphered with computational effort
equivalent to brute force attack at 127-bit cipher, and 127-bit cipher B cannot
be broken by any means other than brute force, but cipher B takes 10 times as
much time to encrypt/decrypt than A, then A is a better cipher.
Stream ciphers can have such a large state space that the number of key bits can
be set arbitrarily.
Joseph Poe
Adam Durana wrote:
> I am going to start doing periodical postings about the contest. Right now
> there are five ciphers in the listing. The one at the top of the list is
> LETSIEF2, which was submitted April 7th. The original LETSIEF was
> successfully analyzed by Matthew Fisher. Matthew Fisher has submitted a
> cipher called VORTEX and it is in second place at the moment. Next there is
> another cipher from the author of the LETSIEF ciphers, Boris Kazak, named
> MMBOOZE. Next in fourth place is PIKACHU and LJA1, by Tom St Denis and
> Andru Luvisi respectively. These two ciphers were submitted today (May
> 11th).
>
> Ciphers are removed from the listing once they have been broken. Anyone can
> participate in the contest. Everything you need to know to get your
> submission together is at http://www.wizard.net/~echo/crypto-contest.html
> Take a look at some of the other submissions for a better idea of what a
> submission should look like.
>
> I would like to define on the web site what it means to break a cipher, so
> the cipher is removed from the listing. Right now all the page states is
> that to get a cipher removed the attack has to be on the full version of the
> cipher, i.e. no reduced round variants. I would define a successful attack
> as an attack which is able to recover the plaintext, or key from the
> ciphertext, with less work than brute force. Now if the key space was say
> 1024 bits, and attack came up that would recover the key or plain text with
> 2^1000 work, should that still be considered an attack good enough to get
> the cipher removed? Obviously no one is going to be able to actually use
> that attack for a while, if ever. But I think when someone publishes a
> cipher for analysis, they are saying that the only attack they can come up
> with is brute force. Any attack better than that would be a break through.
> So if an attack arises that can recover the key or plaintext faster than
> brute force, I think that attack should get the cipher removed from the
> listing. Keep in mind this is a contest of cipher design.
>
> - Adam
------------------------------
From: Abid Farooqui <[EMAIL PROTECTED]>
Subject: Re: Question regarding authentication implementation
Date: Sat, 13 May 2000 01:04:34 GMT
Dear Mr. Denis,
Thanks for the prompt reply.
Actually the cert queue will have both the CA keys as well as partner
certificates and there is automatic refresh of certificates every day or two
like you mentioned. One would have to delete the partner certificates and
reload them again, manually verifying all the certs against the CA
certificates.
On the second note, the CA certificates will be from VeriSign, Thawte and
may be other similar CAs not an intranet situation at all. Actually bulk of
the data transfers and connections will be made using the internet.
Given these facts what do you think?
Thanks
Abid Farooqui
Tom St Denis wrote:
> In article <[EMAIL PROTECTED]>,
> Abid Farooqui <[EMAIL PROTECTED]> wrote:
> > I have an interesting scenario for you guys to battle over. I myself
> > cannot make up my mind for sure but lean towards a certain position in
> > this.
> > Here goes ...
> > A colleague of mine has developed using BSAFE libraries a security
> > application that does authentication at connection startup and
> > encryption when data is transferred. The client certificates, Root
> > certificates and client or partner certificates are stored in so
> called
> > queue. When you load a client/partner certificate you can VERIFY that
> > certificate against a list of available CA Root certificates that you
> > already have in the queue. This is a completely separate step and is
> > done in a non-active manner, meaning this happens way before the
> > client/partner is establishing any kind of connection to you.
> > Now, that you have a clinet/partner certificate loaded into a
> queue ...
> > when the client/partner establishes connection to you, he/she will
> send
> > a NONCE(Dummy message) signed with his/her private key to prove his
> > identity to you. When you receive the NONCE, you can try and decrypt
> it
> > using this partner's Public Key that you have already loaded into the
> > queue, if it decrypts etc. etc. then it must be the partner because
> only
> > he/she has his/her private key.
> > Now what troubles me here is that my colleague is not going ahead at
> > this point and verifying this partner's key against the list of loaded
> > CA Root certificates at the connection establishing time. What if I
> > decide that I don't trust this particular Root CA anymore and thus I
> > delete it from the certificate queue or what if the Root CA
> certificate
> > has been expired or even revoked. Since all my colleague's application
> > is doing is verifying partner's certificate only at load time into the
> > queue and never again. All certificates signed by this Root CA
> > certificate will still authenticate a connection to me even if the
> Root
> > CA certificate has expired some time later or I have deleted it
> because
> > I don't trust it anymore or it has been revoked. I will physically
> have
> > to remove certificates from the cert queue of all clients/partners who
> > had certificates issued by this CA to get them to not authenticate
> with
> > me.
> > Does this seem like a standard implementation of public cryptographic
> > algorithms to you? Is my concern warranted or not?
> > Thanks in advance.
> > Sincerely,
> > Abid Farooqui
>
> Depends upon the period between refreshes of the CA queue. If it's
> only a day or so, that's not bad. If it waits a year before changing
> keys that can be bad.
>
> Typically you want to not change keys every three minutes, but the
> ability to dynamically switch keys is a good idea.
>
> It really depends on the target as well. If you are using keys from a
> sys-admin in an Intranet you don't want to switch the keys often since
> you use them to verify requested public keys, etc.
>
> Maybe I misunderstood... just my 2c.
>
> Tom
>
> Sent via Deja.com http://www.deja.com/
> Before you buy.
------------------------------
From: "kala marai" <Use-Author-Address-Header@[127.1]>
Date: Fri, 12 May 2000 18:06:20 PDT
Subject: none
can i use TEA in a hash function???
the way i am currently using is by encryption a rnd value(or should be 0, or
msg size?), using the text i wanna hash as key, and increasing the
displacement by 64bits(1/2 of tea keysize), in such way that all block,
except the first and last, are once the lower part of the key, and once the
upper
or can i use the "modified Davies-Meyer" that bruce schneider say in 18.11
of applied crypto, but using TEA instead of IDEA???
collision isnt a problem
kala-marai
________________________________________________________________________
Get Your Private, Free E-mail from MSN Hotmail at http://www.hotmail.com
------------------------------
From: Ricardo <[EMAIL PROTECTED]>
Subject: Re: Two basic questions
Date: Sat, 13 May 2000 03:17:53 +0200
Emol eng Keier huet Jerry Coffin <[EMAIL PROTECTED]> an engem
Artikel vum Sat, 6 May 2000 14:04:15 -0600 an der Newsgroup
sci.crypt geschriwen:
>This would be unlikely to slow most attacks enough to notice. In
>most cases, an attacker isn't using dictionary lookups to verify a
>proper decryption. Instead, he's likely to use statistical analysis
>of the result. To throw this off by much, you'd have to do things
>like changing the frequency of using particular digraphs -- e.g. make
>sure you virtually never use "th", substitute various other things
>for 'e' most of the time, and so on.
Indid dat izz prisisli da poynt ov uzin badd spelin. Notis how I
rarli uz da letar "e" and da dygraff "th" in dizz playntext and yett
it rimaynz qwit izi to undastand.
>Ultimately, it's hard to imagine a situation in which this would make
>a noticeable difference to an attacker.
I agri butt iff wun uziz weri badd spelin in da playntext den it
kould konsivubli ward off simpul miinz ov kriptanalysis by havvin da
ifekkt ov dizztawghting da ballans ov friqqwinsizz in da text. Ov
kors dizz iz stil werri farrh fromm randamm...
According to Singh's "Code Book" though, cryptanalytical experts
could handle bad plaintext spelling, homophones, nulls etc. as early
as the 17th century. So much for that means of "security".
--
ricardo icq# 51047940 gsm# +352091511692
esch/alz lux ue obtenez pgp @ http://www.pgpi.com/
"Tu te sens comme je me sens, ou suis-je tout seul?"
d'Regierung as eng Gefor fir d'Fraiheet - votez libertarian!
------------------------------
From: Ricardo <[EMAIL PROTECTED]>
Subject: Re: Two basic questions
Date: Sat, 13 May 2000 03:17:54 +0200
Emol eng Keier huet Tom St Denis <[EMAIL PROTECTED]> an engem Artikel
vum Sat, 06 May 2000 03:31:23 GMT an der Newsgroup sci.crypt
geschriwen:
>> Why don't people just use bad spelling and/or grammer before encrypting
>> messages? If my plain text reads "We-uns gonna tack purl harber
>> toonite" and I take reasonable trouble to not be consistent in my
>> misspellings, it seems like even a simple substitution cipher would
>> throw off most machines for a long time. After all, nothing would match
>> a dictionary lookup...
>
>For the simple reason I know you are saying "We are gonna attack perl
>harbor tonight".
Obviously but I think his point was that (very) bad spelling is a
traditional method of thwarting frequency analysis because it is not
difficult to rewrite English in a way that the most common letters
and digraphs are never used, and yet it is still quite
comprehensible to readers (see my other post).
Note that the 200 page novel "La Disparition" by Geroges Perec was
written without using the letter E at all! Even more amazingly, the
English translation entitled "A Void" also does not contain the
letter E, not even once. It is surprisingly readable, albeit
slightly peculiar due to the lack of what is normally the most
commonly used letter in the English alphabet. Unconditionally
applying frequency analysis in such cases would fail.
>Hey I think all serious crypto people start this way (being bored at
>school) I know I did.
I wouldn't describe myself as a "serious crypto person" but am
certainly interested in the science (art?). But yes I do admit that
it was partly through boredom in school that I became interested...
--
ricardo icq# 51047940 gsm# +352091511692
esch/alz lux ue obtenez pgp @ http://www.pgpi.com/
"Tu te sens comme je me sens, ou suis-je tout seul?"
d'Regierung as eng Gefor fir d'Fraiheet - votez libertarian!
------------------------------
From: Ricardo <[EMAIL PROTECTED]>
Subject: Re: Two basic questions
Date: Sat, 13 May 2000 03:17:55 +0200
Emol eng Keier huet "Douglas A. Gwyn" <[EMAIL PROTECTED]> an engem
Artikel vum Sun, 07 May 2000 08:34:47 GMT an der Newsgroup sci.crypt
geschriwen:
>kidwalden wrote:
>> Why don't people just use bad spelling and/or grammer before encrypting
>> messages? If my plain text reads "We-uns gonna tack purl harber
>> toonite" ...
>
>That still has a lot of the statistical characteristics of English.
Dat exxampul didd but iff wun iz klevva inuff wun kan surtunli
rimmuuv most ov da kommon letarz - ivvun widdowt badd spelin in da
kas ov Jorjj Perikk huu roat da bookk "La Disparition".
>A big problem is that the more you corrupt the natural language,
>the greater the chance that the intended recipient will misread it.
Kan you ridd wot I amm rytin ryt now widdowt tuu manyy probblimmz? I
amm not ov kors in any way sujjistin dat dizz meffud izz a sirius
way ov maykin a simpul monoalffabetikk subbstituschun cyfar sikkur
but it izz surtunly a purffikktly sownd way ov fworting friqqwynsy
anallysis.
--
ricardo icq# 51047940 gsm# +352091511692
esch/alz lux ue obtenez pgp @ http://www.pgpi.com/
"Tu te sens comme je me sens, ou suis-je tout seul?"
d'Regierung as eng Gefor fir d'Fraiheet - votez libertarian!
------------------------------
From: "kala marai" <Use-Author-Address-Header@[127.1]>
Subject: Using TEA in one-way hash function
Date: Fri, 12 May 2000 18:28:36 PDT
can i use TEA in a hash function???
the way i am currently using is by encryption a rnd value(or should be 0, or
msg size?), using the text i wanna hash as key, and increasing the
displacement by 64bits(1/2 of tea keysize), in such way that all block,
except the first and last, are once the lower part of the key, and once the
upper
or can i use the "modified Davies-Meyer" that bruce schneider say in 18.11
of applied crypto, but using TEA instead of IDEA???
collision isnt a problem
kala-marai
________________________________________________________________________
Get Your Private, Free E-mail from MSN Hotmail at http://www.hotmail.com
------------------------------
From: "Scott Fluhrer" <[EMAIL PROTECTED]>
Subject: Re: How does one test an encryption algorithm?
Date: Fri, 12 May 2000 18:19:58 -0700
Mark Wooding <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> Richard Heathfield <[EMAIL PROTECTED]> wrote:
>
> > > Or use one of those well-tested algorithms already available, such
> > > as Blowfish, or Rijndael, Serpent, Twofish, or others.
> >
> > Yeh yeh yeh, and how much fun is /that/ for a programmer? :-)
>
> Actually, I found both Rijndael and Twofish to be rather interesting to
> implement. They took me about a day's work each, from blank source
> files to an implementation which passed the AES test vectors, and lots
> of the hair-tearing and head-slapping which I find tends to accompany
> debugging of crypto primitives.[1]
>
> [1] The problem is that the algorithm will tend to either give you the
> right answer, or something utterly unrelated to the right answer
> giving you no clue as to what exactly it was that went wrong. And
> while this is right and proper for a strong block cipher, it's a bit
> of pain when writing the things.
Really good test vectors include the state of the cipher at internal states,
for example, after each round. This makes tracking down what's not working
*much* easier.
--
poncho
------------------------------
From: Andru Luvisi <[EMAIL PROTECTED]>
Subject: Re: Using TEA in one-way hash function
Date: 12 May 2000 18:46:42 -0700
"kala marai" <Use-Author-Address-Header@[127.1]> writes:
[snip]
> can i use TEA in a hash function???
[snip]
The original TEA had a related key attack which made it unsuitable for
use as a hash function. XTEA reportedly fixed the problem, so I would
recommend using XTEA instead.
Andru
--
==========================================================================
| Andru Luvisi | http://libweb.sonoma.edu/ |
| Programmer/Analyst | Library Resources Online |
| Ruben Salazar Library |-----------------------------------------|
| Sonoma State University | http://www.belleprovence.com/ |
| [EMAIL PROTECTED] | Textile imports from Provence, France |
==========================================================================
------------------------------
From: Bryan Olson <[EMAIL PROTECTED]>
Subject: Re: Prime Generation in C,C++ or Java
Date: Sat, 13 May 2000 01:47:34 GMT
John Myre wrote:
[...]
> What's wrong with the interface?
First, and beside the original point, there's the
constructor-abuse resulting in the prime generator being
called "BigInteger". Should it be obvious that the way to
turn two integers and an RNG into a large integer has
something to do with primality? It would be much better as a
static function so we could include "prime" in its name. I
suppose we could define a subclass called "BigPrime" and
then a constructor would be fine. Let's give the poor
code-readers all the help we can.
And ...
> From a caller's point of view, it seems just right. [...]
I disagree. The exposed functions, even if implemented
efficiently, are not useful in building efficient generators
for primes of important special forms, for example DSA
primes. To find DSA primes I want to simultaneously sieve
for candidate pairs (q, p=d*q+1) where neither has a small
factor, then do exactly one iteration of Miller-Rabin (with
base 2) on q, then if that passes do the same on p, then if
that passes do several randomized iterations to certify
both. I have to write my own sieve and Miller-Rabin test
because the class doesn't expose the ones it already has.
--Bryan
--
email: bolson at certicom dot com
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: [EMAIL PROTECTED] (UBCHI2)
Subject: Re: Deciphering Playfair (long)
Date: 13 May 2000 02:36:22 GMT
Switch to two grid playfair with a double interrupted transposition before
encipherment and then after encipherment. Nothing can get through that
------------------------------
From: Bryan Olson <[EMAIL PROTECTED]>
Subject: Re: Prime Generation in C,C++ or Java
Date: Sat, 13 May 2000 03:08:05 GMT
David Hopwood wrote:
> That's not necessarily the case (that 98 is the number of iterations),
> and you do need to know the interface details. Here they are:
[...]
> I.e. the contract is only that there is less than (1/2)^certainty
> probability of the result being non-prime, and that the running
> time is linear in the certainty parameter.
>
> It would be perfectly valid for an implementation of
> java.math.BigInteger to adjust the number of iterations to
> the minimum required to achieve the given probability
I disagree; Mark Wooding has a point. The run-time comment
appears in the interface, which indicates that the authors
think implementations should perform as stated.
The expected run time of the implementation is
\Theta(bitLength^4 + bitLength^3 * iterations).
"Linear in the certainty parameter" only describes
implementations that are based on the misunderstanding Mark
pointed out. (And doesn't even describe those very well.)
If practice the bitLength^4 term should dominate. The
expected time to find the first candidate that passes one
test iteration should dominate the time to certify the
candidate with further iterations.
I grant that David has a point too: an implementation is
wellcome to deliver on the contract at below the stated
cost. Still, the contract is a bad deal.
--Bryan
--
email: bolson at certicom dot com
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: [EMAIL PROTECTED] (David A. Wagner)
Subject: Re: Key generation for lja1
Date: 12 May 2000 20:44:54 -0700
Why should we expect that all of the key[] array will be initialized?
Or, why should we expect that the key[] array will yield a permutation?
Perhaps I am misreading the code, but it's not clear to me that either
is guaranteed from the algorithm below. I must be confused.
And, while I'm at it, why does the main loop start at i=254 and not i=255?
Also, are you expecting that the following algorithm will yield key[]
arrays that have a cycle of length 256? I don't see why it should.
In article <[EMAIL PROTECTED]>,
Andru Luvisi <[EMAIL PROTECTED]> wrote:
>
> Because the hash function for lja1 is basically an eight bit codebook
> run in cipher block chaining mode, and long periods are generally
> considered a good thing in a block cipher, I suspect keys which would
> have a cycle of length 256 would be stronger than keys with shorter
> cycles. In an extreme case, if every key[i] = i, then the compression
> function would not change the accumulator when hashing zero bytes.
>
> Here's my attempt at a key generator. Suggestions invited:
>
> void make_key(unsigned char *key)
> {
> unsigned char numbers[256];
> unsigned char temp;
> unsigned int i, j, next;
> FILE *fp;
>
> if((fp = fopen("/dev/urandom", "r")) == NULL)
> {
> /* a little harsh, but this is demo code */
> fprintf(stderr, "Can't open /dev/urandom\n");
> exit(1);
> }
>
> for(i = 0; i < 256; i++)
> numbers[i] = i;
>
> next = 255;
> for(i = 254; i > 0; i--)
> {
> fread(&j, sizeof(j), 1, fp);
> j = j % (i + 1);
> temp = numbers[i];
> numbers[i] = numbers[j];
> numbers[j] = temp;
> key[next] = numbers[i];
> next = numbers[i];
> }
>
> key[next] = numbers[0];
> next = numbers[0];
> key[next] = 255;
>
> fclose(fp);
> }
>
------------------------------
From: [EMAIL PROTECTED] (David A. Wagner)
Subject: Re: Key generation for lja1
Date: 12 May 2000 20:56:34 -0700
In article <8fe4an$kn1$[EMAIL PROTECTED]>,
Tom St Denis <[EMAIL PROTECTED]> wrote:
> I would just do something like this:
>
> for i = 0 to 767 do
> x = rand() mod 256
> y = rand() mod 256
> swap(x, y);
> next i
This looks fishy. The probability that any given element is untouched by
one iteration of the loop is about 1 - 2/256. The probability that this
element remains untouched after all 768 iterations of the loop is about
(1 - 2/256)^{768} ~= e^{-6}. Thus, the probability that all elements
are touched is about (1 - e^{-6})^{256} ~= 0.53. In other words,
the probability that some element remains untouched is about 0.47.
Is that bad? It sounds like a small remaining bias. (These calculations
are all heuristics, but they may be reasonable as a first approximation.)
Anyway, the right way to do this is with the following loop:
for i = 0 to 255 do
A[i] = i
for i = 255 downto 0 do
j = a random integer from 0 to i
swap(A[i], A[j])
See Knuth. This is a FAQ.
Note that this algorithm is (1) 3--6 times faster than your proposal;
(2) provably unbiased, if the random number generator is; and (3)
(almost) the same as what the previous poster suggested.
------------------------------
** 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
******************************
