Cryptography-Digest Digest #853, Volume #9 Thu, 8 Jul 99 19:13:03 EDT
Contents:
Re: Weakness of MLCG style encryption ([EMAIL PROTECTED])
Re: The Constrained One-Time Pad and the Cryptanalyst's Lucky Day (John Savard)
Re: somewhat optimization works... (PRNG code) ([EMAIL PROTECTED])
CHES Conference Preliminary Program (Jorge Guajardo)
New Encryption Product! (humor) (John Savard)
Re: Why this simmetric algorithm is not good? (Jerry Coffin)
Re: Why this simmetric algorithm is not good? ([EMAIL PROTECTED])
Re: The Constrained One-Time Pad and the Cryptanalyst's Lucky Day
([EMAIL PROTECTED])
Re: The Constrained One-Time Pad and the Cryptanalyst's Lucky Day
([EMAIL PROTECTED])
----------------------------------------------------------------------------
From: [EMAIL PROTECTED]
Crossposted-To: sci.math
Subject: Re: Weakness of MLCG style encryption
Date: Thu, 08 Jul 1999 20:17:08 GMT
In article <[EMAIL PROTECTED]>,
Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
> I used LCPRNG in the code which is intended as an exemplarly
> implementation of my idea. The scheme of using a bunch of constituent
> generators is, on the other hand, general. You can use whatever type
> of constituent generators you want (or even several different types
> at once).
Well when using different types you have to make sure their periods are
relatively prime.
> That's exactly the 'deficit' not benefit in my view. Why couldn't
> you afford to have a large number of generators? Yes, one knows
> only relatively few good PRNGs in the literature. In my scheme
> I (pseudo-)randomly generate the constituent generators. Since
> the parameters of these are randomly chosen, the chance that any
> individual constituent generator is good is very small. On the
> other hand employing a large number of them (through intermixing
> their output sequences) compensates the deficiency of qualities
> of the individual constituent generators. Of course, if you have
> a number of good PRNGs, you certainly can also use them as
> constituent generators in my scheme and that would very likely give
> you a better result than the randomly chosen ones for the same number
> of constituent generators. But since in my code the constituent
> generators are automatically created, I can employ a higher number
> of these to compensate for that deficiency. I hope that the above
> is sufficient to explain the 'philosophy' underlying my design.
> If you have further questions about my compound PRNG, I'll try my
> best to answer them.
Having fewer is not a deficit. Have you heard of a divide-and-conquer
attack? It worked against A5. If you rely on using many LCG you will
only prolong the attack, not serious hinder it.
Besides why use 256 generators (which must all have different lengths)
instead of one or two? Algorithm M if you are interested works like
this
int temp, x;
x = PrngA() % SIZE;
temp = delay[x];
delay[x] = PrngB();
return temp;
This has the effect of throwing the ouputs of B out of order, this
makes it hard to solve for. In a LCG it is too predictable, however
with LFSRs and additive generators this works great. You can use one
generator as well. If you assume PrngA() is 'random' then the lower
bits used as a index must be random as well.
In my DDARNG I use two generators with a 8-bit delay buffer. You can
check it out (it's in my C++ code). My scheme uses 370 bytes of ram,
RC4 uses 259 bytes, if you can fit your PRNG in less then 1KB then it's
probably worth while to look at.
Generally I would suggest against using many generators because they a)
take too much ram and b) are hard to ensure max length...
Tom
--
PGP key is at:
'http://mypage.goplay.com/tomstdenis/key.pgp'.
Free PRNG C++ lib:
'http://mypage.goplay.com/tomstdenis/prng.html'.
Sent via Deja.com http://www.deja.com/
Share what you know. Learn what you don't.
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: The Constrained One-Time Pad and the Cryptanalyst's Lucky Day
Date: Thu, 08 Jul 1999 21:19:57 GMT
"Tony T. Warnock" <[EMAIL PROTECTED]> wrote, in part:
>Of course the Soviet spies used a super-encypherenment with a OTP during
>(and prior to) WWII. The Venona project broke them anyway.
But only because the Soviets did not *really* use an OTP. The NSA
still doesn't have technology adequate to predicting next week's
PowerBall numbers, which is essentially the equivalent problem to
cracking a real OTP, conscientiously used.
They are brilliant minds, with powerful equipment. But miracles are
beyond even their power.
John Savard ( teneerf<- )
http://members.xoom.com/quadibloc/crypto.htm
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: somewhat optimization works... (PRNG code)
Date: Thu, 08 Jul 1999 20:22:24 GMT
In article <[EMAIL PROTECTED]>,
Terje Mathisen <[EMAIL PROTECTED]> wrote:
> OK, I'll do some proof reading for you:
>
> Your version will run at least one cycle slower/iteration because you
> are using pre-increment of the indices, which means that you have two
> additional load operations in the critical path.
>
It won't run slower then the first version, because the first version
had the pre increment and branch. The 'x = ni1[++x]' should optimize to
mov eax,[x]
mov eax,[x + 1 + offset ni1]
mov [x],eax
This should run in about 3 cycles (stalls). But the other was
mov eax,[x]
cmp eax,54
jl _A
xor eax,eax
jmp _B
_A:
inc eax
_B:
mov [x], eax
Which is no faster.
> Otherwise it should work just like your original code, except that all
> accesses will be one item later.
No they won't either (I hope) in the constructor I sub'd one from the
indexes so they start 'early'. For example y1 starts at 53 which when
passed thru 'y1 = ni1[++y1]' = 54
Thanks for the quick peak. Anything else I should know about?
Tom
--
PGP key is at:
'http://mypage.goplay.com/tomstdenis/key.pgp'.
Free PRNG C++ lib:
'http://mypage.goplay.com/tomstdenis/prng.html'.
Sent via Deja.com http://www.deja.com/
Share what you know. Learn what you don't.
------------------------------
From: Jorge Guajardo <[EMAIL PROTECTED]>
Subject: CHES Conference Preliminary Program
Date: Thu, 8 Jul 1999 16:58:20 -0400
Please find below the prelinarary program of the CHES workshop. For
registration information, please see
http://ece.wpi.edu/Research/crypt/ches
=======================================================
PRELIMINARY PROGRAM
Workshop on Cryptographic Hardware and Embedded Systems
Worcester, Massachusetts, August 12-13, 1999
=======================================================
--- THURSDAY, AUGUST 12 ---
Welcome by Ed Parrish (President, WPI)
Introductory remarks by Cetin Koc and Christof Paar
Invited Talk: Brian Snow, National Security Agency, USA
We Need Assurance
Session: CRYPTANALYTICAL HARDWARE
A. Shamir
Factoring large numbers with the TWINKLE device
I. Hamer and P. Chow
DES cracking on the Transmogrifier 2a
--- break ---
Session: HARDWARE ARCHITECTURES
W.P. Choi and L.M. Cheng
Modeling the crypto-processor from design to synthesis
D.C. Wilcox, L.G. Pierson, P.J. Robertson, E.L. Witzke, and K. Gass
A DES ASIC suitable for network encryption at 10 Gbps and beyond
E. Hong, J.-H. Chung, and C.H. Lim
Hardware design and performance estimation of the 128-bit block
cipher CRYPTON
Session: SMART CARDS AND EMBEDDED SYSTEMS
K. Itoh, M. Takenaka, N. Torii, S. Temma, and Y. Kurihara
Fast implementation of public-key cryptography on a DSP TMS320C6201
P.J. Lee, E.J. Lee, and Y.D. Kim
How to implement cost-effective and secure public key cryptosystems
--- lunch break ---
Invited Talk: Colin D. Walter, Computation Department - UMIST, U.K.
An Overview of Montgomery's Multiplication Technique:
How to make it Smaller and Faster
Session: ARITHMETIC ALGORITHMS
A.F. Tenca and C.K. Koc
A scalable architecture for Montgomery multiplication
J.H. Silverman.
Fast multiplication in finite fields GF(2^N)
B. Kaliski and M. Liskov
Efficient finite field basis conversion involving dual bases
--- break ---
Invited Talk: Eberhard von Faber, Debis IT Security Services, Germany
Security Evaluation Schemes for the Public and Private
Market with a Focus on Smart Card Systems
Session: POWER ATTACKS I
T.S. Messerges, E.A. Dabbish, and R.H. Sloan
Power analysis attacks of modular exponentiation in smartcards
L. Goubin and J. Patarin
DES and differential power analysis
P. Fahn and P. Pearson
IPA: A new class of power attacks
--- CHES Banquet on the WPI Campus, sponsored by Technical ---
--- Communications Corporation, MA ---
--- FRIDAY, AUGUST 13 ---
Invited Talk: Dale Hopkins, Compaq - Atalla, USA
Design of Hardware Encryption Systems for
e-Commerce Applications
Session: TRUE RANDOM GENERATORS
V. Bagini and M. Bucci
A design of reliable true random number generator for
cryptographic applications
D. Maher and B. Rance
Random number generators founded on signal and information theory
--- break ---
Session: CRYPTOGRAPHIC ALGORITHMS ON FPGAS
R.R. Taylor and S.C. Goldstein
A high-performance flexible architecture for cryptography
E. Mosanya, C. Teuscher, H.F. Restrepo, P. Galley, and E. Sanchez
CryptoBooster: A reconfigurable and modular cryptographic coprocessor
L. Gao, S. Shrivastava, and G.E. Sobelman
Elliptic curve scalar multiplier design using FPGAs
Session: GALOIS FIELD ARCHITECTURES
H. Wu, M.A. Hasan, and I.F. Blake.
Highly regular architectures for finite field computation using
redundant basis
H. Wu
Low complexity bit-parallel finite field arithmetic using polynomial
basis
--- lunch break ---
Invited Talk: David Naccache, Gemplus, France
Significance Tests and Hardware Leakage
Session: POWER ATTACKS II
J.-S. Coron
Resistance against differential power analysis attacks for
elliptic curve cryptosystems
H. Handschuh, P. Paillier, and J. Stern
Probing attacks on tamper-resistant devices
--- break ---
Session: ELLIPTIC CURVE IMPLEMENTATIONS
J. Lopez and R. Dahab
Fast multiplication on elliptic curves over GF(2^m) without
precomputation
Y. Han, J. Zhang, and P.-C. Tan
Direct computation for elliptic curve cryptosystems
Session: NEW CRYPTOGRAPHIC SCHEMES AND MODES OF OPERATION
M. Hartmann, S. Paulus, and T. Takagi
NICE - New Ideal Coset Encryption -
T. Horvath
Arithmetic design for permutation groups
O. Jung and C. Ruland
Encryption with statistical self-synchronization in synchronous
broadband networks
===========================================================
Invited talks are 40 min, regular presentations 20 min long
The Thursday program is from 9:00 am - 6:00 pm,
the Friday program is from 8:30 am - 4:30 pm
========================================================
Workshop on Cryptographic Hardware and Embedded Systems
Worcester, Massachusetts, August 12-13, 1999
=======================================================
Information: http://ece.wpi.edu/Research/crypt/ches
E-Mail: [EMAIL PROTECTED]
Program Chairs: Cetin Kaya Koc & Christof Paar
[EMAIL PROTECTED] & [EMAIL PROTECTED]
=======================================================
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Crossposted-To: alt.security.pgp
Subject: New Encryption Product! (humor)
Date: Thu, 08 Jul 1999 21:11:27 GMT
SOMEWHERE, U.S.A. (July 8):
Based on a study of common USENET posts by encryption program users,
Recondite Systems Inc., has discovered that encryption program users
commonly want two things from an encryption program:
- they want it to be so secure that even major government agencies
can't possibly break the code;
- they want to be able to download a program to run on their own home
computers to crack the encryption in about half an hour if they forget
the password.
"They said it couldn't be done", said Recondite Systems engineer Snute
Crawley, "but we managed to design a product that meets both of these
apparently conflicting requirements simultaneously".
A number of alternative technologies for achieving this goal suggested
themselves at the outset, but were rejected on various grounds.
- Generate a large random key that would encrypt a backup file of
decryption keys, and which would be stored on a floppy disk.
"This meant users would have to put the floppy disk in the computer
each time, and so it would be stored beside the computer," Crawley
noted.
- Place a master key on a dongle.
"Basically, the same objection, only worse."
- Use fingerprint recognition technology, with the user's fingerprint
as the master key.
"Sure, some encryption users have their fingerprints on file with the
FBI, but that's just a plus factor; we can advertise that our products
can't be abused by criminals. However, there aren't enough bits there
for easy use."
Eventually, though, a way around the problem was found. A special
keyboard is supplied with the program, with a radio reciever that
communicates with a dongle that the user can wear as a ring. "Of
course, we have to encrypt communications with the ring, so there's a
spot on the keyboard to which the user touches the ring before
starting a session."
And, in case the ring is lost, the same key material as is stored in
the ring is also in a file, encrypted by data based on the user's
fingerprints. "We supply a cardboard diagram explaining how to
generate a key from fingerprint patterns. This is less expensive than
a fingerprint scanner, although we did try to research bringing the
cost down."
The short size of the key thus generated is prevented from being a
problem, because the fingerprint card also has a long serial number
printed on it that the user also has to type in. "We were going to
license EKE technology to make a short key stronger, until we realized
that it only performs privacy amplification by encrypting even the
public keys: when you need access to a private key, your security is
no bigger than the key that opens the door behind which the private
key is stored."
And this information is also on another disk file, which is encrypted
with yet another emergency backup key, stored on a floppy disk
accompanying the original software package. "Since only the key for
the key backup file needs to be used every time by the program, and
that key doesn't change, the key for backup files in which that fixed
key is stored can be kept in a safe place."
John Savard ( teneerf<- )
http://members.xoom.com/quadibloc/crypto.htm
------------------------------
From: [EMAIL PROTECTED] (Jerry Coffin)
Subject: Re: Why this simmetric algorithm is not good?
Date: Thu, 8 Jul 1999 14:44:07 -0600
In article <7m2eeh$di7$[EMAIL PROTECTED]>, [EMAIL PROTECTED]
says...
[ ... ]
[ rewriting ]
> x = (x + 1) & 255
> y = y + state[x]
[ as ]
> y += state[x = (x + 1) & 255]
[ ... ]
> In fact RC4 can be written in about 3 or so lines of code. This makes
> the code faster on most machines and more compact on microcontrollers.
> It makes it harder to read as well.
It's open to argument whether it's harder to read, but there's little
room for argument that with the vast majority of compilers, rewrites
like this will make absolutely NO difference whatsoever in the object
code. I'd almost go so far as to say that any compiler that produced
different object code for these two pieces of code wasn't working
correctly, but that might be over-stating things a bit.
In any case, a rewrite like this is rarely likely to have any effect
at all on the size of speed of the object code.
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Why this simmetric algorithm is not good?
Date: Thu, 08 Jul 1999 21:15:45 GMT
In article <7m32i8$mn5$[EMAIL PROTECTED]>,
[EMAIL PROTECTED] wrote:
> Tom St Denis's code is not a good example.
You are not perfect and I will prove it.
> Today, most optimizing compilers will produce the
> same code either way.
Why risc it :)
> But definitely not as
>
> y += state[x++];
>
> which is what Tom used in his C++ code. If the
> increment of x were a separate statement, it would
> not matter that it's a post-increment where RC4
> requires a pre-increment. Tom's also assuming
> (without comment) that unsigned char holds only the
> values 0 through 255. ANSI/ISO C requires it to
> hold at least that range of values.
Well this has the same effect as long as chars are 8-bits. It will use
x then increment it (which is what you have todo) then add the state[x]
to y. That's RC4 for you.
You can always use an extra '&255' if you are not sure, but that makes
the code slightly longer and slower. Plus almost every platform I have
worked on uses 8-bit chars. It's kinda a standard (people associate
chars with ASCII or bytes...)
>
> Tom has now given us two implementations of the
> simple RC4 algorithm, both of them wrong. He had
> an example implementation code to work from, so it
> seems that both bugs were the result of his
> attempts at optimization.
RC4 is hard to get wrong. I don't see what's wrong with my code except
for the explitcit use of char=8bits...
Here is my understanding of RC4:
y = (y + Sx) mod 256
x = (x + 1) mod 256
swap(Sx, Sy)
z = (Sx + Sy) mod 256
return Sz
> x = ni[x+1];
> y = ni[y+1];
> state[x] += state[y];
> return state[x];
Much better is
return state[x = ni[x + 1]] += state[y = ni[y + 1]];
Which has the effect of keeping something in the accumulator. It's
also shorter. Your code has a superfluous load from 'state[x]' (i.e
not perfect).
I made the 'assumption' that '++x' can be optimized, maybe I shouldn't
have. By removing the '++x' and replacing it with 'x + 1' ALL
compilers will optimize it by not forcing a second store...
> Keeping recently used values handy is among the
> first optimizations compiler authors implement.
> Optimizing away the side effect in the ++x and ++y
> is less common. A decent compiler will do both,
> but why code a useless side effect? It's one
> possibly valuable feature is that it makes the
> reader suspicious of the code's correctness.
You have a point. I will change it to 'x + 1' in my C++ code.
> Nonsense. Static storage and the heap are at least
> as bad as the stack.
Well normally stack usage is harder to track. All you have todo is
memset the round keys when you are done. Most people would not know
how to clear 4KB of stack space... (well it's not hard but most don't
think of it), in fact there is no ANSI standard way to clear stack
space...
Tom
--
PGP key is at:
'http://mypage.goplay.com/tomstdenis/key.pgp'.
Free PRNG C++ lib:
'http://mypage.goplay.com/tomstdenis/prng.html'.
Sent via Deja.com http://www.deja.com/
Share what you know. Learn what you don't.
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: The Constrained One-Time Pad and the Cryptanalyst's Lucky Day
Date: Thu, 08 Jul 1999 21:42:38 GMT
In article <[EMAIL PROTECTED]>,
[EMAIL PROTECTED] wrote:
> Of course the Soviet spies used a super-encypherenment with a OTP
during
> (and prior to) WWII. The Venona project broke them anyway.
>
>
Then they didn't use a OTP.
I think people are missing the point, you cannot break a OTP because
all plaintexts are equally valid. You can guess at the plaintext until
you are satistified, but you cannot be sure, and you can't really use
that knowledge to guess the rest of the keystream (although if you are
sure you have one message the other messages might make more sense with
the knowledge...)
Tom
--
PGP key is at:
'http://mypage.goplay.com/tomstdenis/key.pgp'.
Free PRNG C++ lib:
'http://mypage.goplay.com/tomstdenis/prng.html'.
Sent via Deja.com http://www.deja.com/
Share what you know. Learn what you don't.
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: The Constrained One-Time Pad and the Cryptanalyst's Lucky Day
Date: Thu, 08 Jul 1999 21:40:23 GMT
In article <HXXdWEA$[EMAIL PROTECTED]>,
Toby Kelsey <[EMAIL PROTECTED]> wrote:
> In article <7lst5f$cts$[EMAIL PROTECTED]>, [EMAIL PROTECTED]
writes
> >In theory the OTP is truly the only secure method.
>
> Really?
>
> I intercept your OTP encoded message, for which I know the plaintext
to
> be either "Yes" or "No". The ciphertext is 2 characters long......
>
> So much for "theoretically unbreakable".
That's saying all messages are fixed. What if I said no in french, so
much for your break. Normally I would pad the message (say to 32
bytes) so the length reveals little of the contents.
> The OTP allows any same-length decrypted message to be equally likely,
> but requires a key the same length as the message. You can devise
> methods which have shorter keys and still allow many possible
decrypted
> messages. The OTP is only "simpler" and "more secure" because the
> algorithmic complexity is hidden in the RNG and its testing. There is
> less latitude for error in the encryption implementation, but more
> reliance is placed on the quality of the RNG and the secure channel.
There is no way to test a RNG though. The OTP is secure because the
ciphertext is as 'random' as the RNG. No matter what the plaintext was.
>The bottom line is, I would not feel safer just knowing a OTP was being
>used to encrypt my messages.
Why do people claim OTP security then if it's not secure?
BTW no block cipher or stream cipher can be OTP secure so that's not a
realistic goal.
Tom
--
PGP key is at:
'http://mypage.goplay.com/tomstdenis/key.pgp'.
Free PRNG C++ lib:
'http://mypage.goplay.com/tomstdenis/prng.html'.
Sent via Deja.com http://www.deja.com/
Share what you know. Learn what you don't.
------------------------------
** 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
******************************
