Cryptography-Digest Digest #221, Volume #12 Thu, 13 Jul 00 16:13:01 EDT
Contents:
For Your Information ("Tony T. Warnock")
Re: Random numbers and online-gambling (Scott Nelson)
Re: Bit Shuffling (Ichinin)
Is there any bright mind who have 5 seconds to spare? (Ichinin)
Re: New Idea - Cipher on a Disk ("Joseph Ashwood")
Re: Cryptographic Camouflage ("Joseph Ashwood")
Re: Concepts of STRONG encryption using variable base (Bradley King)
Re: Who was that girl? (Derek Bell)
Re: Is there any bright mind who have 5 seconds to spare? (John Myre)
Re: Proposal of some processor instructions for cryptographical (Terje Mathisen)
Re: Proposal of some processor instructions for cryptographical (Terje Mathisen)
Re: Cryptographic Camouflage (John Myre)
Re: attack against CBC mode (David Hopwood)
On intermixing as encryption processing (Mok-Kong Shen)
Re: attack against CBC mode (DJohn37050)
----------------------------------------------------------------------------
From: "Tony T. Warnock" <[EMAIL PROTECTED]>
Subject: For Your Information
Date: Thu, 13 Jul 2000 12:08:13 -0600
Reply-To: [EMAIL PROTECTED]
"Period of the power generator and small values of Carmichael's
function"
Author(s): John B. Friedlander; Carl Pomerance; Igor E.
Shparlinski.
Journal: Math. Comp.
The above paper (preprint available from AMS server, if you are a
subscriber) shows that both the RSA and BBS generators are very likely
to have a long cycle.
------------------------------
From: [EMAIL PROTECTED] (Scott Nelson)
Subject: Re: Random numbers and online-gambling
Reply-To: [EMAIL PROTECTED]
Date: Thu, 13 Jul 2000 18:13:43 GMT
On Thu, 13 Jul 2000 15:30:02 GMT, [EMAIL PROTECTED] wrote:
>Hi!
>
>Some weeks ago I found a web-page containing
>an analysis of an online-poker system. There
>was described how the shuffling of the cards
>was done and why the chosen approach was not
>appropriate for online-gambling. A description of
>how to break the game including countermeasures
>was given. The report was IIRC about one year old.
>
>As I do not remember in detail the analysis
>of the permutation-algorithm and the flaws in
>the random number generation, I tried several
>search-engines, but with no appropriate results.
>If someone has a hint for me where the report
>can be found or where I can continue my search,
>that would be great!
>
Sounds like Mike Caro, and Planet Poker.
Their shuffling routines have supposedly been fixed.
(I think Mike works for them now)
However, they still refuse to disclose the details
of the new system, so I'd take their claims with a
grain of salt.
If you can't find it on the web, you might try
checking the dejanews archives for rec.gambling.poker
from about a year ago.
Scott Nelson <[EMAIL PROTECTED]>
------------------------------
From: Ichinin <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Subject: Re: Bit Shuffling
Date: Thu, 13 Jul 2000 20:08:57 +0200
Did a similar thing back in 98.
I'll post it now to discourage other "inventors" to patent
group(n)-bit rotations.
Here's an extract, but the whole idea: (You'll see quickly how it works)
_______________________________________________________________________
...We start of by knowing the values
I =7
B = "11001010" ( = the current Bitsegment)
This will be permutated as follows:
11001010 <- Indata (You cannot rotate 1 bit)
11000101 = (2 bits) 11 00 01 01
01110010 = (3 bits) 011 100 10
11100100 = (4 bits) 1110 0100
00111001 = (5 bits) 00111 001
01110010 = (6 bits) 011100 10
10011100 = (7 bits) 1001110 0
Reversing it to decrypt:
10011100 = Indata
01110010 = 7 bits
00111001 = 6 bits
11100100 = 5 bits
01110010 = 4 bits
11000101 = 3 bits
11001010 = 2 bits
Also, you need to flipp the entire string left to right for each
iteration.
So - 11001010 would become 010100011..
_______________________________________________________________________
There, now it's a published text. Try patent that.
Glenn
Sweden
------------------------------
From: Ichinin <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Subject: Is there any bright mind who have 5 seconds to spare?
Date: Thu, 13 Jul 2000 20:29:43 +0200
Hi people.
I'm trying to create a feistel cipher for fun.
Still, it's not reversible (Ok, it 75% "reversible" :oP)
So what's the smeg is wrong with it?
______________________________________
Partial source:
- The F() function IS 100% reversible (Belive me, i've checked.)
- I'm starting at X-1 as i should do [0]
- I'm also flipping halves according to specs.
Data go in one end: l_d & r_d (left data & right data)
void encrypt()
{
for (x = 1; x < 17; x++)
{
// first it swap halves and call the F() function
l_d[x] = r_d[x-1];
r_d[x] = l_d[x-1] ^ f(r_d[x-1]);
}
}
Then after encrypt() is called (after it have exited):
r_r[0] = l_r[16]; l_r[0] = r_r[16]; // it swaps halves.
______________________________________________
Output:
ccccaaaa (Plaintext)
aaaa52e1 , round: 1
52e17459 , round: 2
7459cbe1 , round: 3
cbe1d8ce , round: 4
d8ce4200 , round: 5
42006d44 , round: 6
6d4490e6 , round: 7
90e6774f , round: 8
774f2084 , round: 9
2084e160 , round: a
e1601986 , round: b
1986c548 , round: c
c5485adc , round: d
5adca61d , round: e
a61d203f , round: f
203f8622 , round: 10
203f8622 (Crypttext)
203f929a , round: 1
929a3eb7 , round: 2
3eb74174 , round: 3
417418b5 , round: 4
18b58ee , round: 5
8eee7d1 , round: 6
e7d1509d , round: 7
509d3da1 , round: 8
3da1aa11 , round: 9
aa11211b , round: a
211b5368 , round: b
53684fdd , round: c
4fdd9aa7 , round: d
9aa7ecf3 , round: e
ecf3aaaa , round: f
aaaa4659 , round: 10
4659aaaa (Plaintext) <-- DOOH! |o}
Thanks in advance,
Glenn
Sweden
------------------------------
From: "Joseph Ashwood" <[EMAIL PROTECTED]>
Subject: Re: New Idea - Cipher on a Disk
Date: Thu, 13 Jul 2000 11:21:58 -0700
I think I wrote that out too quickly. In every protocol there is a maximum
number that can be used, at least with static protocols like I suspect
(although I admit I have never sufficiently read the specification) that the
IDE/EIDE/UDMA/SCSI/etc protocols, have a static address range, probably
[0,2^n-1] for some defined n. I was suggesting using the block 2^n-1 to
perform what appears (on the bus) as a regular write, which will actually
trigger a different response in the harddrive, specifically changing the key
used in the cipher, this would normally not impact the volume of the drive,
or the bad sector list. I base this on the fact that there are drives on the
market right now from a few GB to almost 50 GB, I assume there is still some
growth room before a new protocol is required. I called this sideband,
simply because it makes abnormal use of the protocol (probably not the best
choice of terminology).
Joe
"Trevor L. Jackson, III" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
>
>
> Joseph Ashwood wrote:
>
> > > But the harder problem is getting the key from the user to
> > the disk. There's
> > > no existing mechanism for this.
> >
> > Sure there is, use sideband information. Write to a location
> > on disk that cannot exist. There must be a maximum address
> > on the disk, simply reduce the maximum disk size by one
> > block, and "write" to the last block so set the password.
>
> First, writing to a sector isn't really sideband, it's reusing the main
band.
> Thus it may collide with other special purpose uses of the last block.
>
> Also, "the last block" is rarely well defined. Typically the
manufacturer's
> bad sector list is written on the last few tracks, and spare tracks (for
> dynamic track remapping) are allocated from that end of the drive. Adding
> another reserved section to the drive map adds considerable complexity due
to
> the layers of hard and software that know about the existing special
purpose
> sections.
>
> I think this concept needs a true sideband channel -- one that extends the
> interface between the drive and the world. Such extension is hard to do
> transparently.
>
------------------------------
From: "Joseph Ashwood" <[EMAIL PROTECTED]>
Subject: Re: Cryptographic Camouflage
Date: Thu, 13 Jul 2000 11:36:27 -0700
Actually, I do have experience with their designs. Arcot does only
authentication. This authentication is done as a digital
signature, with a bit of a twist as follows:
Original RSA parameters:
e
d
pq
Arcot Authentication Parameters:
E = encrypted version of e (using strong methods, 3DES is the current)
D = encrypted version of d (lightly encrypted, a strong cipher with a small
pin), there's actually more to it, there are some bits that are left clear
because they can be verified without knowlede of e
PQ = pq in clear
Authentication protocol:
Client:
Get challenge C from server
Decrypt D to get probably d
compute X= (C+ padding)^d mod PQ
send X to the server
Server:
decrypt E to get e
compute (M+padding) = X^e mod PQ
verify M as a recent valid challenge
So basically RSA is used as a secret key algorithm, and unless it becomes
possible to verify more information about d without knowledge of e there is
little question that (under reasonable pretense) it is secure. As a
scientist I do have to tell you that YMMV and that based on information that
may be available at some future time my opinion could change vastly, I also
feel it is prudent to inform you that I work for Arcot, in case you feel the
need to discount me as potentially biased.
Joe
"Andrew Wong" <[EMAIL PROTECTED]> wrote in message
news:8kk5cr$poe$[EMAIL PROTECTED]...
> I recently came upon this product, called WebFort, developed by Arcot
> Systems Inc., that uses cryptographic camouflage to secure keys in a
> software container.
>
> Pse advise if anyone has experience on this product and what are your
> comments.
>
> Regards,
> Andrew
>
>
------------------------------
From: Bradley King <[EMAIL PROTECTED]>
Subject: Re: Concepts of STRONG encryption using variable base
Date: Thu, 13 Jul 2000 15:18:20 -0400
To be really picky, it's: touch�.
phil hunt wrote:
> On Tue, 11 Jul 2000 07:45:24 GMT, Bryan Olson <[EMAIL PROTECTED]> wrote:
> >[EMAIL PROTECTED] wrote:
> >> Tuche! (how do you spell that? Its the words you say
> >> when you raise a sword at another person. And what
> >> does it mean anyways?)
> >
> > ,
> >It's spelled touche and it means "touch".
>
> "touched", actually. Its the past participle of "toucher".
>
> --
> ***** Phil Hunt ***** send email to [EMAIL PROTECTED] *****
> Moore's Law: hardware speed doubles every 18 months
> Gates' Law: software speed halves every 18 months
------------------------------
From: Derek Bell <[EMAIL PROTECTED]>
Subject: Re: Who was that girl?
Date: 13 Jul 2000 20:14:07 +0100
David A Molnar <[EMAIL PROTECTED]> wrote:
: Typing "science talent search" into Google or other
: search engine will probably pull those out.
The original contest was the _Young Scientist_ contest in Ireland.
Derek
--
Derek Bell [EMAIL PROTECTED] | Socrates would have loved
WWW: http://www.maths.tcd.ie/~dbell/index.html| usenet.
PGP: http://www.maths.tcd.ie/~dbell/key.asc | - [EMAIL PROTECTED]
------------------------------
From: John Myre <[EMAIL PROTECTED]>
Subject: Re: Is there any bright mind who have 5 seconds to spare?
Date: Thu, 13 Jul 2000 13:14:37 -0600
Ichinin wrote:
>
<snip>
> - The F() function IS 100% reversible (Belive me, i've checked.)
Irrelevant - not necessary.
<snip>
> Then after encrypt() is called (after it have exited):
> r_r[0] = l_r[16]; l_r[0] = r_r[16]; // it swaps halves.
<snip>
> ccccaaaa (Plaintext)
>
> aaaa52e1 , round: 1
> 52e17459 , round: 2
> 7459cbe1 , round: 3
> cbe1d8ce , round: 4
> d8ce4200 , round: 5
> 42006d44 , round: 6
> 6d4490e6 , round: 7
> 90e6774f , round: 8
> 774f2084 , round: 9
> 2084e160 , round: a
> e1601986 , round: b
> 1986c548 , round: c
> c5485adc , round: d
> 5adca61d , round: e
> a61d203f , round: f
> 203f8622 , round: 10
>
> 203f8622 (Crypttext)
Shouldn't that be 8622203f? (Because of swapping halves after.)
>
> 203f929a , round: 1
<snip>
Already wrong; it should be 203fa61d (exactly undoing the last
round of the encrypt, except of course reversed). Continuing,
you should get
203fa61d
a61d5adc
5adcc548
...
52e1aaaa
aaaacccc
<snip>
Question: is f() really stateless, as implied by your code sample?
Or does it act differently in each round? If it acts differently,
then you have to call it in reverse order for decrypting.
Or maybe it's just an ordinary coding bug. For instance, did you
remember to declare l_r[17] and r_r[17] (and not [16])?
JM
------------------------------
From: Terje Mathisen <[EMAIL PROTECTED]>
Crossposted-To: comp.arch
Subject: Re: Proposal of some processor instructions for cryptographical
Date: Thu, 13 Jul 2000 15:50:02 +0200
Eric Fromm wrote:
>
> Terje Mathisen wrote:
> > How many should be cached inside the cpu?
>
> Cray vector systems have implemented a "bit matrix multiply" for many
> years. Two 64-word vectors are multiplied together treating each as a
> 64x64 matrix of 1-bit elements. (A 1-bit multiply is simply a logical
> AND.) This function can be used to apply an arbitrary bit-wise
> permutation on each row of a 64-word operand. The permutation spec would
> be a 64x64 bit sparse matrix (i.e., a 64-word vector) instead of the
> 5x64 bit spec. So this function is useful if the same permutation is to
> be applied many times before the spec is changed.
This is interesting, why do I get the feeling that NSA might have had
some input on the decision to include such an opcode? :-)
Anyway, working with memory-based arrays would be OK for a machine which
was designed from the beginning to not use caches, but today this would
impose a pretty hefty penalty. With two 512-byte operands, each such
operation would claim 1K of whatever L1 cache space was available.
Quoting Andy "Crazy" Glew (from memory): "register-register operations
are, to a first approximation, free. The hard task is to get the data in
and out of the cpu."
>
> >
> > If you must have such a capability, it makes a lot more sense to
> > synthesize it out of a set of smaller building-block operations, maybe
> > based on byte-sized or smaller lookup tables. (I.e. ref the Altivec
> > permute op).
> >
> > Terje
> >
>
> This statement is only true if the area of the execution pipes are a
> large fraction of the over-all resources allocated to a given CPU. At
> some point, the economies change so that dedicated support for efficient
> encryption is not expensive.
Adding opcodes has some cost as well, since it limits how fast you can
decode the instruction stream. (Usually according to some step function,
but there is still a cost related to having many opcdes.)
I'd only add specialized opcodes if the operation they perform is
a) useful to many or an important set of algorithms.
b) hard (i.e. at least 2-3X slower) to define with lower-level
operations.
What would the C pseudo-code for the Cray mod2 matrix mul look like?
Terje
--
- <[EMAIL PROTECTED]>
Using self-discipline, see http://www.eiffel.com/discipline
"almost all programming can be viewed as an exercise in caching"
------------------------------
From: Terje Mathisen <[EMAIL PROTECTED]>
Crossposted-To: comp.arch
Subject: Re: Proposal of some processor instructions for cryptographical
Date: Thu, 13 Jul 2000 15:53:54 +0200
Thomas Womack wrote:
>
> "Dennis Yelle" <[EMAIL PROTECTED]> wrote
>
> > The weakness seems to be that there is only one operation
> > that moves bits from the left half to the right half, or
> > vice versa.
>
> That's familiar; it sounds like the same problem I had when trying to
> construct sorting networks. I reckoned that you could do something clever
> with MMX shuffles, PMIN and PMAX operations, and sort sets of eight shorts
> with 16-bit data attached extremely quickly; it may well be possible, but
> I'm not that clever.
Is that a challenge? :-)
> Not to mention that nobody actually wants to sort
> shorts with 16-bit data attached.
Why not? People use quite a bit of 32+32 bit radix sort, as a way to get
some block of data at least mostly sorted, since this gives much better
cache behaviour afterwards.
Anyway, doing the same with 128-bit Altivec or SSE registers would allow
2 32:32 pairs or a 64:64-bit keys/data pair.
Terje
--
- <[EMAIL PROTECTED]>
Using self-discipline, see http://www.eiffel.com/discipline
"almost all programming can be viewed as an exercise in caching"
------------------------------
From: John Myre <[EMAIL PROTECTED]>
Subject: Re: Cryptographic Camouflage
Date: Thu, 13 Jul 2000 13:23:27 -0600
Joseph Ashwood wrote:
<snip>
> E = encrypted version of e (using strong methods, 3DES is the current)
> D = encrypted version of d (lightly encrypted, a strong cipher with a small
> pin), there's actually more to it, there are some bits that are left clear
> because they can be verified without knowlede of e
> PQ = pq in clear
>
> Authentication protocol:
> Client:
> Get challenge C from server
> Decrypt D to get probably d
> compute X= (C+ padding)^d mod PQ
> send X to the server
> Server:
> decrypt E to get e
> compute (M+padding) = X^e mod PQ
> verify M as a recent valid challenge
<snip>
Is C randomly chosen each time? How about the padding? Do e and d
vary between clients? How about the pin? Does the client know E
or e or both?
JM
------------------------------
Date: Thu, 13 Jul 2000 10:55:15 +0100
From: David Hopwood <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Subject: Re: attack against CBC mode
=====BEGIN PGP SIGNED MESSAGE=====
Serge Vaudenay wrote:
> Research announcement:
>
> The CBC encryption mode hides several weaknesses, although this is not
> so well known. Our laboratory has been developping a ciphertext only
> attack which can apply to any encryption (DES, 3DES, RC5, IDEA) in CBC
> mode as long as the block size is limited to 64 bits. (No matter how
> long the key is.) This holds against SSL, S/MIME, ... whenever the
> plaintext is redundant (like English ASCII text) and the ciphertext is
> long enough.
>
> Our attack requires a large amount of ciphertext (typically a few GB)
> and enables to recover two segments of 8 bytes. We basically look for
> collisions in the set of ciphertext blocks. Then, from the properties
> of the encryption algorithm, the XOR of the two previous ciphertexts
> is equal to the XOR of the two corresponding plaintexts, which enables
> to perform an attack similar to the attack against one-time-pad when
> the key is used twice.
Was this not already well known? I was under the impression that it was
called a "matching ciphertext" attack, and was the primary motivation for
developing 128-bit block ciphers. There is similar leakage of information
for other modes than CBC (e.g. PCBC, and to some extent CFB).
- From the given URL, the research seems to involve demonstrating how much
information can be retrieved in practice for ASCII (or other similarly
redundant) data encrypted in CBC mode. That's fine and useful, but the
above announcement presents this as a completely new attack, which it
isn't.
- --
David Hopwood <[EMAIL PROTECTED]>
Home page & PGP public key: http://www.users.zetnet.co.uk/hopwood/
RSA 2048-bit; fingerprint 71 8E A6 23 0E D3 4C E5 0F 69 8C D4 FA 66 15 01
Nothing in this message is intended to be legally binding. If I revoke a
public key but refuse to specify why, it is because the private key has been
seized under the Regulation of Investigatory Powers Act; see www.fipr.org/rip
=====BEGIN PGP SIGNATURE=====
Version: 2.6.3i
Charset: noconv
iQEVAwUBOW0T1jkCAxeYt5gVAQG5Hgf/SN4YKU69yqn3JBJC4ekLfXFFAhU8peRL
2u9YQeAZmAgOaALJ6oqjeeZqWGJU6a+U4C+dTuKJo82LXrZt2S+QmWjLDloJ0cvZ
6m5ma1LTDID1V2rFosfQyOrRjMRpqahMiMw6+GM3+byD+Wpzewz+pXUu9CmdQpdA
GmBiNbOSloZxvyYCx8adbDJyUD40svcMJTLkrO9vH5kaZZzFkElgr6HXAoHJwRw7
1R1ajAcnH7iuWyNAGeaiEGSIEb6znzT0Fm5+OxU9q1TWK5QEs2LPlWiMpdgF6SSR
ZcOFFhPCofvjbjk9sQEVV7zO7p3+cKLcYe/NfCZeGOW396nSMfCWMg==
=Mo58
=====END PGP SIGNATURE=====
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: On intermixing as encryption processing
Date: Thu, 13 Jul 2000 22:08:40 +0200
Let two ciphertext bit sequences c1_i and c2_i be given,
e.g. being outputs from some block ciphers. With a
real-valued uniformly distributed pseudo-random variable
r() in [0,1), we can do multiplexing to produce one combined
bit stream u_i as follows:
i=j=k=0;
do
i=i+1;
if r() < 0.5 then j=j+1; u_i = c1_j
else k=k+1; u_i = c2_k fi;
od
That is, we intermix the bits of the two given streams in
such a manner that the resulting bits have equal chance of
being originated from the one stream or the other.
Obviously this materially enhances the difficulty of the
opponent, since he has to identify (guess) which bits of
u_i belong to the first stream and which to the second.
For example, if the given bit streams are outputs from a 64
bit block cipher which the opponent happens to have some
effective method of attack, a failure by 1 bit in collecting
together the 64 bits that belong to a ciphertext block is
sufficient to render his efforts futile.
The modification necessary for multiplexing more than two
ciphertext streams is evident.
What if only one ciphertext bit sequence c1_i is given? A
simple (though criticizable, see below) answer is: Substitute
the other with a dummy pseudo-random bit sequence b2_i. Thus
we have
i=j=k=0;
do
i=i+1;
if r() < 0.5 then j=j+1; u_i = c1_j
else k=k+1; u_i = b2_k fi;
od
The critique is, of course, that we have doubled the bandwidth
for sending our messages, since the u_i sequence is on the
average double as long as the information carrying c1_i
sequence. But, on the other hand, we do get benefits from what
we pay: The task of the opponent is now evidently more
difficult than in the previous case in which all bits of u_i
are information carrying and hence could have the potential,
even though practically minute, of being easier identified
than the bits b2 of a stream that has no meaning from the
outset.
A closer look at the above immediately leads to a very useful
generalization. For, since one of the component bit streams is
dummy and conveys no information for the receiver, there is no
reason why we need to specifically choose the probability 0.5
in the expression r() < 0.5 above. It could in principle be
any real value t with 0 < t < 1. Thus we have
i=j=k=0;
do
i=i+1;
if r() < t then j=j+1; u_i = c1_j
else k=k+1; u_i = b2_k fi;
od
This opens a way to easily tune the security of our scheme.
If we choose, for example, t=0.25, then there will be on the
average three time as many dummy b2 bits as the information
carrying c1 bits and consequently the opponent will get much
more confused by these than in the original case with t=0.5
(albeit at correspondingly higher communication cost, of
course).
I have an implementation of the scheme where the c1_i sequence
is from stream encryption, being obtained from the plaintext
bit sequence p_i through xor-ing with a pseudo-random bit
sequence b1_i:
i=j=k=0;
do
i=i+1;
if r() < t then j=j+1; u_i = p_j xor b1_j
else k=k+1; u_i = b2_k fi;
od
M. K. Shen
================================
http://home.t-online.de/home/mok-kong.shen
------------------------------
From: [EMAIL PROTECTED] (DJohn37050)
Date: 13 Jul 2000 19:57:31 GMT
Subject: Re: attack against CBC mode
This was already known and is discussed in the Triple DES ANSI standard as a
potential concern. Hence, AES has 128 bit blocksize.
Don Johnson
------------------------------
** 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
******************************
