Cryptography-Digest Digest #178, Volume #9 Wed, 3 Mar 99 09:13:02 EST
Contents:
Re: The strength of RSA (ring) vs DH/DSA (field) (Was: DSS Keys) ("Thomas J.
Boschloo")
Re: KL-7 Cipher machine (Frode Weierud)
Factorisation of Polynomials with Matrixes as Coefficients (Bo Lin)
More BBC crypto inaccuracy (WAS Re: RSA Cryptography Crack) (Paul Crowley)
Re: Snake Oil (from the Feb 99 Crypto-Gram) (Stefek Zaba)
Re: New Encryption (I would like some analysis) ([EMAIL PROTECTED])
Re: ScramDisk Website?? ([EMAIL PROTECTED])
Scramdisk - paranoia ([EMAIL PROTECTED])
Re: Factorisation of Polynomials with Matrixes as Coefficients (Peter L. Montgomery)
RSA Cryptography Today FAQ (1/1) ([EMAIL PROTECTED])
Re: public read, secure write? (Patrick Juola)
The AES proposal DFC and Provable Security (Vincent Rijmen)
----------------------------------------------------------------------------
From: "Thomas J. Boschloo" <[EMAIL PROTECTED]>
Crossposted-To: alt.security.pgp
Subject: Re: The strength of RSA (ring) vs DH/DSA (field) (Was: DSS Keys)
Date: Wed, 03 Mar 1999 10:08:10 +0100
"Thomas J. Boschloo" wrote:
> [snip]
> > > Here is his post:
> [snip]
> > > > A theoretical result is, that discrete logarithms over a finite field are
> > > > at most as difficult as the factorisation of the predecessor of the
> > > > characteristic of the field which is always prime.
> > > > OTOH discrete logarithms over a finite ring are at most as difficult as the
> > > > factorisation of the ring characteristic itself which is composite is this
> > > > case.
> > > > Several algorithms are knows to solve the problems. But it's unknown what
> > > > algorithms are known to the secret services. The public knownlegde is
> > > > documented in the standard P1363 of the IEEE. Appedix A says:
> > > >
> > > > Ring Field
> > > > -----+---- -----+----
> > > > 512 | 63 |
> > > > 786 | 76 |
> > > > 1024 | 86 1024 | 56
> > > > 2048 | 117 2048 | 112
> > > > 3072 | 139 3072 | 128
> > > > 4096 | 157 4096 | 168
> >
> > Where is this table from? 1024-bit DSA is thought to have an approx. strength
> > of a 2^80 symmetric cipher! Nowhere near 56 bits!
>
> _From IEEE P1363 Appendix A, I hope! I haven't gone throught the trouble
> to subscribing to their mailing list at
> http://grouper.ieee.org/groups/1363/draft.html. But Lutz seemed to know
> what he was talking about. At least he knew of the existance of the
> document?
>
> Forgive me for crossposting, but I just wanted to be sure ;)
Well, since Sam seemed to get a little fed up on the whole subject, I
decided to subscribe to their mailing list myself. I found the current
draft very interesting en surprisingly readable for someone like me.
This is what the draft (version 8) really said in Appendix A (note: DL
means Discrete Logarithm, like in DH/DSS):
***
A.3.10 Parameters for Common Key Sizes
When selecting domain parameters for DL-based cryptography over binary
fields, it is necessary to begin by choosing the following:
— The degree m of the field (so that the field has 2^m elements)
— The prime number r which is to serve as the order of the base point
These two numbers are related by the condition that r must be a
primitive divisor of 2^m – 1 (see Annex A.3.9). Moreover, it is a common
practice to choose the two numbers to provide comparable levels of
security. (See Annex D.4.1.4, Note 1.) Each parameter depends on the
size of the symmetric keys which the DL system is being used to protect.
The following table lists several common symmetric key lengths. For each
length is given a set of parameters of m and r which can be used in
conjunction with symmetric keys of that length.
Key Size m r
40 189 207617485544258392970753527
56 384 442499826945303593556473164314770689
64 506 2822551529460330847604262086149015242689
80 1024 7455602825647884208337395736200454918783366342657
112 2068 2845635541041154750961337415015805123165674305234451316-
1858038422883778013.
128 2880 1919487818858585561290806193694428146403929496534649176-
7953330250249208842371201
***
So Lutz Donnerhacke was indeed on a wind up :-) [Hope he reads this
post]
1024 DSS is about 80 bit symmetric (if I understand the text correctly).
Or maybe there was an error in an earlier draft...
For eliptic curve it had the following estimated strengths (Appendix D):
Size of generator Processing Time
(Bits) (MIPS-Years)
128 4.0x10^5
172 3x10^12
234 3x10^21
314 2x10^33
A minimum length of 161 is suggested by the draft for EC (1024 bits for
DL and 1024 bit for IF).
For IF (Integer Factorization, like RSA) it had the following
interesting table:
Modulus Processing Time Memory Requirements
(Bits) (MIPS-Years) Sieving process Linear Algebra
512 4.0x10^5 130 Kb 20 Mb
1024 3x10^12 300 Mb 100 Tb
2048 3x10^21 8000 Tb 3000 Tb
The sieving process can be done on multiple computers in parallel, the
linear deduction must be done on a single processor.
Hope this was informative (and I made no typo's).
Regards,
Thomas
--
Seven of Nine: "You will be assimilated"
PGP key: http://x13.dejanews.com/getdoc.xp?AN=406702465
Post your keys to news:alt.security.keydist
------------------------------
From: [EMAIL PROTECTED] (Frode Weierud)
Subject: Re: KL-7 Cipher machine
Date: 3 Mar 1999 09:52:42 GMT
Reply-To: [EMAIL PROTECTED]
[EMAIL PROTECTED] (John Savard) writes:
>Actually, there's a KL-7 on display at an Air Force museum -
>http://www.afca.scott.af.mil/pa/public/vcphoto5.htm
>the photo is clearer than the one at the Haida web site, but there is
>no labelling on the knob.
The labelling on this knob which controls a four-way switch is:
O P E D
Which I suppose means Off, Plaintext, Encipher, Decipher.
Frode
--
Frode Weierud Phone : +41 22 7674794
CERN, SL, CH-1211 Geneva 23, Fax : +41 22 7679185
Switzerland E-mail : [EMAIL PROTECTED]
WWW : wwwcn.cern.ch/~frode
------------------------------
From: Bo Lin <[EMAIL PROTECTED]>
Subject: Factorisation of Polynomials with Matrixes as Coefficients
Date: Wed, 03 Mar 1999 10:01:34 +0000
As we know that integer factorisation plays an important role in public
key cryptography such as RSA security highly relies on the difficulty of
integer factorisation. Although there is no efficient algorithm for
integer factorisation, there are many efficient algorithms for
polynomial factorisation. For example, polynomials with rational
coeffients can be factored by the famous LLL algorithm and polynomials
with GF(q) coefficients can be factored by Berlekamp method. Some people
suggested another prolem to me that is the factorisation of polynomials
with matrixes as coefficients in which each entry of a matrix is either
0 or 1, i.e. an element of GF(2). They claimed that the problem could be
more difficult than integer factorisation because it appears that there
is no straightforward method to do or even define division (or
inversion) over matrixes no matter of the poor record of other
polynomials in factorisation. An inversion is inevitable in doing
factorisation.
I'm not an expert in factorisation and I have no idea about their
claims. I should be very grateful if anybody in this group can help or
give any commets.
Regards,
Bo Lin
Motorola
------------------------------
From: Paul Crowley <[EMAIL PROTECTED]>
Subject: More BBC crypto inaccuracy (WAS Re: RSA Cryptography Crack)
Date: 3 Mar 1999 09:43:24 -0000
[EMAIL PROTECTED] (Thomas Pornin) writes:
> According to Jon <[EMAIL PROTECTED]>:
> > David Levy, head of Tiger Security Systems is quoted as saying:
> > "The RSA encryption algorithm was supposed to be uncrackable until two
> > guys in Cambridge University did it. Nothing is impossible."
>
> If this guy really exists, he is a complete lamer. RSA has not been
> publicly broken for the moment.
When the BBC got all breathless about UBE98, I sent some flames their
way advising them to consult someone who knew what they were talking
about before serving that sort of nonsense. The guy responsible
responded that he had already consulted "experts". Now we know who
they were.
--
__
\/ o\ [EMAIL PROTECTED] http://www.hedonism.demon.co.uk/paul/ \ /
/\__/ Paul Crowley Upgrade your legacy NT machines to Linux /~\
------------------------------
From: [EMAIL PROTECTED] (Stefek Zaba)
Subject: Re: Snake Oil (from the Feb 99 Crypto-Gram)
Date: Wed, 3 Mar 1999 11:29:06 GMT
In sci.crypt, Jim Dunnett ([EMAIL PROTECTED]) wrote:
> Our police were complaining last week that a reactivated
> peadophile group was using 'military grade code (!)',
> by which I presume they mean PGP.
> From which it is reasonable to assume they haven't access
> to cryptanalysis, or if they have the cryptanalysis is
> ineffective.
Brute-force cryptanalysis of a single PGP message or file-on-disk (pgp -c)
*is* ineffective. That's the *point* of using decent-length keys (1024 bits
RSA, 128 bits for IDEA).
However, other routes in, based on the weaknesses of the computing platform
the system is running on as well as the non-strong choice of passphrase by
most lusers, *are* available. Depending on which bit of the investigative
agencies you're thinking about, knowledge of and access to such techniques
will vary from totally absent to routine. "Encryption is dangerous" messages
will reach a feverpitch in the UK in the coming days and weeks as the
much-delayed Electronic Commerce bill, which links digital signature
recognition to escrow of encryption keys via voluntary [sic] licensing
arrangements, makes its way throuhgh the drafting process and comes out to
public consultation. The story to watch for is the one which links crypto
simultaneously to Semtex, peadophillia, cocaine, *and* a Premier League
football manager :-)
Cheers, Stefek
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: New Encryption (I would like some analysis)
Date: Wed, 03 Mar 1999 12:16:51 GMT
> If you break the problem into two parts, actual encryption and runtine key
> generation, this allows you to introduce options into how to the the 8182
> bytes, from only a few bytes, pRNG series, to the full amount, with lots
> of compromise options in between.
>
Well, no. My previous argument still holds valid. If you use a home picture
(scanned) or your own voice clip, you can use that as a key. No one else will
have the same, and the chances make it improbable.
>
> Simple XOR is not much of an encryption algorithm by itself, passing off
> strength to very long keys.
That's the point. It uses the values and position of the key elements in the
cipher. I was thinking of actually doing an ADLER of the values to find S and
L but that makes it slower (probably more secure).
As an interesting point, how would go about cracking this algorithm? Say if
you don't know the plaintext, and test case 2: make a key from both
plain/cipher text.
Thanks,
Tom
============= Posted via Deja News, The Discussion Network ============
http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: ScramDisk Website??
Date: Wed, 03 Mar 1999 12:45:55 GMT
New URL: http://home.clara.net/scramdisk/
Dr@usio.
In article <01be63a5$b6886ba0$df7ffcd0@default>,
"T & C Spargo" <[EMAIL PROTECTED]> wrote:
> Do I have the incorrect address, or, is the site down??
>
> Please let me know, as this product is one of the best!!!
>
>
============= Posted via Deja News, The Discussion Network ============
http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own
------------------------------
From: [EMAIL PROTECTED]
Subject: Scramdisk - paranoia
Date: Wed, 03 Mar 1999 12:04:25 GMT
>From my experience of Scramdisk it appears to be a very well written program.
However, here is an interesting little thought to get the paranoia going. If
the government were concerned about encryption then what would be the best
way to gain access to protected data? One way would be to introduce a piece
of free software to the general public which appears to offer strong
protection but also include a back door which would allow them access to any
encypted file - perhaps by including the password at a specific point within
the file. I'm not suggesting scramdisk is such a program but it's a definite
possibility. So far I have not seen a posting from anyone claiming to have
checked out the source code. Also, why has the source code for the latest
release not be published? It was claimed that they were interim releases but
I don't see why it would be a problem zipping up the source code anyway.
You have to agree that it's worth some thought.
John
============= Posted via Deja News, The Discussion Network ============
http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own
------------------------------
From: [EMAIL PROTECTED] (Peter L. Montgomery)
Subject: Re: Factorisation of Polynomials with Matrixes as Coefficients
Date: Wed, 3 Mar 1999 13:23:32 GMT
Since matrix multiplication is non-commutative, we need
to be very careful when we define polynomial arithmetic. For example, if
A1*X + A0 and B1*X + B0, then their product is
A1*X*B1*X + A1*X*B0 + A0*B1*X + A0*B0
We can multiply A0*B1 and A0*B0, but cannot simplify the first
two terms A1*X*B1*X and A1*X*B0 unless we assume that the
variable X commutes with all matrices. The number of terms
in the product grows very fast.
If you do specify that X commutes with all matrices,
you can simplify the products. But we lose many familiar
polynomial properties, such as the degree of a product
being the sum of the degrees (unless one input is the zero polynomial).
For example, if M^2 = 0, then
(M*X + I)*(-M*X + I) = -M*X*M*X + I = I (I = identity)
so we can multiply any other factorization by (M*X + I)*(-M*X + I),
In article <[EMAIL PROTECTED]>
Bo Lin <[EMAIL PROTECTED]> writes:
>As we know that integer factorisation plays an important role in public
>key cryptography such as RSA security highly relies on the difficulty of
>integer factorisation. Although there is no efficient algorithm for
>integer factorisation, there are many efficient algorithms for
>polynomial factorisation. For example, polynomials with rational
>coeffients can be factored by the famous LLL algorithm and polynomials
>with GF(q) coefficients can be factored by Berlekamp method. Some people
>suggested another prolem to me that is the factorisation of polynomials
>with matrixes as coefficients in which each entry of a matrix is either
>0 or 1, i.e. an element of GF(2). They claimed that the problem could be
>more difficult than integer factorisation because it appears that there
>is no straightforward method to do or even define division (or
>inversion) over matrixes no matter of the poor record of other
>polynomials in factorisation. An inversion is inevitable in doing
>factorisation.
>
--
[EMAIL PROTECTED] Home: San Rafael, California
Microsoft Research and CWI
------------------------------
From: [EMAIL PROTECTED]
Crossposted-To:
talk.politics.crypto,alt.security.ripem,sci.answers,talk.answers,alt.answers,news.answers
Subject: RSA Cryptography Today FAQ (1/1)
Date: 3 Mar 1999 13:55:32 GMT
Reply-To: [EMAIL PROTECTED]
Archive-name: cryptography-faq/rsa/part1
Last-modified: 1997/05/21
An old version of the RSA Labs' publication "Answers to Frequently Asked
Questions about Today's Cryptography" used to be posted here until May
1997. These postings were not sponsored or updated by RSA Labs, and
for some time we were unable to stop them. While we hope the information
in our FAQ is useful, the version that was being posted here was quite
outdated. The latest version of the FAQ is more complete and up-to-date.
Unfortunately, our FAQ is no longer available in ASCII due to its
mathematical content. Please visit our website at
http://www.rsa.com/rsalabs/ to view the new version of the FAQ with your
browser or download it in the Adobe Acrobat (.pdf) format.
RSA Labs FAQ Editor
[EMAIL PROTECTED]
------------------------------
From: [EMAIL PROTECTED] (Patrick Juola)
Subject: Re: public read, secure write?
Date: 3 Mar 1999 08:59:00 -0500
In article <7bg8lq$ebb$[EMAIL PROTECTED]>,
Florian Erhard <[EMAIL PROTECTED]> wrote:
>Given is the following situation: There's a set of data,
>saved in a file, which should be protected under following conditions:
>- only one person, the owner of the set, should be able to modify the
> data.
> (Modifications by everyone else should be noticeable, but don't have
> to be prevented.)
>- the information about who is the owner has to be stored with the data.
>- everyone should be able to read the data.
>- the bad guys have read and write access to the stored data.
>
>Is there a possibility to realise this? The system will have access
>to trusted public keys for everyone and I want to avoid that the
>system has to use a own secret key. Attackers will have access
>to the system source code.
Sounds like an ideal application for an appended signature. Owner
writes the file, owner *signs* the file, and places the file+signature
together in storage.
-kitten
------------------------------
From: Vincent Rijmen <[EMAIL PROTECTED]>
Subject: The AES proposal DFC and Provable Security
Date: Wed, 03 Mar 1999 15:03:25 +0100
During the last months, there has been several postings
in this news group about the AES proposal DFC and its
provable security by means of the so-called decorrelation
theory.
A careful analysis of Vaudenay's results on decorrelation
theory shows that block ciphers that are
decorrelated with order d (where d is a parameter),
are provable secure against the following attacks:
- If d >= 2, the basic differential attack, where an attacker is
restricted to
choose the values in the differentials before the attack.
- If d >= 2, the basic linear attack.
- For any value of d, all attacks using at most d-1 chosen and/or known
plaintexts.
Note that DFC has d = 2.
Contrary to what some people may believe, it cannot
be concluded from these results that DFC
is secure against state-of-the-art
applied cryptography. This will be explained in
"On the Decorrelated Fast Cipher (DFC) and its theory,"
by Lars R. Knudsen and Vincent S.H. Rijmen
to be presented at the Fast Software Workshop '99,
March 24-26, in Rome. We also present a differential
attack that breaks DFC if it is reduced to six rounds.
See you in Rome !
Vincent
--
# Vincent Rijmen |
# | Kick the world,
# | Break your foot.
# [EMAIL PROTECTED] |
------------------------------
** 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
******************************
