Cryptography-Digest Digest #511, Volume #14 Mon, 4 Jun 01 05:13:01 EDT
Contents:
Re: Uniciyt distance and compression for AES ("John A. Malley")
Re: National Security Nightmare? (David Wagner)
Re: National Security Nightmare? (SCOTT19U.ZIP_GUY)
Re: BigNum Question ("JGuru")
Re: National Security Nightmare? (SCOTT19U.ZIP_GUY)
Knapsack security??? Ah....huh (Merc42)
Re: National Security Nightmare? ("John A. Malley")
Re: Knapsack security??? Ah....huh ("Jeffrey Walton")
Re: Welcoming another Anti-Evidence Eliminator stooge to USENET (P. Dulles / AKA
Loki) (John Savard)
Re: Knapsack security??? Ah....huh ("Scott Fluhrer")
Re: PRP vs PRF (was Luby-Rackoff Theorems) (Fabian Buechler)
Re: RSA's new Factoring Challenges: $200,000 prize. ("Michael Brown")
----------------------------------------------------------------------------
From: "John A. Malley" <[EMAIL PROTECTED]>
Subject: Re: Uniciyt distance and compression for AES
Date: Sun, 03 Jun 2001 20:48:16 -0700
"SCOTT19U.ZIP_GUY" wrote:
[...stuff edited...]
> When compressed I am compressing m(n) to 2 bit strings and when
> the encryption occurs the the results are 2 bit strings.
>
So there are four messages m1, m2, m3 and m4 that compress down to
> THE COMMON COMPRESSION
> m1 compress to 00
> m2 compress to 01
> m3 compress to 10
> m4 compress to 11
OK. Let M = {m1, m2, m3, m4} where the messages m_i are longer than 2
bits in length. For the cipher to have perfect secrecy the uncertainty
of the messages must be H(M) <= 2 bits, or in other words, the
probabilities of m1, m2, m3 and m4 are such that
- [ P(m1)*log(P(m1)) + P(m2)*log(P(m2)) + P(m3)*log(P(m3)) +
P(m4)*log(P(m4)) ] <= 2.
If the messages in M meet that constraint, encryption with the following
mappings as specified by one of the 4 possible key values gives perfect
secrecy as defined in Shannon's paper.
>
> k1 = 00 selects compression and this mapping:
>
>
> 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
>
As stated in a prior post in this thread, though, compression is not
needed when the cipher provides perfect secrecy.
Alice and Bob can use the following mappings directly and achieve
perfect secrecy:
k1 = 00 selects this mapping:
m1 <-> c1 = 00
m2 <-> c2 = 01
m3 <-> c3 = 10
m4 <-> c4 = 11
k2 = 01 selects this mapping:
m1 <-> c1 = 11
m2 <-> c2 = 00
m3 <-> c3 = 01
m4 <-> c4 = 10
k3 = 10 selects this mapping:
m1 <-> c1 = 10
m2 <-> c2 = 11
m3 <-> c3 = 00
m4 <-> c4 = 01
k4 = 11 selects this mapping:
m1 <-> c1 = 01
m2 <-> c2 = 10
m3 <-> c3 = 11
m4 <-> c4 = 00
A cipher with perfect secrecy doesn't need to compress the message prior
to encryption. Alice, Bob and Eve can all know which strings m1, m2, m3
and m4 correspond to which cryptograms under which key/mapping. The
security of the cipher is totally dependent on the secrecy of the key
used by Alice and Bob. Shannon's description of a cipher with perfect
secrecy offers no compelling reason to use bijective compression or any
other form of compression as was argued far back in this thread.
A cipher _without_ perfect secrecy (like block cipher algorithms - the
DES and AES as examples) _can_ benefit from the compression of the
plaintext prior to encryption to increase the unicity distance for
ciphertext traffic under the same key. I heartily agree with you on
that! AFAIK it can't hurt to compress prior to encryption - except for
known stereotyped header information embedded in the compressed
plaintext prior to encryption as has been pointed out in this newsgroup
in past posts - and I totally agree with that position :-)
However, block chaining modes can and do address the issue of
stereotyped header information embedded in the compressed plaintext.
I am of the personal opinion that compression, even with PKZIP, prior to
encryption with 3DES in outer-CBC mode is a "comfortable" way to go :-)
John A. Malley
[EMAIL PROTECTED]
------------------------------
From: [EMAIL PROTECTED] (David Wagner)
Subject: Re: National Security Nightmare?
Date: Mon, 4 Jun 2001 03:53:18 +0000 (UTC)
Douglas A. Gwyn wrote:
>If you really want to pursue this, linguistic analysis of EOs
>isn't as good as contacting the relevant agencies (under FOIA)
>to obtain copies of the personnel indoctrination material in
>this area.
Ahh, yes, FOIA: the law that the secret agencies just can't seem
to obey. This is the same law that requires the agencies to cough
up records in 30 days or less, but where almost all requests take a
year or more (unless you have enough money to take them to court).
If the agencies can't even obey the law regarding FOIA requests,
should this inspire confidence in their ability to obey other
legal restrictions on their actions?
>After all, the official rules don't matter if they
>differ from the policy that the actual workers are required to
>follow.
I certainly agree, and I would find appropriate excerpts from
the personnel indoctrination material a persuasive answer to the
persistent allegations about the "GCHQ backdoor". However, the
enormous delays in getting any FOIA request answered make it very
hard to take advantage of FOIA in any meaningful way.
Frankly, at the end of the day, after I've gone through as much
effort as I have, I have to say that I place the burden of the
proof on the intelligence agencies. The intelligence agencies
are the ones who have the ability, the access, and the incentive
to provide these documents. Private citizens do not. If the
agencies are unwilling or unable to provide such material, then
in my view it is not unreasonable to draw adverse inferences from
this failure, in absence of any other information.
------------------------------
From: [EMAIL PROTECTED] (SCOTT19U.ZIP_GUY)
Subject: Re: National Security Nightmare?
Date: 4 Jun 2001 03:53:22 GMT
[EMAIL PROTECTED] (David Wagner) wrote in
<9ff02t$vf4$[EMAIL PROTECTED]>:
>Douglas A. Gwyn wrote:
>>As I said, it pretty much takes legal staff to issue accurate
>>interpretations.
>
>Maybe it does with today's laws, but it shouldn't. The intelligences
>community asks citizens to "trust them"; but when the guiding regulations
>are so unnecessarily vague that citizens can't verify for themselves
>how these agencies really operate, should anyone in the intelligence
>community be surprised when citizens don't trust them? We need clear
>and visible protection against violations of civil liberties, not vague,
>inaccessible, classified legalese.
>
>There is no reason that the latest executive orders couldn't include
>the clear language found in EO 11905. Moreover, it seems that the NSA
>could easily publish excerpts from its training manuals to substantiate
>claims that employees are instructed to treat civil liberties seriously.
Do you mean the real manual. What if the reason there not releasing it
is because they have no respect for the ordinary citizen. Isn't far
better to say nothing then release a phony manual that some angry
honest employess could expose as false at a later date.
>
>If electronic surveillance is so critical to national security, why can't
>the intelligence agencies spare 0.1% of their budget to openness and and
>transparency? One is led to the impression that this is not a priority
>for the intelligence community. It seems that the intelligence community
>has not taken any of these easy, no-cost, confidence-inspiring steps.
>Should anyone be surprised if people view this as an indication that
>maybe the intelligence community doesn't care about civil liberties as
>much as it should?
I guess they can't be open an honest is very similar to
your reasons for not being honest in commenting about BICOM. You feel
hatred for those you consider lower than yourself. So you will
not give it an honest look. Same with them they feel citizens
on the whole aren't worthy enough to even care about. After all
when they look at the crypto community they are laughing. Just
like you laugh at things like BICOM but either you haven't looked
or if you have can you behonest about it. Isn't the connection
reather obvious,
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: "JGuru" <[EMAIL PROTECTED]>
Subject: Re: BigNum Question
Date: Mon, 04 Jun 2001 03:57:45 GMT
Java has BigInteger and BigDecimal. As long as there is a JDK available for
your platform, you can write code that can run on any platform.
"George" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> I'm trying to develop a program for Macintosh and I need to operate on
> very large numbers. What is the best BigNum library for Macintosh where
> the source code is also available?
>
> -George
> [EMAIL PROTECTED]
>
------------------------------
From: [EMAIL PROTECTED] (SCOTT19U.ZIP_GUY)
Subject: Re: National Security Nightmare?
Date: 4 Jun 2001 04:07:48 GMT
[EMAIL PROTECTED] (David Wagner) wrote in
<9ff0ne$vp5$[EMAIL PROTECTED]>:
>Douglas A. Gwyn wrote:
>>If you really want to pursue this, linguistic analysis of EOs
>>isn't as good as contacting the relevant agencies (under FOIA)
>>to obtain copies of the personnel indoctrination material in
>>this area.
>
>Ahh, yes, FOIA: the law that the secret agencies just can't seem
>to obey. This is the same law that requires the agencies to cough
>up records in 30 days or less, but where almost all requests take a
>year or more (unless you have enough money to take them to court).
>If the agencies can't even obey the law regarding FOIA requests,
>should this inspire confidence in their ability to obey other
>legal restrictions on their actions?
>
>>After all, the official rules don't matter if they
>>differ from the policy that the actual workers are required to
>>follow.
>
You really can't expect a govenment agency to follow the law
especailly after having Clinton show thats a waste of time.
I have yet to get an anwser from the BXA or whatever the group
is so I can put my crypto on a web page. Off and on I have
written several times but they NEVER write back.
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] (Merc42)
Subject: Knapsack security??? Ah....huh
Date: 3 Jun 2001 21:32:07 -0700
I was wondering if there are any knapsack systems that are still
secure. Any that don't use modular arithmatic to change the keys are
of special interest to me. Furthermore, if anybody does know of any,
could you please tell me some reference where i could learn more about
them. As always, any help is appreciated...
thanx
------------------------------
From: "John A. Malley" <[EMAIL PROTECTED]>
Subject: Re: National Security Nightmare?
Date: Sun, 03 Jun 2001 21:33:20 -0700
David Wagner wrote:
>
> Frankly, at the end of the day, after I've gone through as much
> effort as I have, I have to say that I place the burden of the
> proof on the intelligence agencies. The intelligence agencies
> are the ones who have the ability, the access, and the incentive
> to provide these documents. Private citizens do not. If the
> agencies are unwilling or unable to provide such material, then
> in my view it is not unreasonable to draw adverse inferences from
> this failure, in absence of any other information.
Let's not give up on FOIA - or on the power of the citizen to demand
accountability from his government, especially in the United States of
America. Discouraging? Yes. Frustrating? Yes. Impossible? No. The
intelligence agencies are part of the government that answers to the
citizen.
If the current tactics aren't working then we must look to change
tactics, adapt and continue. FOIA is an avenue to information. If the
requests appear to go nowhere or drag on indefinitely (delay and time
pressure are GREAT negotiation tactics) then why not look to lobbying
one's congressional representatives to aid the request? Or lobby
members of Congress on the intelligence committees? Why not organize a
group of friends and/or colleagues to aid with the FOIA requests and
with strategic lobbying to spread the work out? To make agency stalling
visible to the public and to Congress and politically uncomfortable for
the stallers. Pressure and counterpressure.
It's easier today to organize a group interested in the truth. The
Internet makes it easier than ever before.
There's another side to this. As citizens we can argue for or against
that point of secrecy we call "national security." We can, should and
must help shape its definition with our elected government. There is
nothing (AFAIK) in our Constitution that stipulates citizens have no
role in collectively defining the breadth and scope of secrets for
national security. Sometimes I think the executive branch and government
agencies quietly took it upon themselves to act on our behalf to
establish these limits - and having done so for so long have forgotten
citizens play any part in its definition. And so did the citizens.
Play politics to help get the information from the politicians and the
bureaucrats. :-)
(Or maybe I'm just an optimist? :-) )
John A. Malley
[EMAIL PROTECTED]
------------------------------
Reply-To: "Jeffrey Walton" <[EMAIL PROTECTED]>
From: "Jeffrey Walton" <[EMAIL PROTECTED]>
Subject: Re: Knapsack security??? Ah....huh
Date: Mon, 4 Jun 2001 00:41:02 -0400
Take a look at Chor-Rivest.
Per Menezes, the public key is very large (on the order of 3600 bits for
recommended p and h).
"Merc42" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
: I was wondering if there are any knapsack systems that are still
: secure. Any that don't use modular arithmatic to change the keys are
: of special interest to me. Furthermore, if anybody does know of any,
: could you please tell me some reference where i could learn more about
: them. As always, any help is appreciated...
:
: thanx
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Crossposted-To:
alt.privacy,alt.security,alt.security.pgp,alt.security.scramdisk,alt.privacy.anon-server
Subject: Re: Welcoming another Anti-Evidence Eliminator stooge to USENET (P. Dulles
/ AKA Loki)
Date: Mon, 04 Jun 2001 05:05:59 GMT
On Mon, 04 Jun 2001 01:51:57 GMT, "Trevor L. Jackson, III"
<[EMAIL PROTECTED]> wrote, in part:
>It implies that it is
>possible to prove a falsehood. One typically proves truths.
A "proven lie" is a statement that has been proven to be a lie.
That means one has proven:
the statement is false, and
the person making the statement knew it to be false.
It does _not_ mean the statement (despite being a lie) has been proven
to be true. Although it is true that one could apply the rules of
English grammar to the phrase "proven lie" and find it to be
equivalent to "lie that has been proved", English is actually more
complicated than that.
Thus, it is possible for statements to be proven lies, even if one has
rather strong suspicions about any claims of that nature appearing in
the particular post under discussion.
John Savard
http://home.ecn.ab.ca/~jsavard/frhome.htm
------------------------------
From: "Scott Fluhrer" <[EMAIL PROTECTED]>
Subject: Re: Knapsack security??? Ah....huh
Date: Sun, 3 Jun 2001 23:15:25 -0700
Jeffrey Walton <[EMAIL PROTECTED]> wrote in message
news:3b1b1085$0$[EMAIL PROTECTED]...
> Take a look at Chor-Rivest.
At Crypto 2000, Vaudenay showed how to break it at the suggested security
parameters. You might be able to get around the attack by increasing the
security parameters enough (I haven't gone through the attack in enough
detail to know how feasible that would be), but the existence of such an
attack makes me question that crypto system..
>
> Per Menezes, the public key is very large (on the order of 3600 bits for
> recommended p and h).
>
> "Merc42" <[EMAIL PROTECTED]> wrote in message
> news:[EMAIL PROTECTED]...
> : I was wondering if there are any knapsack systems that are still
> : secure. Any that don't use modular arithmatic to change the keys are
> : of special interest to me. Furthermore, if anybody does know of any,
> : could you please tell me some reference where i could learn more about
> : them. As always, any help is appreciated...
> :
> : thanx
>
>
------------------------------
From: Fabian Buechler <[EMAIL PROTECTED]>
Subject: Re: PRP vs PRF (was Luby-Rackoff Theorems)
Date: Mon, 04 Jun 2001 10:23:59 +0200
No
------------------------------
From: "Michael Brown" <[EMAIL PROTECTED]>
Crossposted-To: sci.math
Subject: Re: RSA's new Factoring Challenges: $200,000 prize.
Date: Mon, 4 Jun 2001 21:13:08 +1200
Sorry about the long delay. A whole lot of things cropped up. I usually respond
quicker to e-mails also :)
"Douglas A. Gwyn" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> Rob Warnock wrote:
> > Michael Brown <[EMAIL PROTECTED]> wrote:
> > | "Douglas A. Gwyn" <[EMAIL PROTECTED]> wrote:
> > | > The main unresolved question seems to be, how many operations
> > | > can we expect for finding a typical N-bit prime factor?
> > | If you are referring to my algorithm (hopefully :P), then there
> > | are x^3 - x^2 - x boxes to complete, where x is the number of digits
> > | in the maximum prime.
> > So I'd be more concerned about Doug's question about "number of operations"
> > than about the memory...
>
> I concur. What I wonder, not having studied this algorithm yet,
> is the rate of growth of work-per-box as the problem size is
> increased.
Sorry. I ahould have put in a bit more information with my first post.
With a decent implementation of the algorithm (see below), the number of
operations per box should remain much the same (actual number of instructions
depends on instruction set).
> If, for example, it is subexponential, then this
> could be a practical method of factoring very large products-
> of-primes; perhaps NASA or some other possessor of a system
> like the ones Rob mentioned would be happy to run the
> remaining RSA factoring challenges against Michael's algorithm,
> especially in exchange for a cut of the prize..
I should imagine that a supercomputer of that size with 16GB of ram wouldn't
leave much change out of $200K (the amount that would be obtained if all
possible factorisable numbers were done) ... However, if you already have one
sitting under (or probably beside) your desk, then it would be a different
story.
> I for one would be happy to see factoring become clearly too
> risky as a base for cryptosecurity. It would make for some
> excitement in this field, which has been rather dull lately.
Ditto, but all that would happen would be a switch to DH/DSS (the PGP name) I
would think.
Anyhow, here's my ideas on implementation of the algorithm on a computer with
more RAM than it knows what to do with (ps: I'm presuming that computer has
registers or equivilent big enough to access its address space):
1) Set up the array of boxes (called Boxes from now on). Each box has the
following properties:
Value : (byte) 4 sets of 2 bits (0 = zero, 1 = one, 2 = unknown, 3 = invalid),
each representing A, B, O, and C
ABox, BBox, OBox, CBox : indixes into the array (this one) of boxes, where ABox
is the box attached to A etc. Each of
these could be a dword.
BoxPart : (byte) 4 sets of 2 bits (0 = A, 1 = B, 2 = O, 3 = C) where the Part of
The time taken for each box would be the same regardless of how many boxes there
were.
2) A lookup table (called Lookup from now on) would have to be already set up.
This would have translations from things such as (in the form A-B-O-C) 0-?-?-?
to 0-?-?-0 so would be the "box filling" part of the process.
3) The values for the O of the bottom row of boxes would be set, and these boxes
pushed onto a stack that contains boxes that need to be updated.
4)
<PSEUDOCODE>
CurBox := GetNextBox;
OldVal := Boxes[CurBox];
Boxes[CurBox] := LookUp[Boxes[CurBox]];
</PSEUDOCODE>
If the any of the lower two bits of (OldVal xor Boxes[CurBox]) are set then set
the corresponding bit (from ABOx and lower 2 bits of BoxPart) to the correct
value (sorry this is rather vauge, but the pseudocode is downright horrible).
Push the destination box onto the box stack.
Ditto for B, O, and C.
<<< Note: There may be a little bit of confused text around here as I had to
stop for about 24 hours ... sleep, school, homework etc>>>
5) Do the bit at the top of the horozontal boxes (HBoxes hehehehe ... oh dear, I
really need to get out of the sci.crypt newsgroup =P ), where you check to see
if an and bm are one and C is zero (hence am != bm). If so then substitute into
the boxes further on. Again, this could be computed in a lookup table before
hand (since we're not too worried about RAM anymore).
6) Repeat 4 & 5 until you can't go any further. Take the information from the
(er, just one more time?) HBoxes and put it into the product table to determine
A and B.
Steps 4 and 5 are entirely constant per box (maximum of doing a box 4 times) and
with the lookup table, step 5 should be linear as well). Step 2 is also constant
also, with the lookup table not changing. Step 3 is of course linear. Step 6 is
quadratic and step 1 is cubic (or constant per box).
All put together, the overall pattern will be a fairly constant number of
operations per box, and since the number of boxes is cubic, the factoring time
should be cubic.
I'm not sure if this is coherent enough to answer your question, but I hope it
is.
Regards,
Michael
------------------------------
** 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
******************************
