Cryptography-Digest Digest #424, Volume #13 Fri, 5 Jan 01 16:13:01 EST
Contents:
Re: Comparison of ECDLP vs. DLP ("Joseph Ashwood")
Re: Simple Sublimibimbimal Exercise (Mok-Kong Shen)
Re: Key scheduling ("Joseph Ashwood")
Re: Genomes ("John Feth")
Re: Key scheduling (Simon Johnson)
Re: ____MIPS (Where is my problem?) ("Joseph Ashwood")
Re: Intel holding back because of security issues! ("Joseph Ashwood")
Rabin encryption (was Re: Quadratic Residuosity Problem) (David Hopwood)
Rabin encryption (was Re: Quadratic Residuosity Problem) (David Hopwood)
Re: NSA and Linux Security (Simon Johnson)
----------------------------------------------------------------------------
From: "Joseph Ashwood" <[EMAIL PROTECTED]>
Subject: Re: Comparison of ECDLP vs. DLP
Date: Fri, 5 Jan 2001 11:12:04 -0800
When in doubt fond someone who doesn't have a vested interest in either
side. You've heard from both Silverman and Johnson, two very good people in
their respective fields (Silverman-factoring, Johnson-ECC). I have no ax to
grind with either side.
I see no reason to debate for debate on the smaller sizes, and in all
honesty they generally don't either, they in fact agree within small bounds
(is 430 or 512 bit RSA equivalent to 112-bit ECC is a trivial matter).
However like many other people I'm sure you've noticed that the values they
give at the extreme are significantly different, in fact a factor of 10
different. The difference is in what they considered pertinent to the
relationship, Silverman considered cost, Johnson considered compute power.
For small values these are virtually identical with processing power being
the main requirement. The choice really is what areas are of importance to
you. Personally for comparing equivalent strength for key sizes, I prefer
Silverman's measure of cost to buy the compute power/memory for the job.
However when choosing key sizes I am very pessimistic about my estimates, so
for example my PGP key is 4096 bits, not because anything I send is worth
that, but because even a significant advance against the algorithms will
likely still keep me safe.
Given that you want this for a realistic comparison, I would recommend
Silverman's numbers (http://www.rsalabs.com/bulletins/bulletin13.html
section VIII), if you want to sell people on using ECC, Johnson's numbers
(http://www.certicom.com/research/download/ECCFut.zip) do make a very good
resource. The only problem is that these numbers compare RSA with ECC, and
it seems you are interested in DLP, currently DLP and factoring are
equivalent for the fastest method for both (it's the same algorithm).
Joe
"Martin Hamann" <[EMAIL PROTECTED]> wrote in message
news:932sm7$qbq$[EMAIL PROTECTED]...
> I'm looking for at comparison of the stregths in a Elliptic Curve DLP and
a
> DLP in Zp*. I have seen a table stating which keysizes roughly offer the
> same strength, for example 2^106 in ECDLP roughly equals 2^512 in "normal"
> DLP. I believe it is taken directly from a book or article, which I cannot
> locate.
>
> I need it for at discussion of why ECDSA is 'better' than DSA.
>
> Can you point me to some references to this ? Any comments are appreciated
> :)
>
> Thanks and regards,
> Martin Hamann, Student,
> Technical University of Denmark.
> http://www.dtu.dk
>
>
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Simple Sublimibimbimal Exercise
Date: Fri, 05 Jan 2001 20:34:31 +0100
wtshaw wrote:
>
> Mok-Kong Shen<[EMAIL PROTECTED]> wrote:
>
> > The problem with stego with the aid of computer is that
> > it can just as well be detected with the aid of the
> > computer (in systematic ways), I believe.
>
> Stego can be much more varied than normal forms of crupto, even to hiding
> otherwise encrypted stuff. There are no systematic ways to cover all
> possible forms of crypto, just a small subset of them. Different forms of
> hiding content and meaning can be added at the drop of a hat; dropping
> hats would be hard to make a criminal offense. The wetdream of many
> control freaks is that crypto in general is a containable process.
>
> With the immediate example detection can be done in several ways. Three
> are: manipulating the color table, working with brightness and contrast,
> and repainting. The use of nicked letters, as in 217Skin.GIF, caters to
> repainting.
It would in general depend on how much effort one is willing
to put in it, I believe. If work somehow comparable to that of
artists is done, then the detection could indeed be difficult.
Otherwise, if one just employs some more or less 'mechanical'
way to do stego without much thought, I conjecture that
detection is fairly likely, since the file transmitted could
be analysed in detail for presence of certain 'irregularities'.
In fact, it seems that researchers in watermarking still
have lots of open problems.
> > .....There are situations where
> > one needs to hide the presence of secret. And that need
> > may get bigger with the creation of new laws in certain
> > democratic countries.
> >
> And, there is no humane way to sucessfully force all secrets to be told.
Humane could be a relative concept. I happened to read
recently in a newspaper article that somewhere one person, who
was presumably guilty but whose crime couldn't be proved by
the authority, was (legally) kept in prison for investigation
purposes for four years. Isn't that a strong enough 'force'
for plenty of people?
M. K. Shen
------------------------------
From: "Joseph Ashwood" <[EMAIL PROTECTED]>
Subject: Re: Key scheduling
Date: Fri, 5 Jan 2001 11:29:18 -0800
[comments after text]
"Doug Kuhlman" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> Certain ciphers (e.g. IDEA, DES) -- usually older ones -- have a very
> simple key scheduling. Other, later ciphers (Twofish, AES) have much
> more complicated key scheduling algorithms (often almost as complex as
> the cipher itself).
>
> Why? What attacks (if any) are there against the simpler key scheduling
> algorithms? Is there a gain? If so, what?
They do it because most attacks boil down to finding a few of the later
round keys, and computing the earlier ones. By using a solidly built key
schedule, one that cannot be computed in reverse, they make this type of
attack instantly more difficult. Additional reasons are that if you have a
sophisticated key schedule, you can simplify the cipher itself, and make the
cipher faster when the key schedule is amortized across the entire
ciphertext. So speed and security in one, once you know that it seems quite
obvious to follow suit.
Joe
------------------------------
From: "John Feth" <[EMAIL PROTECTED]>
Subject: Re: Genomes
Date: 5 Jan 2001 18:54:46 GMT
I looked at about 700,000 bases (base here relates to a chemical
constitution of the components A, C, G, T, not numerical) on a gene and
found the A:C:G:T ratios to be very close to 3:2:2:3. An Allan deviation
analysis shows that the order looks like noise in strings of up to about
1,000 bases but carries information in strings from 1,000 to 10,000 bases
long. I believe an A always occurs with a T so steganography in DNA might
be a little different than in photos or music.
John Feth
Mok-Kong Shen <[EMAIL PROTECTED]> wrote in article
<[EMAIL PROTECTED]>...
>
> Does anyone happen to know the statistical properties of the
> genome sequences in general? Are they sufficiently 'random'?
>
> BTW, since the code is base 4, one can use the same to readily
> transcribe any given binary sequences. This could have some
> steganographical benefit, I suppose. For a paragraph that is
> gibberish easily gives rise to suspicion of crypto, while the
> same in the alphabet AGCT is presumably difficult to
> distinguish from the result of a genetic research, if
> appropriately enveloped. One could perhaps also hide information
> in genuine genome sequences through modifications analogous to
> what is done with graphical files.
>
> M. K. Shen
>
------------------------------
From: Simon Johnson <[EMAIL PROTECTED]>
Subject: Re: Key scheduling
Date: Fri, 05 Jan 2001 19:50:10 GMT
In article <934pid$sta$[EMAIL PROTECTED]>,
[EMAIL PROTECTED] (David Wagner) wrote:
> Doug Kuhlman wrote:
> >Why? What attacks (if any) are there against the simpler key
scheduling
> >algorithms?
>
> Weak keys and equivalent keys are obviously something worth avoiding.
>
> More subtly, the hashing modes of operation (Davies-Meyer, etc.) for
> block ciphers often stresses the key schedules very hard, and some
> simple key schedules may not suffice for this application.
>
> There are also related-key attacks to worry about, although I predict
> that they are probably not a major concern in most practical uses.
>
> For some discussion on attacks on too-simple key schedules, see
>
> ``Key-schedule cryptanalysis of IDEA, G-DES, GOST, SAFER, and triple-
DES.''
> John Kelsey, Bruce Schneier, and David Wagner. CRYPTO '96.
> http://www.cs.berkeley.edu/~daw/papers/keysched-crypto96.ps
>
> ``Related-Key Cryptanalysis of 3-WAY, Biham-DES, CAST, DES-X, NewDES,
> RC2, and TEA.'' John Kelsey, Bruce Schneier, and David Wagner.
> ICICS '97. http://www.cs.berkeley.edu/~daw/papers/keysched-
icics97.ps
>
Somewhat off topic, but related is DES. Why didn't people redesign the
DES key-shedule to deal with 128-bit keys (where complying to a
standard was not essiential)?
That's what i don't get about triple DES, why? Surely a faster
algorithm than tripple DES would be the following:
1. Design a new key-shedule to take 128-bit keys.
2. Increase the number of rounds to the 19 (this prevents Differential
cryptanalysis from being possible according to AC2)
If your gonna use tripple DES anyway, you probably wont care about the
addition of 3 rounds to the cipher.
Simon.
--
Hi, i'm the signuture virus,
help me spread by copying me into Signiture File
Sent via Deja.com
http://www.deja.com/
------------------------------
From: "Joseph Ashwood" <[EMAIL PROTECTED]>
Subject: Re: ____MIPS (Where is my problem?)
Date: Fri, 5 Jan 2001 11:59:27 -0800
Crossposted-To: comp.benchmarks
"kctang" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> The reason that I keep on asking is, in my opinion, rather obvious!
And the reason we don't respond is equally obvious. MIPS is a term from
benchmarking, not from crypto.
>Many papers, journal papers, newspapers or the likes, not long ago,
> simply used MIPS.
And if you look at recent papers with more recent results, results which can
drastically change the security offered, you will find them in lo and
behold, useful numbers, not MIPS.
> What I want is to do is to relate their information to my own
> PII-400Mhz PC?
You might try relating the newer information to your PC. Especially since
you are looking at public key cryptography, where the processor is rarely
the bottleneck.
>Here is the problem: In a Certicom paper dated 1998 [snip useless
information]
Yep, looking at a paper regarding computing power from 2 years ago and
trying to align them with today is extremely difficult
>So how can I relate those MIPS years with the computing power of my
>Pentium II-400Mhz despite that I don't have 10^10 number of such
> PCs?
Look at it this way. even if your computer was capable of 1BIPS (which it
isn't, not even close), that's still 10^7 years. Do you really think you
need to be concerned?
Joe
------------------------------
From: "Joseph Ashwood" <[EMAIL PROTECTED]>
Subject: Re: Intel holding back because of security issues!
Date: Fri, 5 Jan 2001 12:01:54 -0800
Crossposted-To: comp.sys.laptops
"Scott Craver" <[EMAIL PROTECTED]> wrote in message
news:9339sj$hvt$[EMAIL PROTECTED]...
> >>> ( IA-64 ) processor because it can crack 128-bit SSL encryption in
less a day
> Right. I wonder what smaller number his spell-checker replaced
> with "128"?
I vote for 12.8, or maybe it's 1.28. Realistically the number should be
around 40 bits. A couple years ago we could do a reasonable job against
40-bit crypto in a weekend, so a 2 fold improvement for what seems more and
more to be just a pilot program for something that may be very powerful in
the future seems reasonable.
Joe
------------------------------
Date: Fri, 05 Jan 2001 20:30:57 +0000
From: David Hopwood <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Subject: Rabin encryption (was Re: Quadratic Residuosity Problem)
=====BEGIN PGP SIGNED MESSAGE=====
Medvedev Michael wrote:
> I would like to find out, is it possible to decrease redundancy in Rabin
> public - key encryption?
>
> If somebody is new in this field, I'll try to expain the problem:
>
> If Allice wants to encode the message X, she computes Y = X^2 mod n (n = p *
> q, where p, q - are prime numbers) and sends Y to Bob. Bob knows n, p, q. He
> tries to find the square roots of Y. As n is a product of two primes, he
> evaluates four square roots: x1, x2, x3, x4.
Two of the roots are < n/2, and two are > n/2 (note that n is odd), because
(n-x)^2 = x^2 (mod n). So two roots can immediately be eliminated by choosing
an encoding such that X < n/2.
> But how to recognize, what xi was encoded? As a rule, if Alice wants to
> encrypt message M, she duplicates the message and encrypts X = MM. So Bob
> must finds out, which xi is duplicated.
One way of distinguishing between the two remaining roots is to use something
like OAEP to encode the message, then on decryption, choose the square root
for which the OAEP decoding succeeds. This has a small probability of failure
when both roots satisfy the redundancy criterion (as does the "X = MM" method),
but this is extremely unlikely to happen in practice.
In fact OAEP+ has some advantages over OAEP (it is secure under weaker
assumptions); OAEP+ is described in
Victor Shoup,
"OAEP Reconsidered,"
http://eprint.iacr.org/2000/060
Assuming the intractibility of factoring, this should be provably secure in
the random oracle model against adaptive chosen ciphertext attacks, which
plain Rabin encryption is not.
> Is it possible not to duplicate M, but to add 1 bit or 2 bits or some bits
> of information to the message (the MINIMUM number of information)?
Using OAEP or OAEP+ as suggested above will add about 2k bits to the message,
where k is the output length of a hash function. The theoretical minimum
(just using the standard Rabin trapdoor function, and assuming the message
is already compressed) would be about k' bits of redundancy to get a failure
probability of 2^-k'. However, that does not take into account the fact that
random padding must be included for security, so the secure minimum expansion
would be something like 2k' bits for k' ~= 128, say (i.e. OAEP[+] is not very
far from optimal).
Bear in mind that there is no standard for encryption using Rabin, unlike
PKCS #1 v2 for RSA, DLIES from IEEE P1363a for Diffie-Hellman-based
encryption, etc., so you will have nothing to compare your implementation
with, and the precise variant you use will not have been analysed by anyone
else (it is quite easy to get the details wrong even when using a "provably
secure" technique). Was there any specific reason you wanted to use Rabin?
For most applications, I'd recommend RSA or DLIES instead.
- --
David Hopwood <[EMAIL PROTECTED]>
Home page & PGP public key: http://www.users.zetnet.co.uk/hopwood/
RSA 2048-bit; fingerprint 71 8E A6 23 0E D3 4C E5 0F 69 8C D4 FA 66 15 01
Nothing in this message is intended to be legally binding. If I revoke a
public key but refuse to specify why, it is because the private key has been
seized under the Regulation of Investigatory Powers Act; see www.fipr.org/rip
=====BEGIN PGP SIGNATURE=====
Version: 2.6.3i
Charset: noconv
iQEVAwUBOlVdaDkCAxeYt5gVAQH5Egf9FJArjvnXX8EmkYrfjK+q4SKCQIdRzqGG
64MUr5H4wGRmfQPihsF6aIk8yCTFkMpoya68sh1RDMUwvKZin/OySmlim+5c+M5N
6VlwdcMfZLS1vOW3gEDq5coHc9g2FmncnC2UF5gEIgOcE3cfpn2/sCNi08dS8ZX7
c0vOGnUcjyrnOGtwlHlbcMgiaBvZjhckhv1rsJDqP44S++kek6llZPVJtQYHYKkc
uCYFAhOL4S1JPz2vDBZT+npCU+qfmiH7mDqXFEsn0pj0YFns9WD6XQUssbMLKriD
cBjhGEh4kQjc+wd79r2dEtann5SQs5UXfdzGCfqjK5NPSnpK5vzbDw==
=cZ0s
=====END PGP SIGNATURE=====
------------------------------
Date: Fri, 05 Jan 2001 20:31:28 +0000
From: David Hopwood <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Subject: Rabin encryption (was Re: Quadratic Residuosity Problem)
=====BEGIN PGP SIGNED MESSAGE=====
Mok-Kong Shen wrote:
> Medvedev Michael wrote:
[snip]
> > Is it possible not to duplicate M, but to add 1 bit or 2 bits or some
> > bits of information to the message (the MINIMUM number of information)?
>
> The four values have an order as binary numbers. If one
> appends 2 bits, that would resolve the ambiguity. Or
> am I missing something?
This won't work, because the encryptor only knows two of the roots
(X and n-X), not four.
- --
David Hopwood <[EMAIL PROTECTED]>
Home page & PGP public key: http://www.users.zetnet.co.uk/hopwood/
RSA 2048-bit; fingerprint 71 8E A6 23 0E D3 4C E5 0F 69 8C D4 FA 66 15 01
Nothing in this message is intended to be legally binding. If I revoke a
public key but refuse to specify why, it is because the private key has been
seized under the Regulation of Investigatory Powers Act; see www.fipr.org/rip
=====BEGIN PGP SIGNATURE=====
Version: 2.6.3i
Charset: noconv
iQEVAwUBOlVhADkCAxeYt5gVAQES3AgAvWjk0T7YHWBxwr7qd+BKIKpivp4miJV4
0DSDF1XYUT9RSKOQPfhv/yLJmw3e7U9RgZqEt18Y3eW5ExZfuBZvE0n6Xpp0Imzo
0wrqxCf0vyvoaBQY1VDV8N42WCNUcczLkB9NgPyCM4uBE5DouLnNwUCVqi1VQQUU
FgunMjFNisJOOrXNSCqNKzatwovz7/7aiWrYeXqhXy6yWguJgpZQXa7R5s+rGN8a
A/8gp57ViQMdWhm9qBl9vB208ObEJiy5qUCAzR1prmQomwVLFRCIns/aGD5NBPKY
LJiFIRfm9qpv0dN4KajE9MTtoREWSwVwmWY5XWARHRJtb7UzA3Yc3A==
=t6uT
=====END PGP SIGNATURE=====
------------------------------
From: Simon Johnson <[EMAIL PROTECTED]>
Subject: Re: NSA and Linux Security
Date: Fri, 05 Jan 2001 20:33:30 GMT
In article <[EMAIL PROTECTED]>,
Stephan Eisvogel <[EMAIL PROTECTED]>
wrote:
> David Bernier wrote:
> > NSA has recently announced that it is working on improving
> > the security of Linux...
>
> Yes. Some observations:
>
> 1. "We give back to you guys" raised a lot of people's attitude over
the NSA as
> a whole, away from the big-bad-guys theme. In GPL you are what you
give.
> 2. They had a newline buffer-overflow problem but there has already
been a fix
> announced at http://marc.theaimsgroup.com/?
l=selinux&m=97847509307650&w=2
> Of course this was found very early because the source code came
from such
> a promiment place.
> 3. While reading through
http://www.nsa.gov/selinux/example_config.html I keep
> thinking about NSA's real world structure (air-gaps, need-to-know,
domains)
> having been imported into the Linux kernel.
> 4. Selinux is the best attempt so far to rid Un*x-like systems from
the big
> drawback of having almighty powers as 'root'. There are other
approaches
> like LIDS, sudo or the evil suid-bits, but they all do not
separate policy
> from enforcement (i.e. once God, laws no longer apply to you).
FreeBSD
> tries to solve this on their own with the jail(2) system-call.
> 5. Building on 4., once this is stable and included in the main tree
one
> could envision a compromised system (e.g. through ftpd) that keeps
running
> in safety because security policies protect the remaining system
from
> tampering and snooping.
>
> --
> Stephan Eisvogel, Hartmannstrasse 129 App.119, 91058 Erlangen DE
> mailto:[EMAIL PROTECTED] tel ++49 (0)9131 127876
> HAWO-Network Administration & Security
>
Prehaps the NSA have been forced to shift there policy somewhat due to
the possibilitity of having their funding cut. In the times of the cold
war, the NSA needed to be a secret agency which did secret things.
Since this role doesn't exist in the same capacity as before, they must
be forced to do other work.
Personally, i believe the Americans have nothing to fear of their
agency. Infact, there probably quite a productive group.... They'll
probably want to insure that American secrets remain secret so they
won't build trapdoors into their algorithms etc..... The real worry is
what they do abroad. I remember once reading that the NSA broke the
encryption of between an candian exporter of grain and some EU
distrubuter. The NSA then promptly sold this information to an American
supplier and the American comapny successfully undercut the deal.
--
Hi, i'm the signuture virus,
help me spread by copying me into Signiture File
Sent via Deja.com
http://www.deja.com/
------------------------------
** 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
******************************
