Cryptography-Digest Digest #808, Volume #9 Wed, 30 Jun 99 15:13:03 EDT
Contents:
Re: Moores Law (a bit off topic) (Jim Felling)
Re: A Quanitative Scale for Empirical Length-Strength (Jim Gillogly)
Re: Secure link over Inet if ISP is compromized. (Alan Braggins)
Re: trapdoor one way functions (Medical Electronics Lab)
How to find the period of a sequence ("cairus")
Re: Hamming Weight, sample code (Francois Grieu)
Re: How to find the period of a sequence (Mok-Kong Shen)
How serious is related key attack? (Robert Scott)
Re: A Quanitative Scale for Empirical Length-Strength (Mok-Kong Shen)
Re: Performance of cryptographic algorithms (Medical Electronics Lab)
Re: one time pad (William Tanksley)
Re: Secure link over Inet if ISP is compromized. (Jim Felling)
Re: Performance of cryptographic algorithms (Mok-Kong Shen)
Re: Why mirrors invert left-to-right (was: Kryptos article) ("Paul Pires")
Re: A Quanitative Scale for Empirical Length-Strength (Jim Gillogly)
Re: two questions (William Tanksley)
----------------------------------------------------------------------------
From: Jim Felling <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Subject: Re: Moores Law (a bit off topic)
Date: Wed, 30 Jun 1999 11:14:25 -0500
[EMAIL PROTECTED] wrote:
> In article <[EMAIL PROTECTED]>,
> [EMAIL PROTECTED] wrote:
>
> > I have my doubts as to the "permanent" security of 128-bit codes --
> mind you
> > for the very long term they are damn near perfect -- if I
> want "permanent"
> > security I'd go with 256-bit.
> >
>
> Really well I will teleport us 200 years into the future. RSA-128 bit
> challenges are on the block. I have my 250Ghz program running 2^64 keys
> a second... blah blah blah. Now how strong is a 256 bit key? It will
> only be another 100 years before it falls.
>
> Never say permanent. For now 64 - 128 bit keys are more then enough,
> well I wouldn't use 64-bit keys for long term (> 1 year) stuff but you
> know...
>
> 256 bit keys are not use effectively in most ciphers so I will have to
> wait for AES to come out. In which case I will have to assume that no
> attack is faster on that cipher then 2^255 effort...
>
> > Reasoning:
> > assume a computer can be built from 1 atom.
>
> Even quantum theory doesn't assume a computer is one atom. They assume
> they can control many atoms to perform their task. (I am not big in qt
> so back up a bit...). Even at your rate of 2^70 which I find highly
> non-probable for a very long time (assuimg we do actually progress).
> Most computers only have 2^28 cycles so let's say this doubles every
> 1.5 years... 100 years = 66 periods. this would get you your 2^70 (it
> would be about 2^94)....
I was attempting to design the "best system possible" given that we are
making our computers out of atoms, and transmitting data using speed of
light based data transmission. Given those assumptions, the best possible
clock speed is (speed of light)/(radius of chosen atom) anything with a
clock speed faster than that is impossible given the above assumptions.
This combined with the assumption that we convert a planetary mass to
computing, (and power it with a sun!) I feel are reasonable upper bounds on
the amount of comitable resources to break a key.
>
>
> This debate has been going on for a long time. I think it's quite
> futile as well most standard methods of attacks are squeemish...
>
> Tom
> --
> PGP key is at:
> 'http://mypage.goplay.com/tomstdenis/key.pgp'.
>
> Sent via Deja.com http://www.deja.com/
> Share what you know. Learn what you don't.
------------------------------
From: Jim Gillogly <[EMAIL PROTECTED]>
Subject: Re: A Quanitative Scale for Empirical Length-Strength
Date: Wed, 30 Jun 1999 10:11:33 -0700
Mok-Kong Shen wrote:
> Applying the classical transposition cipher twice (with different keys
> having different lengths) is a superencipherment. However, it
> appears certain that the result is not equivalent to encryting once in
> the same manner with a certain key. So I wonder whether one can
In fact, I believe Courville showed that double transposition is
equivalent to single transposition with a much longer key. I'd have
to go back and check.
> determine your length-strength of the total as a function of the
> length strength of the underlying two components. By the way,
> there are people saying that the scheme is hard to crack. I just
> want to call attention to that. Perhaps you could propose one such
> problem to ACA and see if someone could solve it.
Double transposition has indeed surfaced several times in the ACA's
publication "The Cryptogram". If memory serves, the problems were
in depth -- i.e. suitable for multiple anagramming and key recovery.
If you'd like to post a double transposition of (say) in the
neighborhood of 150 letters with keys of (may as well be specific)
11 and 12 letters to sci.crypt, we could all have a go at it. Do
double-check your encipherment, though -- it's a nuisance to burn
cycles on an incorrectly-enciphered problem.
--
Jim Gillogly
Sterday, 7 Afterlithe S.R. 1999, 17:05
12.19.6.5.15, 6 Men 3 Tzec, Seventh Lord of Night
------------------------------
From: Alan Braggins <[EMAIL PROTECTED]>
Subject: Re: Secure link over Inet if ISP is compromized.
Date: 30 Jun 1999 17:00:00 +0100
[EMAIL PROTECTED] (S.T.L.) writes:
> <<face-to-face conversations, are compromised, >>
>
> By compromised, do you mean monitored or prevented? If you monitor a
> face-to-face conversation between me and Bob, then we can still
> exchange public keys and know we can communicate safely.
Tamper with - if you can't recognise Bob, or they can replace him with
a sufficiently good double, then they can replace him so you really
exchange public keys with the opponent. (Or prevent, so that you have
to use an alternative mechanism they can tamper with).
------------------------------
From: Medical Electronics Lab <[EMAIL PROTECTED]>
Subject: Re: trapdoor one way functions
Date: Wed, 30 Jun 1999 11:54:51 -0500
Nicol So wrote:
> I think you missed my point. I'm not asking for the definition of a
> trapdoor one-way function (which I understand perfectly well). By
> convention, a trapdoor one-way function is, loosely speaking, a function
> which is easy to compute in the "forward" direction, but hard in the
> "reverse" direction *without the trapdoor information*. By this
> convention, discrete log is not even a candidate for a one-way
> function--modular exponentiation is!
You are correct, I don't understand your point. Discrete log is the
inverse of modular exponentiation. It could be I'm being too lose
with the definitions. So what is it your looking for (assuming you've
gotten the right answer so far)?
Patience, persistence, truth,
Dr. mike
------------------------------
From: "cairus" <[EMAIL PROTECTED]>
Subject: How to find the period of a sequence
Date: Wed, 30 Jun 1999 18:17:34 +0200
Does anyone know which is the best
algorithm to find the period of a given
sequence (I remember something like
the Floyd algorithm, but I forgot the
details)?
Thank you very much,
Cairus
------------------------------
From: [EMAIL PROTECTED] (Francois Grieu)
Subject: Re: Hamming Weight, sample code
Date: Wed, 30 Jun 1999 19:40:56 +0200
[EMAIL PROTECTED] wrote :
> What is a Hamming Weight and how does one calculate it ?
The hamming weight of a bit vector is the number of bits set in the vector,
also called it's Population Count. This is usefull in some cryptanalysis
applications. Rumor is that the NSA has mandated POPCOUNT in the
instruction set of some computers.
If a bit vector is represented as an "unsigned long", any of the
following three obfuscated functions will quickly determine it's
hamming weight / population count.
Francois Grieu
/* Popcount1 : count bits in input
optimised for speed on 'sparse' input
execution time grows linearly with the result
no dependancy on size of unsigned long
*/
int Popcount1(unsigned long x)
{ int n = 0;
if (x) {
do ++n; while ((x &= x-1)!=0);
}
return n;
}
/* Popcount2 : return number of bits set in x
table-based method, 8 bits at a time
execution time grows with the rank of leftmost non-empty chunk
no dependancy on size of unsigned long
*/
int Popcount2(unsigned long x)
{ int n = 0;
const char pop8[256] = {
0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4,
1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,
1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,
2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,
2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,
2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8
};
do n += pop8[x & 255]; while ((x >>= 8)!=0);
return n;
}
/* Popcount3 : return number of bits set in x
optimised for speed on random input, on architectures with fast modulus.
execution time is constant (except for variation on execution of final
modulus)
As is, limited to 32 bit unsigned long, but just expanding the
three hex constants will fix this, up to 254 bit architectures
*/
int Popcount3(unsigned long x)
{ x = ((x>>1)&0x55555555UL) + (x&0x55555555UL);
x = ((x>>2)&0x33333333UL) + (x&0x33333333UL);
return (((x>>4)+x)&0x0F0F0F0FUL) % 255;
}
/* validation suite for Popcount1 / Popcount2 / Popcount3 above */
#include <stdio.h>
int main(void)
{ unsigned long x,y;
int i1,i2,i3;
long err;
err = 0;
x = 0; err = 0;
do
{ i1 = Popcount1(x); i2 = Popcount2(x); i3 = Popcount3(x);
if (i1!=i2 || i1!=i3)
if (++err <= 12) printf("error :%5d%5d%5d for 0x%lX\n",i1,i2,i3,x);
/* the following will step x thru a reasonable range of values */
y = x; x += x>>14; x += 1;
} while (x>y);
printf(err==0?"test pass\n":"test fails, %d errors\n",err);
return 0;
}
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: How to find the period of a sequence
Date: Wed, 30 Jun 1999 19:24:28 +0200
cairus wrote:
>
> Does anyone know which is the best
> algorithm to find the period of a given
> sequence (I remember something like
> the Floyd algorithm, but I forgot the
> details)?
I haven't read published algorithms for this. I do it this way:
Take the first element A_1 and try to match the following. If it
matches A_i then see if A_2 matches A_(i+1). If not proceed further,
if yes see if A_3 matches A_(i+2) and so on. It is not difficult to
write a procedure to do that. If there more elegant ways, I also like
to learn them.
M. K. Shen
------------------------------
From: [EMAIL PROTECTED] (Robert Scott)
Subject: How serious is related key attack?
Reply-To: [EMAIL PROTECTED]
Date: Wed, 30 Jun 1999 17:32:24 GMT
>From an application point of view, how serious is a
related key attack? Specifically, which applications
would suffer if the cipher used were vulnerable to a
related key attack? I can see how things like a chosen
plaintext or chosen ciphertext attack might actually
happen where the attacker gets temporary custody of
an encryption machine. But how would and attacker go
about capitalizing on a cipher whose only weakness was
to related key?
Bob Scott
Ann Arbor, Michigan (email: rscott (at) wwnet (dot) net )
(My automatic return address is intentionally invalid.)
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: A Quanitative Scale for Empirical Length-Strength
Date: Wed, 30 Jun 1999 19:35:31 +0200
Jim Gillogly wrote:
>
> In fact, I believe Courville showed that double transposition is
> equivalent to single transposition with a much longer key. I'd have
> to go back and check.
If you find the reference, please let us know the essentials of
the proof. More or less on intuition I thought that that might be
impossible in general.
M. K. Shen
------------------------------
From: Medical Electronics Lab <[EMAIL PROTECTED]>
Subject: Re: Performance of cryptographic algorithms
Date: Wed, 30 Jun 1999 12:32:05 -0500
Peter Krueger wrote:
> I'm looking for a survey of the performance of cryptographic
> algorithms, symmetric, asymmetric and one-way hashs.
> Fine would be an analysation of efficient algorithms in
> the O-Notation.
It's pretty much all over the place. What's efficient in an
FPGA is horrible in a 16 bit microcontroller. In general,
hash functions which are programmed as unrolled (no loops)
are faster (but consume more rom) than looped hashes.
Hash is faster than symmetric which is faster than asymmetric.
"performance" is really hard to pin down. For some applications
speed is more important than space. For others, cost is the
most important and speed can be sacrificed. That's one of the
reasons there are so many algorithms, they all have advantages
and disadvantages for any particular application.
The best thing to do is to pin down the application and then look
for algorithms advertised to perform within that realm. Then,
if possible, try a few of them on your hardware and see how they
do. You'll get far more accurate information that way.
Patience, persistence, truth,
Dr. mike
------------------------------
From: [EMAIL PROTECTED] (William Tanksley)
Subject: Re: one time pad
Reply-To: [EMAIL PROTECTED]
Date: Wed, 30 Jun 1999 18:22:07 GMT
On Wed, 30 Jun 1999 05:19:31 GMT, Greg Ofiesh wrote:
>> I am 100% certain that they do not have such a device. Such a machine
>> cannot be built in this universe, regardless of the technology.
>Show me the physics. I need the physics. Why can't POSSIBLY a quantum
>computer be built in this universe?
I'm almost certain that he's talking about the 1k-bit key cracker, not the
quantum computer. A quantum computer could, of course, crack a 1kbit key,
if anything I've heard about it is true.
I have my suspicions.
>Sent via Deja.com http://www.deja.com/
--
-William "Billy" Tanksley
------------------------------
From: Jim Felling <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Subject: Re: Secure link over Inet if ISP is compromized.
Date: Wed, 30 Jun 1999 12:35:38 -0500
Else wrote:
> Jim Felling wrote in message <[EMAIL PROTECTED]>...
> >That is incorrect. Any internet encryption sceme is as secure as the
> >parameters allow it to be.
>
> Show please how SSL is secure against man-in-the-middle attack.
>
> >If, for example, a trusted certification authority/ trusted public key
> >collection exists, internet communication is as secure as that
> certification
> >authority/trusted key repository are. (Trusted authority)
>
> How do you access this authority? Whould not it be thorough the ISP?
When I claim a "trusted authority" I am claiming that we somehow have trust
that this authority is who we think they are, and that the information
that they provide is valid.
If someone can completely control your access to all foms of communication
with this authority then you cannot trust that authority. (It boils down to
the exchange between A and B case above)
If not a simple "Do you hold a key for me with the fingerprint XXXXXXX"
request to the authority using some other means of communication will
succeed. Or an access of a authority using a publicly published key
(assuming that the ISP does not control the media that you access)
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Performance of cryptographic algorithms
Date: Wed, 30 Jun 1999 20:22:32 +0200
Medical Electronics Lab wrote:
>
> It's pretty much all over the place. What's efficient in an
> FPGA is horrible in a 16 bit microcontroller. In general,
> hash functions which are programmed as unrolled (no loops)
> are faster (but consume more rom) than looped hashes.
> Hash is faster than symmetric which is faster than asymmetric.
Concerning FPGA I read a newspaper saying one company is building
a computer for supercomputing with FPGAs, utilizing the fact the
FPGAs can be adapted to the problem being solved and that it
intends to later also produce PCs on the same basis with three
times the power of current top PCs at the cost of only 1000 dollar.
>
> "performance" is really hard to pin down.
Yes. It certainly depends quite a lot on how the program is designed.
M. K. Shen
------------------------------
From: "Paul Pires" <[EMAIL PROTECTED]>
Subject: Re: Why mirrors invert left-to-right (was: Kryptos article)
Date: Wed, 30 Jun 1999 11:24:43 -0700
Major Snip:
<>
Come on you guys, This is not an analytical problem, it's and indication of
or ability to automatically assume.
Draw a picture of the light paths from image to eye. Nothing flips, Nothing
rotates. Or, if you want to get technical and include the optics within the
eye, nothing flips or rotates inconsistently.
The image in the mirror is a south side image of a north facing person.
We compare that In our (alleged) minds to a south facing person.
This assumed south facing person (we compare to) must rotate 90 degrees
about a vertical axis or we would see his backside, not his front. Our
assumptions are inviolate so the image must rotate. It doesn't.
If the confounding image was a transparency, we could correct the image by
walking around it and viewing it from the other side. In essence, double
correcting our assumed rotation and thereby canceling it out.
A simple mind is a terrible thing to waste.
Paul
------------------------------
From: Jim Gillogly <[EMAIL PROTECTED]>
Subject: Re: A Quanitative Scale for Empirical Length-Strength
Date: Wed, 30 Jun 1999 11:20:55 -0700
Mok-Kong Shen wrote:
>
> Jim Gillogly wrote:
>
> > In fact, I believe Courville showed that double transposition is
> > equivalent to single transposition with a much longer key. I'd have
> > to go back and check.
>
> If you find the reference, please let us know the essentials of
> the proof. More or less on intuition I thought that that might be
> impossible in general.
Rather than doing this, I'll give you a demo that you can extend into
a proof. Here's a cryptogram based on your previous paragraph encrypted
with keys "baced" and "dfbeac".
PTTLH SNTYK ETMAP UNNSO SESIB IUOAA LHHEF TUMDE SGEOH EEIIP NHSIN
TMHRE EOIFS RTLEF IBREN EUORA SEFTE RATOF WLTHL OTNCO NIENT IITEM
ESRGG ELIST EOHON OHK
This can be solved as a double transposition with those two keys,
or as an incomplete columnar with this 30-letter key:
gpcDsvzmjCbfryiluBexqahodAkwtn
The capital letters are intended to follow the lower-case ones.
I didn't "cook" this example: just encrypted it with the two
keys and solved the resulting one as an incomplete columnar.
I conjecture that Courville's monograph (to which I refer you for
the actual proof) will show that the result is the product or the
LCM of the two key lengths.
By the way, the double transposition that I suggested you provide
(key lengths 11 and 12) would have a key-space of about 2^54.
--
Jim Gillogly
Sterday, 7 Afterlithe S.R. 1999, 18:12
12.19.6.5.15, 6 Men 3 Tzec, Seventh Lord of Night
------------------------------
From: [EMAIL PROTECTED] (William Tanksley)
Subject: Re: two questions
Reply-To: [EMAIL PROTECTED]
Date: Wed, 30 Jun 1999 18:27:17 GMT
On Wed, 30 Jun 1999 04:50:07 GMT, Douglas A. Gwyn wrote:
>William Tanksley wrote:
>> DES-OFB uses a block cipher to generate a keystream, which is XORed
>> into the plaintext. Obviously, any block cipher could be used in OFB
>> mode.
>Yes, but you're not using it as a block cipher any more, just as a
>PRNG running totally independently of the input plaintext.
Eh? Of course you're not using it as a block cipher -- the statement I
was contradicting was, "it's impossible to make a block cipher into a
stream cipher."
Proof by construction. I like it ;-).
--
-William "Billy" Tanksley
------------------------------
** 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
******************************
