Cryptography-Digest Digest #586, Volume #11 Thu, 20 Apr 00 08:13:01 EDT
Contents:
Re: Q: NTRU's encryption algorithm (David A Molnar)
Improved Page Tag Encryption Demonstration (uses new keys for each user session.)
("C. Prichard")
Re: BlowWire (Sandy Harris)
Brute force (was Re: Why is this algorithm insecure?) (Sandy Harris)
Re: Cipher Contest Update ("Patrik J�rnefelt")
Re: password generator (jan grant)
Re: password generator (Tom St Denis)
Re: OAP-L3: Semester 1 / Class #1 All are invited. (Tom St Denis)
Re: OAP-L3: Semester 1 / Class #1 All are invited. (Taneli Huuskonen)
This is a test Pls Ignore (Janaka Anguluaha)
Re: OAP-L3: Semester 1 / Class #1 All are invited. (Tom St Denis)
What is going on with 'sci.crypt.research' ? (Francois Grieu)
Re: This is a test Pls Ignore (Tom St Denis)
Des S-Boxes (schack01)
Re: Des S-Boxes (Tom St Denis)
----------------------------------------------------------------------------
From: David A Molnar <[EMAIL PROTECTED]>
Subject: Re: Q: NTRU's encryption algorithm
Date: 20 Apr 2000 06:00:39 GMT
Diet NSA <[EMAIL PROTECTED]> wrote:
> computer would help. If someone wanted
> to make a cryptosystem that is
> theoretically secure against quantum
> computing then they might begin by trying
> to invent one-way functions that no
> quantum computer can invert better than
> random guessing.
Does this last sentence have to mean "no better than using Grover's
algorithm"? It seems that as soon as you have a means of "checking" your
guess, you can use the algorithm to search for a preimage of a given
value in O(sqrt(n)) time. With a one-way function, it seems you can
check your guess g by evaluating f(g) and comparing against the target
value.
> P.S. Is BQP equivalent to the problems
> having statistical zero-knowledge proof
> systems? A: No one knows.
Now *that*'s an interesting question. Salil Vadhan came here a while
months ago and gave a talk on the class of problems which have
statistical zero-knowledge proof systems. I had not known much about
the class before this, but now it seems as though it might be a step
towards characterizing what makes problems like RSA "hard," yet not
"hard enough" to be NP-complete. Therefore exciting. :-)
I hadn't thought about your question here at all.
Let's see. What would we need to even begin approaching the question?
BQP contained in SZK :
What do we know that's even *in* BQP, besides factoring and discrete
log? I seem to recall that a quantum computer can simulate a classical
one step by step, so BPP is in BQP (am I wrong?). What else?
Are there any BQP-complete problems? Can there be?
(I don't know)
Anyway, factoring and discrete log are in SZK, I think. So is BPP. So
far so good. :)
SZK contained in BQP :
We'd have to show that an SZK-complete problem has an efficient quantum
algorithm, thus placing it in BQP. There aren't that many to choose from
right now. Looking at Salil's thesis yields the
Statistical Difference is the promise problem SD = (SD_Y, SD_N)
where
SD_Y = { (X, Y) : StatDiff(X, Y) >= 2/3 }
SD_N = { (X, Y) : StatDiff(X, Y) <= 1/3 }
where X and Y are circuits which encode probability distributions, and
StatDiff is just that -- a function which computes some notion of
"statistical difference."
(all defined in
http://theory.lcs.mit.edu/~salil/papers/phdthesis-abs.html)
In this case we're looking for some kind of quantum algorithm which
could distinguish "close" distributions from "far away ones." The only
technique I know which seems relevant is the "inverting around the
average" used in Grover's algorithm. In some sense the "right
answers" become more probable and the wrong ones less probable. It
doesn't seem all that relevant, though, since the distribution of
"correct answers" keeps being changed on each step in Grover...
Another question that's nagging me a little bit now :
* There seem to be various kinds of provers and verifiers in statistical
zero-knowledge proofs (or even computationally indistinguishable ones).
One of the results mentioned in the talk I saw was about how
"honest-verifier SZK = cheating-verifier SZK." This was accomplished by
means of a construction which
1) first converted the SZK protocol in question to a
"public-coin" or "arthur-merlin" protocol, in which the verifier
simply sends random strings at each stage, independent of the
prover's responses.
2) then uses a "joint random selection" procedure between
prover and verifier to ensure that the strings are really
generated randomly. This is something like coin flipping over
telephone, but much more sophisticated. In particular, it uses
some results about universal hash functions to avoid the need
for anything nasty like bit commitment...
given in
http://theory.lcs.mit.edu/~salil/papers/dishonest-abs.html
Anyway, part 1) of the construction blows up the number of rounds to
something large and exponential. Can we show that HVSZK = SZK without
using this detour through Arthur-Merlin? Can we show that such a detour
is necessary (maybe under some assumptions)?
Do the answers to the previous questions change when the prover and
verifier are polynomially bounded quantum TMs? When one's a quantum TM
and the other isn't? When one's a superpoly bounded quantum TM and the
other's poly and quantum -- etc. etc.
At first glance it doesn't seem like a quantum TM should give you any
more power than a computationally unbounded party - so the only possible
separation would be between a quantum poly and a probabilistic poly time
TM. I haven't thought about it very much yet, though...way too much else
to do... :-\
Thanks,
-David
------------------------------
From: "C. Prichard" <[EMAIL PROTECTED]>
Subject: Improved Page Tag Encryption Demonstration (uses new keys for each user
session.)
Date: Thu, 20 Apr 2000 08:42:54 GMT
The Perl wrapped demonstration at:
http://www.greentv.com/cgi-bin/cgiwrap/greentv/CRI/_nttc.cgi?page=3Dopene=
r&user_id=3D&env=3Dx
Now uses CipherText II to encrypt the tag keys with DIFFERENT keys for =
each user session. This means that all users have different encrypted =
links as part of their persistent data for the application. Try it and =
you will see that the tags are encrypted differently each time you =
refresh the above link to a frameset.
This eliminates the possibility that encrypted links can be exchanged =
via email to unlock protected pages and it prevents users from reusing =
the encrypted keys in successive sessions.
When using framesets it is only possible to refresh links when the =
entire frameset is refreshed. However, IF THERE ARE NO FRAMES, the =
encryption key can be changed with EACH user response.
Using CipherText II there are no problems encrypting page tags and =
transmitting them in the default internet protocol.
With a simple password to protect a page, there is virtually no way to =
navigate to the protected page by entering the encrypted link for a =
given session.
This another example of encryption in the default HTTP protocol where =
CipherText is doing something that other algorithms cannot.
Patent is pending on the CipherText algorithm.
-Charles Prichard
www.greentv.com
------------------------------
From: [EMAIL PROTECTED] (Sandy Harris)
Subject: Re: BlowWire
Date: 20 Apr 2000 08:47:00 GMT
[posted and mailed]
Spleen*no spam*[EMAIL PROTECTED] (Spleen Splitter) spake thus:
>Greetings:
>
>I need something to crank on, so I decided to toy with something I
>fancifully call BlowWire, which is simply a 500MHz or so fully pipelined
>implementation of Blowfish
I'd suggest you go to www.counterpane.com and take a good look at
Twofish. That is an AES (http://csrc.nist.gov/encryption/aes/) candidate
cipher designed by Schneier and a team of others.
One of the design criteria for Twofish (or of its AES rivals) was that it
allow efficient hardware implementations.
If Twofish wins the AES competition, a good hardware implementation would
become a fairly valuable commodity.
>I think I can do this in 60Kgates, ...
The Twofish papers discuss gates/speed tradeoffs. As I recall, they could
get down to 17K gates with some speed sacrifice.
------------------------------
From: [EMAIL PROTECTED] (Sandy Harris)
Subject: Brute force (was Re: Why is this algorithm insecure?)
Date: 20 Apr 2000 09:10:34 GMT
[EMAIL PROTECTED] (Richard Heathfield) spake thus:
>Tom St Denis wrote:
>>
>> Richard Heathfield wrote:
>> > > The task of brute-forcing 2^128 different keys is out of reach for
>> > > any known adversary.
>> >
>> > But wasn't it done recently?
>>
>> I sincerely hope you are joking with this last question.
No. He's confusing key lengths for public key algorithms and symmetric
algorithms, a really common error.
>Sorry, I may have disremembered. I thought I'd read somewhere (trade
>press) that a bunch of machines had worked for about a month on - RSA,
>was it? ...
The record for factoring RSA moduli was 512 bits last I looked and there
was a crack of a 108-bit ECC (elliptic curve crypto) challenge recently,
but those problems are quite different from brute force search against a
symmetric cipher. In particular, they don't get exponentially harder as
key size increases.
Brute force attacks on symmetric ciphers do. Every extra bit of key
doubles the number of possible keys the attacker has to look at. 128 is
utterly out of reach.
e.g. the EFF DES cracker broke 56-bit DES in 57 hours. Assume an attacker
has a machine that breaks a 64-bit cipher (2^8=256 times harder) in one
second (~200,000 times faster). Extend the key to 96 bits. Now the
attacker needs 2^32 seconds on that machine, just over a century. For
128, he needs something over 2^32 centuries.
Of course, if the attacker finds some weakness in the cipher, then he
need not use brute force and the above is irrelevant.
------------------------------
From: "Patrik J�rnefelt" <[EMAIL PROTECTED]>
Subject: Re: Cipher Contest Update
Date: 20 Apr 2000 11:23:58 +0200
"Adam Durana" <[EMAIL PROTECTED]> writes:
> Hello,
>
> The contest started about two weeks ago, and so far I have only received ONE
> submission. Boris Kazak submitted a cipher named LETSIEF (Feistel
> backwards). Matthew Fisher was able to perform differential analysis on it,
> and Mr. Kazak resubmitted his cipher. LETSIEF2 is still in the running and
> I have no heard of any attacks on it yet.
[http://www.wizard.net/~echo/crypto-contest.html]
Hmmm.. from the webpage: "Weaknesses found on variants of entries, such
as reduced round variants, will be posted along with the cipher in the
listing but will not get the cipher removed."
"If a weakness is found in a cipher in either listing it will be
removed, and the author has the option to resubmit it once she or he
corrects the problem."
Those seems to be mutex, is it removed or not? Since LETSIEF is not
listed I assume you do remove 'broken' ciphers. I also assume the
contest's purpose is not to push an AES alternative but rather 1) be
fun, 2) educate & enlighten, 3) a place to gather the various design
ideas which pop up here. So, imho, you should definitly make Fishers
comments (and any future relevant comments on any of the ciphers)
available. We learn by mistakes. Preferably someone elses. ;)
Also, online viewing of the paper of the cipher would be
appreciated. Or at least a short description. Being forced to download
a .zip file is not particulary nice at all. Just my 0.02 euros.
--
------------------------------
From: jan grant <[EMAIL PROTECTED]>
Subject: Re: password generator
Date: Thu, 20 Apr 2000 09:47:44 GMT
Ignoring Anton's XOR mistake,
Anton Stiglic wrote:
>
> Here are some comments on the code:
>
> static int trng_bit(void)
> {
> long a, b;
>
> b = 0;
> a = GetTickCount();
> while (a == GetTickCount())
> b ^= 1;
> return b&1;
> }
How does this behave on a heavily-loaded* machine? Isn't there a danger
of the while-loop never executing (due to preemption) and returning a
higher percentage of zero bits?
jan
* Forget the heavily-loaded part; how often/likely is a preempt between
the assignment to a and the while check?
--
perl -e 's?ck?t??print:perl==pants if $_="Just Another Perl Hacker\n"'
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: password generator
Date: Thu, 20 Apr 2000 10:24:35 GMT
jan grant wrote:
>
> Ignoring Anton's XOR mistake,
>
> Anton Stiglic wrote:
> >
> > Here are some comments on the code:
> >
> > static int trng_bit(void)
> > {
> > long a, b;
> >
> > b = 0;
> > a = GetTickCount();
> > while (a == GetTickCount())
> > b ^= 1;
> > return b&1;
> > }
>
> How does this behave on a heavily-loaded* machine? Isn't there a danger
> of the while-loop never executing (due to preemption) and returning a
> higher percentage of zero bits?
>
> jan
>
> * Forget the heavily-loaded part; how often/likely is a preempt between
> the assignment to a and the while check?
I am not sure what you mean by the preempt between the assign/while.
However on my computer I have about a 25% cpu load and it behaves fairly
'statistically' random. I am in the middle of trying to make enough
output to run diehard. This means I just leave the program go day and
night (hi/low loads). I will tell the group what I find.
Tom
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Crossposted-To: talk.politics.crypto
Subject: Re: OAP-L3: Semester 1 / Class #1 All are invited.
Date: Thu, 20 Apr 2000 10:31:00 GMT
Anthony Stephen Szopa wrote:
> Was it you who actually suggested that OAP-L3 may be as strong as
> the AES candidates? Someone in these news groups did very recently.
> I thought it was you.
Um no it was not me.
> What a let down: "For starters I am a stupid-ass when it comes to
> abstract algebra..."
>
> I guess your opinions carry little weight in this news group. I
> never gave them much weight any why simply because you never
> supported any of your positions. What did you expect?
Actually I was being very realistic. I am a *high school* student, so
even if I wanted to, I don't know the required math todo it. *however*
as I stated, that doesn't mean others can't.
If you took the mirrored sunglasses off you would notice I am actively
developping a crypto api, peekboo iii and working on odds and ends. And
obviously people reply so they think somewhat ok of my opinion.
> This is all so richly comical.
Because you are not taking anything serious.
> Was it you who also suggested that the posters in this news group
> could help me work out "flaws" in OAP-L3?
No I said "do your own homework".
> So what makes you think I would want or accept your help or anyone
> else's help with OAP-L3? Nearly none of you really seems to
> understand the software anyway.
Post the source code, then we'll talk. Or clean up your algorithm
description with some pseudo code... It's not the easiest description to
follow.
> I want to assure you that I know what questions to ask regarding
> OAP-L3 and I have probably already asked them. I am completing
> Version 4.3 now.
Do you have a copy for the 8051 yet?
> I have also mapped out in detail Version 5.0, Version 5.1, and even
> a subsequent version. All more powerful and more secure and more
> versatile.
How are they more secure?
> Version 5.0 will be an evolutionary leap. Here is a table I
> included in a paper I wrote describing the fundamental concept
> of Version 5.0 and subsequent versions. I am posting it here
> (without any explanation) to put on record that I have already
> done it. For those interested in brain teasers, this could be an
> enjoyable one to figure out what is going on.
>
> When I release Version 4.3, then I will post this entire document
> describing the fundamentals of Version 5.0 (including this table)
> on my web site.
>
> Table 1 -
>
> Usg IIP MixFile1 MixFile2 MixFile3 Digit
> 5 8 6327491805 5382460791 1352094678 9
> 1 3 7246301598 6153704298 7801354926 3
> 6 5 7845069213 4019682573 2184065379 4
> 2 9 1904735268 4273860915 8670159423 7
> 4 1 0819374256 6421935087 9710324865 9
> 3 7 3145682790 8601534279 8523419670 4
> 1 2 1495638027 4139708562 8642375190 4
> 4 0 6712958403 9152743860 7618943205 5
> 6 4 1093865724 6491830725 2705941368 6
> 2 6 8610273495 3091268475 1846327095 8
> 5 8 7568421390 6729480531 0876925413 8
> 3 1 9310845672 0567483192 0835974162 9
>
> Usg = usage
> IIP = initial index pointer
This makes no sense to me whatso ever.
One very strong critic. How do you make the mixfiles to begin with?
Can your prng run on a 8051 with say 64 bytes ram? Stop calling it an
OTP. How are the newer versions any better?
tom
------------------------------
From: [EMAIL PROTECTED] (Taneli Huuskonen)
Crossposted-To: talk.politics.crypto
Subject: Re: OAP-L3: Semester 1 / Class #1 All are invited.
Date: 20 Apr 2000 13:21:54 +0300
=====BEGIN PGP SIGNED MESSAGE=====
Hash: SHA1
In <[EMAIL PROTECTED]> Anthony Stephen Szopa
<[EMAIL PROTECTED]> writes:
[...]
>Table 1 -
>Usg IIP MixFile1 MixFile2 MixFile3 Digit
>5 8 6327491805 5382460791 1352094678 9
>1 3 7246301598 6153704298 7801354926 3
>6 5 7845069213 4019682573 2184065379 4
>2 9 1904735268 4273860915 8670159423 7
>4 1 0819374256 6421935087 9710324865 9
>3 7 3145682790 8601534279 8523419670 4
>1 2 1495638027 4139708562 8642375190 4
>4 0 6712958403 9152743860 7618943205 5
>6 4 1093865724 6491830725 2705941368 6
>2 6 8610273495 3091268475 1846327095 8
>5 8 7568421390 6729480531 0876925413 8
>3 1 9310845672 0567483192 0835974162 9
>Usg = usage
>IIP = initial index pointer
Usg IIP MixFile1 MixFile2 MixFile3 Digit
1 8 6327491805 5382460791 1352094678 9
2 3 7246301598 6153704298 7801354926 7
3 5 7845069213 4019682573 2184065379 1
4 9 1904735268 4273860915 8670159423 3
5 1 0819374256 6421935087 9710324865 0
6 7 3145682790 8601534279 8523419670 6
Taneli Huuskonen
=====BEGIN PGP SIGNATURE=====
Version: PGPfreeware 5.0i for non-commercial use
Charset: noconv
iQA/AwUBOP7aE1+t0CYLfLaVEQIHUwCfVX4MwuwPnlYto8AJW4iZYItupEIAniEv
BsuX8t0/6YeuufEKHuaOytQ1
=3O5z
=====END PGP SIGNATURE=====
--
I don't | All messages will be PGP signed, | Fight for your right to
speak for | encrypted mail preferred. Keys: | use sealed envelopes.
the Uni. | http://www.helsinki.fi/~huuskone/ | http://www.gilc.org/
------------------------------
From: Janaka Anguluaha <[EMAIL PROTECTED]>
Subject: This is a test Pls Ignore
Date: Thu, 20 Apr 2000 04:50:46 +0530
This is a test Pls Ignore
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Crossposted-To: talk.politics.crypto
Subject: Re: OAP-L3: Semester 1 / Class #1 All are invited.
Date: Thu, 20 Apr 2000 11:17:27 GMT
Anthony Stephen Szopa wrote:
> You insist on knowing what you are talking about. And here I will
> prove you do not: the software says explicitly that it is
> recommended that all user input be true random numbers, etc.,
> and two methods are suggested:
>
> 1) number beans and place them in a bottle and shake them up then
> withdraw them one at a time and this will be your input sequence
That's a bad idea. If you start with say just '0' and '1' on the
beans. Well if you had 50 to start (25 '0' and 25 '1') if you pull a
'0' out you are now more likely to pull a '1' out next. So that type of
'rng' is flawed because it becomes biased.
You should have added "and place the bean back when you are done".
> 2) use a deck of cards with the two jokers. Add two jokers from
> another deck and label each one with one of the four suits giving
> a deck of 56 cards with 14 cards in each suit with the jack, queen,
> king, joker representing the 11, 12, 13, & 14. Shuffle this deck
> and then peel off one card at a time from the top of the deck and
> place each card in a pile according to suit. You will then have
> four 14 number sequences that can be used for input, etc.
>
> Did you not read the Help Files?
>
> Obviously not.
Well "help files" should turn into "credible academic project". Make
your information more presentable (and mature) and people will take you
seriously.
> I think you are pathetic to present yourself as a credible poster
> when you clearly do not know what you are talking about.
And you want positive feedback when you make comments like this? What
do *we* *owe* you?
Tom
------------------------------
From: Francois Grieu <[EMAIL PROTECTED]>
Subject: What is going on with 'sci.crypt.research' ?
Date: Thu, 20 Apr 2000 13:17:19 +0200
The last posting on 'sci.crypt.research' was on March 5,
and the FAQ on March 13. Since then, nothing, either
on my server or DejaNews.
One of my message submitted April 4 has not appeared.
Any idea of what is (not) going on ?
Francois Grieu
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: This is a test Pls Ignore
Date: Thu, 20 Apr 2000 11:19:18 GMT
Janaka Anguluaha wrote:
>
> This is a test Pls Ignore
Yup we can all see you. Feel proud? :-)
Tom
------------------------------
From: schack01 <[EMAIL PROTECTED]>
Subject: Des S-Boxes
Date: Thu, 20 Apr 2000 11:11:47 GMT
Hello all!
If i can modify the s-boxes in any way, is it possible to
then "easaly" discover what key that are being used.
If so? what to write in s-boxes and how to implement the
key-extract ?
Regards
Schack
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: Des S-Boxes
Date: Thu, 20 Apr 2000 12:01:41 GMT
schack01 wrote:
>
> Hello all!
>
> If i can modify the s-boxes in any way, is it possible to
> then "easaly" discover what key that are being used.
>
> If so? what to write in s-boxes and how to implement the
> key-extract ?
turn the sboxes into a identity permutation. That should make it easy
to attack, as to how well... just look at the algorithm.
Tom
------------------------------
** 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
******************************
