Cryptography-Digest Digest #740, Volume #13 Fri, 23 Feb 01 19:13:01 EST
Contents:
Re: Powers of Complex Associative Functions (Jim Steuert)
Re: Really big numbers in C (Ben Cantrick)
Re: Super strong crypto ("Douglas A. Gwyn")
Re: Super strong crypto ("Douglas A. Gwyn")
Re: Really big numbers in C ("Douglas A. Gwyn")
Freq analysis of a possible cyphertext. (Ben Cantrick)
Re: super-stong crypto, straw man phase 2 (SCOTT19U.ZIP_GUY)
Re: Rnadom Numbers (Eric Lee Green)
Re: super-stong crypto, straw man phase 2 ("Trevor L. Jackson, III")
Re: Any alternatives to PGP? ("Iain White")
Re: Random numbers from your sound card ("Trevor L. Jackson, III")
Re: Random numbers from your sound card ("Trevor L. Jackson, III")
Re: Really big numbers in C ("Michael Scott")
----------------------------------------------------------------------------
From: Jim Steuert <[EMAIL PROTECTED]>
Subject: Re: Powers of Complex Associative Functions
Date: Fri, 23 Feb 2001 17:40:02 -0500
As a tiny example, I will take the second linear function OP2.
Here the function, as in your notation can also be expressed in
(non-constant) matrix form
as: [c] = [a] OP2 [b] is defined as:
| c0 | | a0 0 0 a2 | | b0 |
| c1 | | 0 a1 a3 0 | | b1 |
| c2 | | 0 a2 a0 0 | | b2 |
| c3 | | a3 0 0 a1| | b3 |
Note that I am NOT proposing any linear function, the exact placement of
the vector components of vector [a] in multiple places, or structure of the
matrix A is important, as in the OP2 example above, in order to make it
associative, which is necessary for Diffie-Hellman usage.
Choosing mod 11, and plugging in values a0 = 7, a1=5, a2 = 8, a3 = 3,
makes the matrix A non-singular (since det A = a0*a1*a0*a1 = 4 mod 11).
Note that the matrix IS NOT THE FUNCTION.
| c0 | | 7 0 0 8 | | 7 |
| c1 | | 0 5 3 0 | | 5 |
| c2 | = | 0 8 7 0 | | 8 |
| c3 | | 3 0 0 5 | | 3 |
therefore: a^2 = [7 5 6 3] mod 11
now, plugging these into the formula: a^2 =
| a0 0 0 a2 | | a0 |
| 0 a1 a3 0 | | a1 |
| 0 a2 a0 0 | | a2 |
| a3 0 0 a1| | a3 |
we get a^4 =
| 7 0 0 6 | | 7 |
| 0 5 3 0 | | 5 |
| 0 6 7 0 | | 6 |
| 6 0 0 5 | | 3 |
==> [ 1 10 6 2 ] mod 11
and so on for arbitrarily higher powers of vector [a] using OP2.
Since they are associative, we can create a^6 = a^4 OP2 a^2,
so we can form any power by multiplying (OP-ifying) the
already-built powers. Thus we can simply create a huge power
of vector [a] in logarithmic time.
Hope that helps,
-Jim Steuert
Mok-Kong Shen wrote:
> Jim Steuert wrote:
> >
> > No, my intention was not that the specific function was a cipher by simply
> > applying it to plaintext. My intention in a Diffie-Hellman sense is that an
> > "exponent value" is to be hidden in the result of exponentiating this function.
> > For example, assume the matrix A, (especially if each cell of the matrix is
> > itself another (say 3-part) associative function). Raise it to some huge (1024
> > bit)
> > exponent. That exponent encodes a secret. The result is another matrix
> > A-prime = A^k(seed val). What is the possiblity of finding k, ie. of taking the
> > discrete logarithm based on the power of a matrix (or some arbitrarily complex
> > associative
> > function) (i.e. of finding the hidden exponent). First, the seed value must be
> > a generator of the multiplicative group of the function. I am not aware of any
> > methods for finding discrete logs base some arbitrary function. (Please let
> > me know if there are any such methods). I think that these functions may be
> > simpler to implement than exponentiation.
> >
> > The second use of this multi-level associative construction is in creating
> > associative hash functions, which can have as an additional parameter an
> > exponent as well as a seed value, or can be used, as in Jean Bosset's
> > application,
> > as a means of incrementally (additively) hashing a long record or file, because
> > it is
> > associative.(although that is a solution in search of a problem)
> > Also, in that use, xor can be used instead of modular addition. The
> > constructions I suggested do a lot of "mixing", which is useful for hashing.
>
> Could you give a very tiny numerical example to ease
> understanding? Thanks.
>
> M. K. Shen
------------------------------
From: [EMAIL PROTECTED] (Ben Cantrick)
Subject: Re: Really big numbers in C
Date: 23 Feb 2001 15:45:07 -0700
In article <[EMAIL PROTECTED]>,
Taylor Francis <[EMAIL PROTECTED]> wrote:
>Anyone know how to handle really bug numbers in C? I'm talking
>1024-4096 bit numbers...my compiler only handles 64 bit (that I can
>tell...)
There's some GNU library for arbitrary precision arithmetic.
Can't remember what it's called. Throw "GNU arbitrary precision"
into Google and see what you can find.
-Ben
--
Ben Cantrick ([EMAIL PROTECTED]) | Yes, the BGC dubs still suck.
BGC Nukem: http://www.dim.com/~mackys/bgcnukem.html
The Spamdogs: http://www.dim.com/~mackys/spamdogs
The Nissan 300ZX twin-turbo: Drugs would be cheaper.
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: Super strong crypto
Date: Fri, 23 Feb 2001 22:19:06 GMT
> Why "so-called," Doug?
Because it's but one, rather weak, exploitation of the idea.
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: Super strong crypto
Date: Fri, 23 Feb 2001 22:21:44 GMT
David Wagner wrote:
> if this is the only attack on your proposal, then your proposal seems
> to be a real contribution. Nonetheless, I did want to point out that
> your proposal does not stop all attacks.
Thanks; I'm not trying to sell a particular product,
but rather to get people to think "along these lines".
I have one specific application in mind, but it is a
general issue that seems worthy of further development.
Although if there is a fundamental problem with it in
practice, I want to know that too!
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: Really big numbers in C
Date: Fri, 23 Feb 2001 22:25:21 GMT
Taylor Francis wrote:
> Anyone know how to handle really bug numbers in C? I'm talking
> 1024-4096 bit numbers...
This is a FAQ (I don't know if it is answered in the sci.crypt
FAQ periodic posting). The simple answer is, this calls for an
implementation of multiple-precision arithmetic (modulo word size),
and there are several available. Try a Web search for:
bignum
multiple precision
GMP
OpenSSL
MIRACL
and undoubtedly others you will hear about in follow-ups.
------------------------------
From: [EMAIL PROTECTED] (Ben Cantrick)
Subject: Freq analysis of a possible cyphertext.
Date: 23 Feb 2001 16:20:53 -0700
Greetings, sci.crypt!
I am one of those annoying newbies y'all hate so much. ;] But don't
worry, I'm not here to propose a lame new crypto system, claim I've found
a new factoring algorithm, or say that I decoded the Voynich manuscript.
Nah, instead I'm just gonna bore you to death with trivial problems. ;]
Several days ago, a post was made to boulder.general (an obscure
newsgroup for the town of Boulder, Colorado.) You can see a copy at
http://www.dim.com/~mackys/junk/cyphertext. This appears to be
random jibberish sent by a USENET spammer.
But, it looked to me like just maybe it could be mistaken for a
cyphertext of some sort. And if it was, probably produced by a mono-
or poly-alphabetic substitution cypher. So I started poking at it,
just for giggles.
I wrote a couple of programs to help me out. For those of you
that care, copies are in the same directory as the cyphertext.
(http://www.dim.com/~mackys/junk/) Using these programs I tried
several things:
- I generated the 25 non-trivial cylical mono-alpha (Cesearian)
encryptions of the possible cyphertext. None of these were intelligible,
at least to my eye.
- I wrote a small program to do frequency analysis of characters in
text. I rant it on a randomly generated file full of characters, a
sample piece of english cut from a lengthy posting on a web board I
frequent, and on the possible cyphertext. All three were of approximately
the same length (2000 characters).
The program and samples are available at the aforementioned web
location, so I won't repost the results in full here. Run it yourself
if you care. But basically, the letter frequencies were almost identical
in the random text, classic English letter frequencies in the sample
english text, and somewhere inbetween in the possible cyphertext.
So I'm left with a dilemma. At this point I think it's just random
garbage. But there there appear to be patterns in this possible cyphertext.
Why would moron spammers bother to put vaguely textual patterns in random
spam? Am I tilting at a windmill here? Is it worth going back and doing
a digraph and trigraph frequency analysis? Any other opinions?
-Ben
P.S. For any other newbies lurking, there's a fun little article on
simple crypto in Phrack magazine @ http://www.2600.com/phrack/p51-13.html
--
Ben Cantrick ([EMAIL PROTECTED]) | Yes, the BGC dubs still suck.
BGC Nukem: http://www.dim.com/~mackys/bgcnukem.html
The Spamdogs: http://www.dim.com/~mackys/spamdogs
Space is an illusion; disk space, doubly so.
------------------------------
From: [EMAIL PROTECTED] (SCOTT19U.ZIP_GUY)
Subject: Re: super-stong crypto, straw man phase 2
Date: 23 Feb 2001 23:28:11 GMT
[EMAIL PROTECTED] (Henrick Hellstr�m) wrote in
<976mm7$94c$[EMAIL PROTECTED]>:
>"John Myre" <[EMAIL PROTECTED]> skrev i meddelandet
>news:[EMAIL PROTECTED]...
>> If a cipher can be attacked with one ciphertext block in
>> a practical way, without even known plaintext, then it is
>> hopeless. But most modern attacks on decent ciphers
>> require largish amounts of data. Could you prove that a
>> given block cipher (triple-DES, say, or Rindael) requires
>> at least, say, 4 known plaintext/ciphertext pairs to be
>> broken? Of course, so far as we know, you need way more
>> than that. Is there any provable minimum?
>
>The provable (absolute) minimum, based only on the assumption that the
>key is recovered by means of cryptoanalysis, is the amount of chosen
>plain text required for a brute force key search to succeed. This
>minimum is usually equal to the size of the key. If I am not mistaken,
>e.g. Rijndael with a 256-bit key would always be broken by such a
>theoretical attack given exactly two blocks of known plain text. I don't
>know if it would take three or maybe four blocks of known plain text to
>break TwoFish because of it's loss of internal data caused by the shift
>left by one operation.
>
>I base these conclusions on the observation that relatively small
>portions of internal key data could be used to unequivocally determine
>the key. For instance, it seems to be common practice to set up S-boxes
>so that only one value S(x) or at most two values S(x), S(y)
>unequivocally determines the entire S-Box. The only non-static
>substitution in Rijdael seems to be xor-operations with internal key
>data.
>
>Let's just say that I would find it somewhat comforting to find out that
>I was completely wrong about this.
>
Sorry to say your not completely wrong about this problem of short
keyed ciphers. However most so called experts will encourage you to use
them trying to get you to belive that a dumb blind search would take
longer than the sun to burn out before a solution is found.
However as noted in another thread most ciphers do have a much faster
theoritically break than a blind search. I would suggest you use more
than one cipher in series and at least one of those should be a large
key cipher like scott19u if you want more security.
David A. Scott
--
SCOTT19U.ZIP NOW AVAILABLE WORLD WIDE
http://www.jim.com/jamesd/Kong/scott19u.zip
Scott famous encryption website **now all allowed**
http://members.xoom.com/ecil/index.htm
Scott LATEST UPDATED source for scott*u.zip
http://radiusnet.net/crypto/ then look for
sub directory scott after pressing CRYPTO
Scott famous Compression Page
http://members.xoom.com/ecil/compress.htm
**NOTE EMAIL address is for SPAMERS***
I leave you with this final thought from President Bill Clinton:
------------------------------
From: [EMAIL PROTECTED] (Eric Lee Green)
Subject: Re: Rnadom Numbers
Reply-To: [EMAIL PROTECTED]
Date: 23 Feb 2001 17:43:37 -0600
On Fri, 23 Feb 2001 07:41:15 GMT, wint <[EMAIL PROTECTED]> wrote:
>In article <968kvd$s48$[EMAIL PROTECTED]>, Viktor "CK" Pilpenok
><[EMAIL PROTECTED]> says...
>> Is there any algorithm that allows to estimate the randomness of a
>> stream of numbers?
>
>May find something of interest here
> http://www.protego.se/statistictest_en.htm
Note, however, that statistical randomness is a necessary but not
sufficient quality for detirming the suitability of a PRNG for
cryptographic use. Unpredictability is the other quality of interest.
For example, no intermediate value should be able to be computed by an
attacker based upon previous or future values. If you can predict the
intermediate value (or at least narrow it down to a smaller subset of
possible values) based upon previous or future values, this can leak
key information and other important information to the attacker,
despite the fact that the PRNG passes all statistical tests. This implies
that you want to use a one-way function to generate the output values, i.e.,
a function that cannot be decomposed back to its inputs other than via
brute force. This also implies that the inputs must be of sufficient size
that brute force is not a practical attack.
The PRNG has been a major problem with most cryptosystems at some time or
another. Netscape Navigator and Kerberos both shipped with broken
PRNG's at some point in time, for example. Design of cryptographic-quality
PRNG's should not be undertaken lightly, or without reading the
cryptographic literature on the subject. Asking here is not going to
give you all the information you need to produce a cryptographic-quality
PRNG -- you need to do your homework.
--
Eric Lee Green Linux Subversives
[EMAIL PROTECTED] http://www.badtux.org
====== Posted via Newsfeeds.Com, Uncensored Usenet News ======
http://www.newsfeeds.com - The #1 Newsgroup Service in the World!
======= Over 80,000 Newsgroups = 16 Different Servers! ======
------------------------------
From: "Trevor L. Jackson, III" <[EMAIL PROTECTED]>
Subject: Re: super-stong crypto, straw man phase 2
Date: Fri, 23 Feb 2001 23:52:00 GMT
David Wagner wrote:
> For almost all of the publicly known attacks, doubling
> the number of rounds adds substantial protection.
Is this a general consensus for homomorphic ciphers (or what ever the
term is for ciphers composed of identical rounds)? Are heteromorphic
ciphers too complex to analyze or does doubling the complexity of the
round (say two variants) have an effect similar to doubling the number
of identical rounds?
------------------------------
From: "Iain White" <[EMAIL PROTECTED]>
Crossposted-To: alt.security.pgp,comp.security.pgp.discuss
Subject: Re: Any alternatives to PGP?
Date: Sat, 24 Feb 2001 00:55:45 +0100
"Ryan M. McConahy" <[EMAIL PROTECTED]> wrote
> -----BEGIN PGP SIGNED MESSAGE-----
> Hash: SHA1
>
> I myself haven't ever really trusted NAI. I used to use the pgpi.org
> versions, but then I found out about CKT. They're much better. They feel
> more 'user friendly'.
>
> -----BEGIN PGP SIGNATURE-----
> Version: 6.5.8ckt http://irfaiad.virtualave.net/
> Comment: KeyID: 0xA167F326A5BE3536
> Comment: Fingerprint: 838C 815E 5147 2168 5A76 16F1 A167 F326 A5BE 3536
>
> iQA/AwUBOpbHUKFn8yalvjU2EQIY/wCfYYVYFs99VC4KvflmQFUYlPBryvAAnjpw
> D3E49DGyP/obQzicY17Mffcs
> =4V1g
> -----END PGP SIGNATURE-----
=====BEGIN PGP SIGNED MESSAGE=====
Hash: RIPEMD160
I use the ckt build of pgp as well, and I don't want to discourage any
onefrom using it.
Nonetheless I consider it a very bad idea to propose the pgpi and/or the
ckt versions of pgp as an alternative to nai-pgp if you don't trust nai.
This is why:
Back when the US had strong and restrictive crypto laws, the pgpi version
was based on the nai-pgp freeware version. Since the US loosened their
crypto laws, there are no real pgpi versions any more, they now simply
mirror the nai versions. And the ckt builds are based on the pgpi version.
Therefore, if there is a serious bug or a backdoor in a nai version of pgp,
it is also in the according pgpi / ckt version.
Okay, it might be possible that Imad found that flaw and corrected it when
making the ckt builds (btw: I know he found and corrected several minor
flaws, but I'm talking about serious ones) but then imho he would have made
that public and we would all *know* (and not only fear) that something's
wrong with nai-pgp.
So if you don't trust nai then imo you either must use a version of pgp
that was programmed before prz went to nai or you must change to gpg, which
of course (at least for Windoze users) means using a command line or a beta
version of a gui.
Out of those two alternatives, I prefer gpg because it's newer and gives
you more options and bigger keys.
Regards,
Iain
=====BEGIN PGP SIGNATURE=====
Version: 6.5.8ckt
iQEVAwUBOpbolYkxr1kQn7QdAQN1cQgAhpjdDWZpgGs3IRC/qbZnHtZ0n3pQHixS
mr2VYChVlN/Gj3pAkAzorDlZQ9CY07g1XAq9Dmb2v5foykgV7udTGEcJZidS9T4w
OsicxhzV/EvnuIN70xjruSa43CHqBuaYZ6nP4hR1BOilcSqbewwa9Sniakha7qop
yyW1+Os3s3U5PBjmNdBHOi8kzU/ib7GB0UgxbyjwlyNIu8A14GdNIVhdP2pbLDd5
tv/ndNVBfqrpx8CpI51NxxdmqRW/IM2jSSZMwMeC3+uyr2uBegm7mdknZEyDPbAh
8Llzo4KVxMrsyLgHjpSfHbaspJUNP7L4U5pGem12Lg/MHRqioo3Daw==
=cdvX
=====END PGP SIGNATURE=====
------------------------------
From: "Trevor L. Jackson, III" <[EMAIL PROTECTED]>
Subject: Re: Random numbers from your sound card
Date: Sat, 24 Feb 2001 00:00:36 GMT
Jerry Coffin wrote:
> In article <[EMAIL PROTECTED]>, [EMAIL PROTECTED] says...
>
> [ ... ]
>
> > You can create massive quantities of unreasonably volatile data for less than
> > $100. At the pet store buy an aquarium with an over-large pump and extra air
> > stones for under $50. With this equipment you can create a high speed version of
> > the lava lamp. At the computer store buy a parallel port webcam for under $40.
> > With the extra $10 buy a bright light and shine it on the tank (you want reflection
> > of the light not transmission, so put it on the same side of the tank as the
> > camera.
>
> Note that if you add salt to the water, you get much finer bubbles.
> At least theoretically, with a high-enough resolution camera, you
> should be able to get randomness even faster this way...
I've not experimented with additives except various surfactants. All worthless. The
foam tends to get rigid and the volatility becomes hidden under that static foam.
But, as you noted, the resolution of the camera, with its attendant cost, is a limiting
factor. Given a single tank one can have many cheap, low resolution cameras as opposed
to a single, expensive high resolution camera. And when the cheap camera gets wet
(there's really no need to inquire about those particular events) one doesn't curse as
vehemently.
------------------------------
From: "Trevor L. Jackson, III" <[EMAIL PROTECTED]>
Subject: Re: Random numbers from your sound card
Date: Sat, 24 Feb 2001 00:07:36 GMT
Paul Pires wrote:
> Trevor L. Jackson, III <[EMAIL PROTECTED]> wrote in message
>news:[EMAIL PROTECTED]...
> > [EMAIL PROTECTED] wrote:
> >
> > > 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.
> >
> > You can create massive quantities of unreasonably volatile data for less than
> > $100. At the pet store buy an aquarium with an over-large pump and extra air
> > stones for under $50. With this equipment you can create a high speed version of
> > the lava lamp. At the computer store buy a parallel port webcam for under $40.
> > With the extra $10 buy a bright light and shine it on the tank (you want reflection
> > of the light not transmission, so put it on the same side of the tank as the
> > camera.
> >
> > If you have extra cash buy a mirror the size of the tank and put it opposite the
> > camera and the light. If you are rich buy two mirrors the size of the long side of
> > the tank, with which you make a hall-of-mirrors, and move the camera & light to the
> > end of the tank.
> >
> > Yes, you need to fill the tank with water and plug in the air pump.
> >
> > Operating the webcam at video speeds gives an unreasonably large volume of volatile
> > bits. Of course an adversary can chill the output with a clothes pin on the air
> > line, but for raw TRNG it works for me.
> >
> > Your Randomness May Vary. ;-)
>
> Do fish improve the output (by occulting the
> bubbles according to an incomprehensible
> rational) ?
I suspect so, but I've not measured the effect ;-).
Fish do have the effect of dramatically increasing the maintenance required because,
while feeding
is trivial, dealing with the processed food and the algae that feed on it is not
trivial. Water
and a little bleach to keep down the algae is the best recipe I have to date.
I'd love to find a cheap method of getting video at the level of brownian motion, but
the
microscope costs are a limiting factor. One can get very volatile effects at the
boiling point of
water with ultrasonic stimulation, but either the water boils into steam and blows
away, or you
need a pressure vessel and point-wise heating, or a you have a heat exchanger. None
of those are
simple or cheap.
------------------------------
From: "Michael Scott" <[EMAIL PROTECTED]>
Subject: Re: Really big numbers in C
Date: Fri, 23 Feb 2001 18:01:38 -0600
Also
Crypto++
Cryptlib
BTW 4096 bit numbers are just big. Really big would be 1 million bits and
up.
Mike Scott
"Douglas A. Gwyn" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> Taylor Francis wrote:
> > Anyone know how to handle really bug numbers in C? I'm talking
> > 1024-4096 bit numbers...
>
> This is a FAQ (I don't know if it is answered in the sci.crypt
> FAQ periodic posting). The simple answer is, this calls for an
> implementation of multiple-precision arithmetic (modulo word size),
> and there are several available. Try a Web search for:
> bignum
> multiple precision
> GMP
> OpenSSL
> MIRACL
> and undoubtedly others you will hear about in follow-ups.
------------------------------
** 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
******************************
