Cryptography-Digest Digest #738, Volume #13 Fri, 23 Feb 01 14:13:00 EST
Contents:
Re: New unbreakable code from Rabin? ("Tony T. Warnock")
Re: New unbreakable code from Rabin? (Bill Unruh)
�������� �� ������, �� ������!!!!!!! ("kononec")
Re: looking for 16-bit RNG... ("Douglas A. Gwyn")
Re: New unbreakable code from Rabin? ("Douglas A. Gwyn")
Re: Comments on Rabin's proposal ("Douglas A. Gwyn")
Re: The Key Vanishes: Scientist Outlines Unbreakable Code, Read it and ("Douglas A.
Gwyn")
Random numbers from your sound card ([EMAIL PROTECTED])
Re: super-stong crypto, straw man phase 2 (John Myre)
fiat shamir (zipa)
Open-SSH(portable) and EGD ([EMAIL PROTECTED])
Re: New unbreakable code from Rabin? ([EMAIL PROTECTED])
Re: Any alternatives to PGP? (Alberto)
Re: Super strong crypto (JPeschel)
Re: Any alternatives to PGP? ("Sam Simpson")
Re: Random numbers from your sound card (Mok-Kong Shen)
Re: Powers of Complex Associative Functions (Jim Steuert)
----------------------------------------------------------------------------
From: "Tony T. Warnock" <[EMAIL PROTECTED]>
Subject: Re: New unbreakable code from Rabin?
Date: Fri, 23 Feb 2001 10:18:30 -0700
Reply-To: [EMAIL PROTECTED]
Page 107778788373812 of "Gone With the Solar Wind"
------------------------------
From: [EMAIL PROTECTED] (Bill Unruh)
Subject: Re: New unbreakable code from Rabin?
Date: 23 Feb 2001 17:25:22 GMT
In <8Uol6.20332$[EMAIL PROTECTED]> wint <[EMAIL PROTECTED]>
writes:
>In article <3a93968d$[EMAIL PROTECTED]>, [EMAIL PROTECTED] says...
>> John Savard <[EMAIL PROTECTED]> wrote:
>>
>> > Obviously, any random bit stream two participants are capable of
>> > exchanging is capable of being stored by an adversary.
>>
>> The point is that this isn't such a bit stream.
>> No one generates, transmits or exchanges this bit stream.
>> They only exchange information on how to extract a bit
>> stream from a transient, public pool of random data.
Both people need access to it. Since it is public, so does a third
person, and can record it. "Noone can record that much data" is in the
same league as "no one can factor numbers". Ie, it may well be
unbreakable in practice, but in theory it is as breakable as any
other scheme. It sounds like an attempt at creating a one time pad from
a public source. While the pad is provably secure IF the pad is not
known, in this case the pad is a known subset of a large number of pads
(actually not that large, since the number of reliable public random
bitstreams is not that great-- remember both parties must be able to
reliably extract the same bitstream from the public source, and such
reliable bitstreams are not that common.)
------------------------------
From: "kononec" <[EMAIL PROTECTED]>
Crossposted-To:
relcom.www.users,relcom.x,sci,soc,soc.culture,soc.culture.brazil,soc.culture.irish,soc.culture.israel,soc.culture.scottish
Subject: �������� �� ������, �� ������!!!!!!!
Date: Sat, 24 Feb 2001 02:32:20 +1000
�� "�������" ���������� ����������� �������� ������� � ������ ����� �������
�� ������.
� ������� ������� �������� ���� ��������, � ����� ���أ ��������������
�����. ����� �� ������ ���������� �� ������ �� ������: �. �����������, ��.
���������������� 19, ����� �����������, � �-��. ����. �������: 8(22)
46-72-89
mail-to:[EMAIL PROTECTED]
http://www.primrek.by.ru
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: looking for 16-bit RNG...
Date: Fri, 23 Feb 2001 16:55:26 GMT
Rik Blok wrote:
> Does anybody know of a simple and fast 16-bit pseudo-random number
> generator I could use? There are more constraints: I want to use it on
> a Lego Mindstorms robot which can only handle 16-bit integers (and only
> has enough storage for 32 of them...and no support for arrays). I was
> thinking something like a linear congruential generator but is there
> anything better? If I do use a LCG what are some good constants to use?
Your choices are basically LCG or shift-register. Here is a LCG
implementation; like any 16-bit PRNG it is not of crypto quality.
However, it may be enough for the LEGO MindStorms robot (which by
the way is a great toy for adults).
static unsigned Next16 = 1; /* current state (seed) */
unsigned Rand16( void ) { /* returns "random" value 0 .. 65535 */
return Next16 = (Next16 * 15245 + 12345) & 0xFFFF;
}
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: New unbreakable code from Rabin?
Date: Fri, 23 Feb 2001 16:56:21 GMT
[EMAIL PROTECTED] wrote:
> I think we can agree that the "random" bit stream must come
> from a completely trusted source for this approach to have any value.
No, I don't agree, for reasons explained in another post.
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: Comments on Rabin's proposal
Date: Fri, 23 Feb 2001 17:04:17 GMT
Anonymous wrote:
> In my opinion the generation of these random number strings could be
> relatively easily fudged to appear random whilst not actually being
> so........
Of course they can. Any really good binary encryption method
when applied to a sequential counter will generate output that
is indistinguishable from uniform random noise to all but the
initiated. That could be further obscured by e.g. XORing with
the contents of a very long random string (which can be reused).
But the practical issue with that is that it is *really* hard
to hide all patterns in such a huge volume of data, which would
be intensely scrutinized.
If such a scheme were to be implemented, one would expect that
a commercial consortium would be responsible for creation and
validation of the physical source of randomness and its
subsequent processing; they would stand to lose a *lot* if they
weren't completely open and honest.
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: The Key Vanishes: Scientist Outlines Unbreakable Code, Read it and
Date: Fri, 23 Feb 2001 17:11:21 GMT
Mok-Kong Shen wrote:
> My point was that, since a crypto-quality generator is
> 'by definition' infeasible to be cracked (in practice,
> i.e. wrpt to opponent's resources), its direct use is just
> as fine as indirectly via the proposed scheme (with its
> additional 'proofs').
Not unless one has a *proof* of uncrackability.
That is the whole purpose behind involving genuine
random bits in the process.
> ... I don't see that it differs in 'nature' from
> the infeasibility of brute-forcing, e.g. 128 bits of key,
Brute-force infeasibility has never constituted a proof
of security, even for limited resources.
> On the whole, I surmise that it was the journalism of
> the NY Times that has created a flare/claim of (absolute)
> 'unbreakability' of the scheme and has consequently
> caused much unnecessary discussions/misinterpretations.
I don't say I think the method is of any real practical
value. The unbreakability is evident; for any assumed
adversarial capability, a key location schedule can be
devised that defeats the adversary. However, it may be
a horrible waste of bandwidth.
One should never count on mass-media journalists to give
a reasonable presentation of any technical issue. The
best we can hope for is that they don't mislead the public
too much, and possibly that they encourage public interest
where it would actually do some good.
------------------------------
From: [EMAIL PROTECTED]
Subject: Random numbers from your sound card
Date: 23 Feb 2001 17:58:19 GMT
==== NOTE =====
Something wierd is going on, that's the third time i post this article and it
appears that it got lost somwhere on his way ... Hopefully this one will post
correctly. Sory if someones actually gets more than one copy, and if you do,
please reply to this one and not to the others.
===============
A "real" random number generator (as opposed to PRNGs), that would
require only hardware that the average home-PC has, could be a pretty
usefull thing, some attempts were made by timing (mod a small nuber)
the distance between interrupts from some external devices (mouse and
keyboard mostly) with a high pecision timer. This way was for example
used in older PGP versions and in some other cryposoftware too. Such
an approach might work for smaller amounts of data but imagine
yourself pressing 8192 keys to generate 8kBits of random data, not
quite the healthiest thing (both for you and your keyboard :)
A few weeks ago i came up with an idea: Using sound input to
generate random numbers. When you record any piece of audio from an
analogue source to your computer, you will always hear some noise
that was never present in the original audio, this is the result of
Electro Magnetic Radiation picked up by the ADC (Analogue to
Digital Converter) in your sound card. In fact the few lowest bits
can be cosidered random, as they are full of White radio noise, and
can be used to generate random numbers.
The algorithm is pretty simple:
We input a 512 words sized block from the sound card.
(Stereo, 44,100 Hz, 16 bits)
We take only the least significant bit from each sample, and remain
with 512 bits (64 bytes) of (supposedly) random data.
We use some mixing/compressing function to make it even more random
(look at the comments below)
The resulting data seems to be random and it passes the DieHard test
suite.
Comments:
At the third step i currently use the MD5 transformation. (Note
that only the transformation is used, i don't pad it with anything
including the size as MD5 does)
The data seems to pass the diehard tests even without the md5
so do i need it at all? no idea ... Maybe i should use some other
function?
Under "passes the diehard tests" i mean that it doesent gets any
p-value p>0.99 or p<0.001 and even those are rare (~4 times and
in different places each time)
As an idea, maybe i should use the parity of the sample instead of
the lsb, as far as i understand it the parity of some group of bits
has atleast the same enthropy as the bit with highest enthropy in
the group ...
The user can screw all of this up by incorrect seetup, for example
by recording from a digital device (Digital -> No pass thru ADC ->
No white noise -> No randomality) or ecording with very low volume,
so it would be helpfull to use use some randomality-check algorithm
that is fast and doesn't requires large ammounts of data (for
DieHard, which requires a total of ~12 mb of data, i had to record
for nearly 1 hour and 15 minutes ...) to give an on the fly
indication of haw random the data that we get is.
Currently the program idles around 65% of the time, waiting for the
next audio buffer to come in (on my AMD K6-2 500mHz), so there is
place for additions to the "filtering" part without causing
slowdowns.
Also, it could be intresting to try to do the same stuff with TV
cards, it should give much more data and thus speed the whole
thing up, not having a TV card and any knowledge about the APIs
used with them, it's problematic for me to test this out, but
you're welcome.
I would like to tr some more tests of it, if someone can point to any
other randomality test suite i would be really thankfull
And i definetly would like to hear the general opinion on this idea.
The DieHard test results, sourcecode (Delphi 5) and an executable
(win32) are avaiable at the following address:
http://viktor-p.narod.ru/sb_rng.zip
If you download it and try to run it, read the comments.txt before
doing anything else.
You can send me an email to [EMAIL PROTECTED]
Viktor Pilpenok
----- Posted via NewsOne.Net: Free (anonymous) Usenet News via the Web -----
http://newsone.net/ -- Free reading and anonymous posting to 60,000+ groups
NewsOne.Net prohibits users from posting spam. If this or other posts
made through NewsOne.Net violate posting guidelines, email [EMAIL PROTECTED]
------------------------------
From: John Myre <[EMAIL PROTECTED]>
Subject: Re: super-stong crypto, straw man phase 2
Date: Fri, 23 Feb 2001 11:01:14 -0700
Doug - I assume you will correct any misrepresentations
I have made here...
David Wagner wrote:
<snip>
> I guess I don't understand. This is a heuristic trick, but there are
> many other heuristic tricks, and they all have to be evaluated on a
> cost-benefit basis. The cost of your proposal is very high: It doubles
> bandwidth requirements. In comparison, doubling the number of rounds is
> much cheaper (network bandwidth is scarcer than CPU cycles) and seems
> likely to provide similarly strong-albeit-heuristic protection against
> cryptanalysis. I'd like to understand what your proposal provides that,
> say, Triple-DES-CBC doesn't already offer. Am I overlooking something?
What you are overlooking is the real question: why should
we believe that doubling the number of rounds would provide
protection to a similar extent? Or tripling, or more?
Doug's contention is that even *unknown* attacks could be
foiled by the fact that there is very little data encrypted
under any one key. (What we could actually prove in this
regard I don't know; we'd need something from the basic
block encryption to start with. Injecting entropy obviously
helps sometimes: consider OAEP or probabalistic encryption.)
I think his idea is to try to arrive at information-theoretic
arguments for the security of a cipher mechanism. What do
we need from a basic block cipher to get "provable" security,
if we promise to encrypt no more than X bits under any one
key, and every block as at least Y bits of random data?
JM
P.S.
I don't know that Doug insists on using half of the bandwidth
for new random data. If we could get any provable mechanism
going, the next question might be: what is the necessary overhead?
Maybe one new random bit per 128-bit block is enough. Or maybe
provable security requires using at *least* half the bandwidth
for random data. Or perhaps in depends on, well, who knows.
------------------------------
From: zipa <[EMAIL PROTECTED]>
Subject: fiat shamir
Date: Fri, 23 Feb 2001 13:18:27 -0500
In Fiat-Shamir the prover chooses a random r<n in the first step.
If the prover sends X=r^2 +m*n (for some random m<n) instead of
X=r^2 (mod n) can the verifier find r ?
------------------------------
From: [EMAIL PROTECTED]
Subject: Open-SSH(portable) and EGD
Date: Fri, 23 Feb 2001 18:29:19 GMT
Hi,
How does (should?) a person set up a binary (precompiled) version of
Open-SSH so that it uses the egd.pl daemon?
Thanks,
Gord
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: New unbreakable code from Rabin?
Date: 23 Feb 2001 18:44:36 GMT
Douglas A. Gwyn <[EMAIL PROTECTED]> wrote:
>[EMAIL PROTECTED] wrote:
>> I think we can agree that the "random" bit stream must come
>> from a completely trusted source for this approach to have any value.
>No, I don't agree, for reasons explained in another post.
So to summarize, your belief then is that the Rabin approach still
has value even if the bit-stream is non-random and any portion of it,
going arbitrarily into the past, can be re-generated at will by
an attacker.
Do I have this correct?
What is the value of the Rabin approach under this circumstance?
Steve
------------------------------
From: Alberto <[EMAIL PROTECTED]>
Subject: Re: Any alternatives to PGP?
Date: Fri, 23 Feb 2001 18:49:29 GMT
>Alberto wrote:
>> I've decided to leave PGP.
>why?
No real reason. But I feel that I can't trust NAI anymore... Just a
feel... Sorry...
>> What is a good alternative?
>GnuPG...
Thanks to all for the answers.
------------------------------
From: [EMAIL PROTECTED] (JPeschel)
Date: 23 Feb 2001 18:52:28 GMT
Subject: Re: Super strong crypto
Douglas A. Gwyn [EMAIL PROTECTED] writes, in part:
>I don't think so-called differential cryptanalysis
>can even get a foothold.
Why "so-called," Doug?
Joe
__________________________________________
Joe Peschel
D.O.E. SysWorks
http://members.aol.com/jpeschel/index.htm
__________________________________________
------------------------------
From: "Sam Simpson" <[EMAIL PROTECTED]>
Crossposted-To: alt.security.pgp,comp.security.pgp.discuss
Subject: Re: Any alternatives to PGP?
Date: Fri, 23 Feb 2001 18:57:19 -0000
=====BEGIN PGP SIGNED MESSAGE=====
Hash: SHA1
Alberto,
I'd very strongly recommend CKT build 6.5.8 build 3 (see
http://irfaiad.virtualave.net/ ). It supports all the necessary algorithms
(including Blowfish, 3 sizes of AES and Twofish) and is patched against the
ADK bug).
Oh, it's released with source.
- --
Regards,
Sam
http://www.scramdisk.clara.net/
=====BEGIN PGP SIGNATURE=====
Version: 6.5.8ckt http://irfaiad.virtualave.net/
iQA/AwUBOpayee0ty8FDP9tPEQLwjACg5hbtEqyAl9w4W1cDOmq1yPheDlUAoKeF
UPr9ovw5FWO6etYYfEIupmBP
=sQV4
=====END PGP SIGNATURE=====
Alberto <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> >Alberto wrote:
> >> I've decided to leave PGP.
> >why?
>
> No real reason. But I feel that I can't trust NAI anymore... Just a
> feel... Sorry...
>
> >> What is a good alternative?
> >GnuPG...
>
> Thanks to all for the answers.
>
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Random numbers from your sound card
Date: Fri, 23 Feb 2001 20:03:01 +0100
[EMAIL PROTECTED] wrote:
>
[snip]
> I would like to tr some more tests of it, if someone can point to any
> other randomality test suite i would be really thankfull
You can have a look of the following:
http://csrc.nist.gov/rng/
M. K. Shen
------------------------------
From: Jim Steuert <[EMAIL PROTECTED]>
Subject: Re: Powers of Complex Associative Functions
Date: Fri, 23 Feb 2001 14:32:39 -0500
The function I supplied in the initial post is not a good example
associative function, as it doesn't reference b1 at all. Sorry about that.
Here are two better examples: C = A OP1 B
c0 = a0*b0 + a2*b1 + a1*b2
c1 = a0*b1 + a1*b0 + a2*b2
c2 = a1*b1 + a0*b2 + a2*b0
and C = A OP2 B
c0 = a0*b0 + a2*b3
c1 = a1*b1 + a3*b2
c2 = a0*b2 + a2*b1
c3 = a1*b3 + a3*b0
Note that the second is a generalization of normal (Cayley) 2x2
matrix multiplication. I have generated several various examples of the
above two forms which are associative. They are also "balanced"
in the sense, that for a given fixed "non-zero" A vector value, the result
ranges through a different C values for each distinct B value. Xor may
also be useful, although more as an associative hash functions than
for Diffie-Hellman exponentiation.
I came across a use of associative non-commutative "Verification Codes"
in a reference to a paper by French mathematician Jean Bosset in
"01 Informatique Mensuel 1977". He used 2x2 matrices modulo a
prime, with each symbol represented by a different matrix which is
a generator of the group of the matrix multiples.
Jim Steuert wrote:
> With a simple c program, I have been able to create large numbers of
> arbitrarily complex associative vector functions of various dimensions.
> For example, the vector operator OP defined as:
> c0 = a0*b0 + a3*b2 + a2*b3
> c1 = a1*b3 + a1*b2 + a1*a0
> c2 = a3*b3 + a2*b0 + a0*b2
> c3 = a3*b0 + a2*b2 + a0*b3
> and where * is associative, * is both left and right distributive over
> +. Note
> that only the + operator needs to be commutative.
> The (*,+) can be pointwise arithmetic modulo a large prime, or can
> recursively
> in turn be a vector scheme as above.
> Because of the associative natures of this, powers may be built up
> in logarithmic time (as in x, x^2, x^4, x^8) and "OP-ified" (multiplied)
> and
> used in a Diffie-Hellman-like scheme.
> I am aware that simple quaternion and matrix schemes have been
> proposed,
> but I am not aware of any more complex associative schemes.
> More importantly, I am not aware of any attacks that generally apply to
> arbitrary associative functions.
> Does anyone know of any other schemes like this?
> -Jim Steuert
------------------------------
** 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
******************************
