Cryptography-Digest Digest #501, Volume #14 Sun, 3 Jun 01 06:13:01 EDT
Contents:
Re: Uniciyt distance and compression for AES ("John A. Malley")
Re: crypt education (anish)
Re: Uniciyt distance and compression for AES (SCOTT19U.ZIP_GUY)
Re: National Security Nightmare? (David Wagner)
Re: Question about credit card number (Roger Fleming)
Re: Luby-Rackoff Theorems? (David Wagner)
Re: Question about credit card number (Roger Fleming)
----------------------------------------------------------------------------
From: "John A. Malley" <[EMAIL PROTECTED]>
Subject: Re: Uniciyt distance and compression for AES
Date: Sun, 03 Jun 2001 00:32:35 -0700
I *think* I see what are saying, here's another paraphrase:
There are 16 strings s1, s3, s4, s5...s17 in the string set S where the
length (in bits) of each string is i, 1 <= i <= 17 and i != 2.
So there is no 2 bit string in S.
Each string in S is compressed to the set M = {m1, m2, m3, m4} AND
encrypted using just four 2-bit keys, k1 = 00, k2 = 01, k3 = 10, k4 =
11. Compression reduces the string si to a message mj that is
enciphered to cryptogram ck.
k1 = 00 selects this compression and this mapping:
s1 <-> m1 = 0 <-> c1 = 0
s3 <-> m2 = 10 <-> c2 = 10
s4 <-> m3 = 110 <-> c3 = 110
s5 <-> m4 = 111 <-> c4 = 111
notice for the 4 messages no mapping to s2 so no two bit output
at this point.
k2 = 01 selects this compression and this mapping:
s6 <-> m1 = 0 <-> c1 = 10
s7 <-> m2 = 10 <-> c2 = 110
s8 <-> m3 = 110 <-> c3 = 111
s9 <-> m4 = 111 <-> c4 = 0
k3 = 10 selects this compression and this mapping:
s10 <-> m1 = 0 <-> c1 = 110
s11 <-> m2 = 10 <-> c2 = 111
s12 <-> m3 = 110 <-> c3 = 0
s13 <-> m4 = 111 <-> c4 = 10
k4 = 11 selects this compression and this mapping:
s14 <-> m1 = 0 <-> c1 = 111
s15 <-> m2 = 10 <-> c2 = 0
s16 <-> m3 = 110 <-> c3 = 10
s17 <-> m4 = 111 <-> c4 = 110
and it's be shown before (back in the March 2001 post referenced in this
thread) why the encipherment of mi into cj has perfect secrecy. When
Eve gets c1, c2, c3 or c4 she learns nothing more about which message mi
Alice sent to Bob than what she already knew.
Eve does know this - the four messages in the set M = { m1, m2, m3 , m4
} occur with probability P(m1) = 1/2, P(m2) = 1/4, P(m3) = P(m4) = 1/8
where P(m_i) means probability of occurrence of m_i. Eve knows the
uncertainty of M, H(M), is
H(M) = - ( - 1/2 * 1 - 1/4 * 2 - 1/8 * 3 - 1/8 *3 ) = 1.75 bits
and thus Alice and Bob encoded the messages as these bit strings
m1 = 0
m2 = 10
m3 = 110
m4 = 111
Here's something interesting. The probabilities of the messages in M
establish constraints on the probabilities of occurrence of the strings
in the set S.
For example, the strings s1, s6, s10 and s14 all compress down to the
message m1. If s1 occurs then k must be 00 and the message must be m1.
If s6 occurs then k must be 01 and the message must be m1. If s10
occurs then k must be 10 and the message must be m1. If s14 occurs then
k must be 11 and the message must be m1.
So the probability of m1 appearing is the sum of the probability of s1,
s6, s10 and s14 appearing prior to compression:
P(m1) = P(s1) + P(s6) + P(s10) + P(s14) = 1/2
And it can be similarly shown
P(m2) = P(s3) + P(s7) + P(s11) + P(s15) = 1/4
P(m3) = P(s4) + P(s8) + P(s12) + P(s16) = 1/8
P(m4) = P(s5) + P(s9) + P(s13) + P(s17) = 1/8.
So as long as the probabilities of the strings satisfy these constraints
then the cipher works :-)
Now back to the threat model.
The threat model assumes Eve knows the entire algorithm - all of those
tables above, including which strings in S are compressed to which
messages in M and then mapped to which cryptogram. Eve also knows the
value si and probabilities P(si) of every string Alice and bob want to
send and the value mj and probabilities P(mj) of every message to
which the strings compress. All Eve doesn't know is the secret key
value.
When Eve intercepts a cryptogram - like 111 for example - for all she
knows:
Alice just sent either s5, s8, s11 or s14 to Bob and the string
compressed down to either m4, m3, m2 or m1.
But Eve DOES know the cryptogram corresponds to one of only those four
strings! Eve can rule out 12 other strings that could have been sent.
The probability of strings s1, s3, s4, s6, s7, s8, s9, s10, s12, s13,
s15, s16, or s17 having been sent drop to zero AFTER Eve intercepts the
cryptogram 111. In fact with any intercepted cryptogram Eve can always
rule out 3/4 of the strings as possible strings sent. This means the
encipherment of the strings does NOT have perfect secrecy ( or Eve
couldn't do what she did - rule out 3/4 of the possible strings as
having not been sent after she saw the cryptogram 111. )
However, with any intercepted cryptogram Eve knows the string compressed
to either m1, m2, m3 or m4. Eve cannot rule out any of the messages mi
as the message the string compressed down to. The probability the
message mi was m1, m2, m3 or m4 given Eve knows the cryptogram remains
the a priori probability of m1, m2, m3 and m4 known to Eve before she
got the cryptogram. The encipherment of the messages DOES still have
perfect secrecy.
In this combined compression-mapping cipher ONLY the messages mi
actually have perfect secrecy. The strings that compress down to the
messages mi do NOT have perfect secrecy.
[big snip here]
> But look what happens when one decrypts any message of 2 bits.
> since its not used in the message space. I maintain that this
> decryption system maps each 2 bit value for c2 space back to four
> values sa s1 s2 s3 and s4. The mapping are such they match you
> example for the perfect security method you just explained.
>
> I perform a compression ( bijective mapping ) so the 4 messages
> I was using map to s1 s2 s3 s4. These statements all mapp to c2
> two bit valuse. The same as you example. So know by using bijective
> compression I have turned a not secure system to one of perfect
> security by the use of bijective compression.
> Take a look at what I wrote in this message and you will see you
> quoted it wrong.
>
I did not understand the above two paragraphs even when I saw the new
mappings. Hopefully the example in this post is close to your intended
model. If not we can probably work from the model in this post to get it
there :-)
John A. Malley
[EMAIL PROTECTED]
------------------------------
From: [EMAIL PROTECTED] (anish)
Subject: Re: crypt education
Date: 3 Jun 2001 00:39:49 -0700
Mok-Kong Shen <[EMAIL PROTECTED]> wrote in message
news:<[EMAIL PROTECTED]>...
> "Douglas A. Gwyn" wrote:
> >
> > We know where bin Laden is, but we have laws prohibiting assassination,
> > and his host nation refuses to extradite him.
>
> Maybe one doesn't have the very exact location. Otherwise
> missiles of the type used in the war in Yogoslavia
> could have been employed, I guess.
>
> M. K. Shen
Hi all,
I dont think getting into academics and doing a regular MS program
is no that easy . I have been
trying to do the same for for quite sometime ..U have n reasons given
by prof s around from nationality
to the back ground ....I have been working in security realted areas
for past three
plus years some of which I spent doing intership to professors who
work on these
areas and rest working for Fortune 500 firms (telcom)
anish.....
------------------------------
From: [EMAIL PROTECTED] (SCOTT19U.ZIP_GUY)
Subject: Re: Uniciyt distance and compression for AES
Date: 3 Jun 2001 08:08:02 GMT
[EMAIL PROTECTED] (John A. Malley) wrote in
<[EMAIL PROTECTED]>:
>
>I *think* I see what are saying, here's another paraphrase:
>
>There are 16 strings s1, s3, s4, s5...s17 in the string set S where the
>length (in bits) of each string is i, 1 <= i <= 17 and i != 2.
>So there is no 2 bit string in S.
Well I am not sure I defined an S but there are 16 strings that
would appear as cipher text for the for messages when each one
is encrypted with one one of the four keys.
>
>Each string in S is compressed to the set M = {m1, m2, m3, m4} AND
>encrypted using just four 2-bit keys, k1 = 00, k2 = 01, k3 = 10, k4 =
>11. Compression reduces the string si to a message mj that is
>enciphered to cryptogram ck.
When compressed I am compressing m(n) to 2 bit strings and when
the encryption occurs the the results are 2 bit strings.
>
>
EDITING BELOW
k1 = 00 selects compression and this mapping:
THE COMMON COMPRESSION
m1 compress to 00
m2 compress to 01
m3 compress to 10
m4 compress to 11
00 <-> c1 = 00
01 <-> c2 = 01
10 <-> c3 = 10
11 <-> c4 = 11
k2 = 01 selects compression and this mapping:
00 <-> c1 = 11
01 <-> c2 = 00
10 <-> c3 = 01
11 <-> c4 = 10
k3 = 10 selects compression and this mapping:
00 <-> c1 = 10
01 <-> c2 = 11
10 <-> c3 = 00
11 <-> c4 = 01
k4 = 11 selects compression and this mapping:
00 <-> c1 = 01
01 <-> c2 = 10
10 <-> c3 = 11
11 <-> c4 = 00
>The threat model assumes Eve knows the entire algorithm - all of those
>tables above, including which strings in S are compressed to which
>messages in M and then mapped to which cryptogram. Eve also knows the
>value si and probabilities P(si) of every string Alice and bob want to
>send and the value mj and probabilities P(mj) of every message to
>which the strings compress. All Eve doesn't know is the secret key
>value.
>
>When Eve intercepts a cryptogram - like 111 for example - for all she
>knows:
If she get 111 somethings wrong since BOB and ALICE and using the
encryption scheme with compression and only 4 message and they are
each ecrypted to 2 bits with any of the keys,
>However, with any intercepted cryptogram Eve knows the string compressed
>to either m1, m2, m3 or m4. Eve cannot rule out any of the messages mi
>as the message the string compressed down to. The probability the
>message mi was m1, m2, m3 or m4 given Eve knows the cryptogram remains
>the a priori probability of m1, m2, m3 and m4 known to Eve before she
>got the cryptogram. The encipherment of the messages DOES still have
>perfect secrecy.
>
>In this combined compression-mapping cipher ONLY the messages mi
>actually have perfect secrecy. The strings that compress down to the
>messages mi do NOT have perfect secrecy.
All that is sent is the 4 messages so the system does have perfect
secrecy. There are no other messages.
>
>
>[big snip here]
>
>> But look what happens when one decrypts any message of 2 bits.
>> since its not used in the message space. I maintain that this
>> decryption system maps each 2 bit value for c2 space back to four
>> values sa s1 s2 s3 and s4. The mapping are such they match you
>> example for the perfect security method you just explained.
>>
>> I perform a compression ( bijective mapping ) so the 4 messages
>> I was using map to s1 s2 s3 s4. These statements all mapp to c2
>> two bit valuse. The same as you example. So know by using bijective
>> compression I have turned a not secure system to one of perfect
>> security by the use of bijective compression.
>> Take a look at what I wrote in this message and you will see you
>> quoted it wrong.
>>
>
>I did not understand the above two paragraphs even when I saw the new
>mappings. Hopefully the example in this post is close to your intended
>model. If not we can probably work from the model in this post to get it
>there :-)
>
Hopefully
David A. Scott
--
SCOTT19U.ZIP NOW AVAILABLE WORLD WIDE "OLD VERSIOM"
http://www.jim.com/jamesd/Kong/scott19u.zip
My website http://members.nbci.com/ecil/index.htm
My crypto code http://radiusnet.net/crypto/archive/scott/
MY Compression Page http://members.nbci.com/ecil/compress.htm
**NOTE FOR EMAIL drop the roman "five" ***
Disclaimer:I am in no way responsible for any of the statements
made in the above text. For all I know I might be drugged or
something..
No I'm not paranoid. You all think I'm paranoid, don't you!
------------------------------
From: [EMAIL PROTECTED] (David Wagner)
Subject: Re: National Security Nightmare?
Date: Sun, 3 Jun 2001 09:23:08 +0000 (UTC)
Thank you for being willing to discuss this.
However, I must report that I have carefully read the documents you
referred to, and as far as I can see, they do not say what you thought
(with the possible exception of one case that is unclear at best).
See my detailed analysis below.
In particular, I couldn't find any prohibition against the "GCHQ
backdoor", i.e., a gentleman's agreement between the NSA and GCHQ to
spy on each other's citizens and swap intercepts. If it is the
policy of the NSA that such conduct is forbidden, how can I tell?
I would warmly welcome any specific pointers.
I guess my challenge still stands. If it is the policy of the US to
protect US communications, no matter who or how they were collected,
where is this clearly stated? Where are the excerpts from the NSA's
training manuals that describe these procedures? It does not sound
like an entirely unreasonable request.
At present, the guiding policy and procedures are apparently classified
(see below). If US policy prohibits the "GCHQ backdoor", what national
security reason could one have for keeping the relevant excerpts of the
policy secret? I'd be grateful for any help in understanding this
puzzling state of affairs.
I hope you can see why this does not provide much reassurance. Quite
likely there is nothing all that nefarious going on in much of the NSA
today, but it does not seem unreasonable to ask for something better
than the above.
Here's the detailed analysis. I'll go through each of the documents
you referred to. If I overlooked anything, I'd be grateful for a
correction.
- 50 USC 1801-1829. This creates a new way under which US agencies
can be authorized to spy on people. However, nothing says it is the
only way. As far as I can see, it only adds to the things the NSA
is allowed to do---it doesn't restrict them. (By the way, FISA is
hardly a shining example of civil rights protection, IMHO. If FISA
is intended to be representative of the way the national intelligence
community treats US citizens, I think outsiders might be right
to be somewhat concerned.)
- Executive Order 12139. I can't see the relevance.
- Executive Order 11905. Once upon a time, this did give explicit
protection against the "GCHQ backdoor": see Sections 5(a)(1) and
5(b)(7). I agree that this would be an excellent model for policy
on this issue. However, 11905 has been superseded (see below),
and sadly, those prohibitions are apparently now gone.
- Executive Order 12333. No prohibitions against the "GCHQ backdoor".
The relevant protections in 11905 disappeared. Has a reference to
nebulous procedures established by the head of the agency, but these
procedures are _classified_ and apparently are subject to change at
any time.
Also, 12333 seems to explicitly permit collecting intercepts on US
people: see Sections 2.3(c) and 2.3(h), which permit agencies to
intercept US communications if they are gathered as part of a larger
operation whose purpose is not solely for intercepting US communications.
But this is exactly the sort of scenario we should be worried about.
As a minor note, there are no obvious prohibitions in 12333 against
passing our intercepts of British citizens to the GCQH.
http://www.reagan.utexas.edu/resource/speeches/1981/120481d.htm
- Hayden's testimony (12 Apr 2000). Says US agencies are forbidden
by 12333 to ask GCHQ to spy on US citizens: I'm prepared to accept
this for the purposes of argument. What Hayden does _not_ say is
that it's only forbidden to ask; if GCHQ does it without asking (or
if there is an unspoken gentleman's agreement), it is not at all
clear that this would be a violation of 12333 Sec 2.12.
Hayden also says 12333 requires "no information [...] about a U.S.
person may be retained unless the information is necessary to
understand a particular piece of foreign intelligence or assess
its importance." That would be a truly laudable policy... except
that I cannot see where in 12333 he is finding this requirement.
(This is the exception I mentioned above.) Am I missing something?
------------------------------
From: [EMAIL PROTECTED] (Roger Fleming)
Subject: Re: Question about credit card number
Date: Sun, 03 Jun 2001 08:23:56 GMT
(Please be careful with your attributions. A careless reader could get the
impression that I wrote the quoted text.)
Chenghuai Lu <[EMAIL PROTECTED]> wrote:
>John Hairell wrote:
>>
>> On Fri, 01 Jun 2001 13:56:16 GMT, [EMAIL PROTECTED] (Roger Fleming)
>> wrote:
>>
>> Actually, a whole bunch of commercial websites have been hacked,
>> including some large ones, based on the fact that the front ends used
>> encryption but the back ends were somewhow left open, and the CC
>> numbers were not stored in an encrypted form. Many of the hacks were
>> based on systems people not keeping their systems patches up to date,
>> and ignoring information about well-known attacks.
>
>Even if the CC numbers are stored in an encrypted form in the back ends,
>they are easy to break since all of CC numbers are encrypted using the
>same master key. Isn't it right?
Sure, more or less. The fact is the data has to be delivered to the front end
in a form it can use. That either means the (more vulnerable) front end knows
the key (where it can be stolen), or - more usually - the data is decrypted
before delivery to the front end. That means that if the front end can ask
for credit card numbers and I can hack it to the extent of executing arbitrary
SQL queries, I can just ask the database for all the credit card numbers, and
it doesn't matter in what form they are stored. On the other hand, if the
designers have wisely not allowed the webserver to ask for credit card
numbers, then I can't get them unless I hack the (much more deeply protected)
database server too. In that case, it once again doesn't matter if they are
encrypted or not.
The only time I can think encrypting them will be useful is one of these small
sites where many virtual sites, all running as the same "nobody" user, share
the same machine. In that case public key encryption may offer some protection
against your fellow web merchants.
------------------------------
From: [EMAIL PROTECTED] (David Wagner)
Subject: Re: Luby-Rackoff Theorems?
Date: Sun, 3 Jun 2001 09:31:27 +0000 (UTC)
I think you might have gotten caught by two subtle pitfalls.
If I'm not mistaken, they will account for the difference between
our two results, and correcting for them will give what I claimed.
But tell me whether you agree or not---this is tricky stuff,
and who knows, maybe I went wrong somewhere.
1. The Luby-Rackoff paper uses 2n for the block size, and proves
security so long as m^2/2^n is small, where m is the number of
texts. Thus, this provides security up to m ~ 2^{n/2}. If we
let n' = 2n be the block size (n' is "my n" in my earlier post),
then this provides security for up to 2^{n'/4} texts. With a
128-bit block cipher, this is security up to 2^32 texts.
2. The Luby-Rackoff paper is actually not quite enough if you want
to use their construction recursively. You need to look to modern
generalizations. In particular, LR prove
If the Feistel function is truly random, then
the 4-round cipher is pseudorandom.
Note that they require a truly random (unconditionally secure)
Feistel function, so if you try to instantiate the Feistel function
using a recursive LR construction, the original LR theorem doesn't
apply. Since then, others have made the slight generalization to
the case where the Feistel function is assumed only to be pseudorandom
(e.g., Maurer, Lucks, Naor/Reingold, etc.). Let q-pseudorandom
refer to a keyed function that is indistinguishable from its idealized
version if the adversary has access to at most q texts. Then the
modern form of the Luby-Rackoff theorem is
If the Feistel function is q'-pseudorandom, then
the 4-round cipher is q-pseudorandom.
In particular, q is related to q' by q ~ min(q',2^{n/2}) where
n is as above, i.e., q ~ min(q',2^{n'/4}). This is why the q'
appears in my statement of the theorem but does not appear in
the original Luby-Rackoff paper.
------------------------------
From: [EMAIL PROTECTED] (Roger Fleming)
Subject: Re: Question about credit card number
Date: Sun, 03 Jun 2001 08:54:13 GMT
[EMAIL PROTECTED] (John Hairell) wrote:
[...]
>Actually, a whole bunch of commercial websites have been hacked,
>including some large ones, based on the fact that the front ends used
>encryption but the back ends were somewhow left open, and the CC
>numbers were not stored in an encrypted form. Many of the hacks were
>based on systems people not keeping their systems patches up to date,
>and ignoring information about well-known attacks.
Yes, well there's no accounting for stupidity. The security benefits of
multi-tier architecture derive from isolating the separate tiers. That
requires that the back end machines be totally inaccessible to public
networks, listening on only one port from the webserver's (internal, martian)
IP. Literally unreachable unless the webserver has first been completely
compromised. Add some good filtering on the one channel between them, and it
becomes very tricky to squeeze an attack down such a narrow pipe even if the
database is not well maintained.
>My credit card number and that of thousands of other customers was
>ripped off late last year from a commercial server which had been left
>open to attack, and the people who ran it continued doing their usual
>silly stuff despite having been warned beforehand at least twice. The
>hackers had multiple months of direct access before anything was done.
>Too little, too late.
Yep, during the dot com wave I had the experience of working alongside quite a
few dot coms, and was appalled by how many were totally incompetent. Not just
programmers who could only program by copying (unvetted) code from websites,
and sysadmins who'd never heard of CERT, but also marketing people who didn't
understand demographics and managers who didn't know how to budget. And not
just folks working from their garages; the largest partner that gave me a
strong impression of cluelessness had over 100 employees. No wonder it all
fell in a heap.
>My bank got their web security certification, with their web-page
>allowing access to accounts based on a four-digit PIN number and an
>unlimited number of retries if you make a mistake, and with the PIN
>number (letters and numbers) being assigned by them. They said that
>too many digits (like 8) is too hard for their customers to remember.
To be fair, most people indeed cannot remember 8 digit PINs. But they could
use passphrases instead, or issue X.509 certs, or at least put in a long delay
(and report to security) every 3 errors. All of these, however, require a
little work to transfer onto the web from a PIN based system on stateful
machines, and work means eroding the bottom line.
>I don't trust any commercial website, no matter what security policy
>they have posted or what certification they have. Their back end
>could be wide open, with their sysadmins sitting there fat, dumb, and
>happy.
Agree 100%. Hopefully the consumer's victim-oriented position will gradually
be improved by various programs that require sites to be independantly and
expertly audited before making various security claims, but at present it's a
mess.
------------------------------
** 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 by posting to sci.crypt.
End of Cryptography-Digest Digest
******************************
