Cryptography-Digest Digest #942, Volume #12 Tue, 17 Oct 00 06:13:01 EDT
Contents:
Re: On block encryption processing with intermediate permutations (Mok-Kong Shen)
Re: MS's fast modular exponentiation claims II ("John A. Malley")
Re: DNA encoding (Richard Heathfield)
Re: Algorithm Performance (Richard Heathfield)
Re: pseudo random test ("Joseph Ashwood")
Works the md5 hash also for large datafiles (4GB) ? ([EMAIL PROTECTED])
Re: Algorithm Performance (Wei Dai)
Re: DNA encoding ([EMAIL PROTECTED])
Re: MS's fast modular exponentiation claims II (Wei Dai)
Re: Simple Intro Encryption Info Wanted (Andre van Straaten)
Re: Rijndael implementations (Daniel James)
Re: algo to generate permutations ("Tim Tyler")
Re: Works the md5 hash also for large datafiles (4GB) ? (Runu Knips)
x509 ("Antonio Merlo")
Re: What is meant by non-Linear... ("Tim Tyler")
useful literature? ("Florian Peterl")
Re: Counting one bits is used how? ("Tim Tyler")
Re: pseudo random test ("Tim Tyler")
----------------------------------------------------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: On block encryption processing with intermediate permutations
Date: Tue, 17 Oct 2000 07:54:46 +0200
David Hopwood wrote:
>
> Mok-Kong Shen wrote:
> > David Hopwood wrote:
> > > Mok-Kong Shen wrote:
> > > > Now Bryan Olson claimed to have found an attack and
> > > > subsequently he said that under a certain condition
> > > > his attack doesn't work. So I modified my scheme to
> > > > make it immune to his attack.
> > >
> > > No you didn't. It's clear that the attack still applies, although
> > > it is more difficult because the attacker would have to break twice
> > > as many rounds of the cipher as in the original case. Under
> > > reasonable assumptions, it would still be easier than breaking the
> > > cipher in a standard mode such as CBC, though.
> > >
> > > The point is that you should be trying to extend the attack
> > > yourself, not making a minor change and relying on others to
> > > cryptanalyse it. You won't learn anything that way.
> >
> > Can I assume that you have the intention to discuss with
> > me on an attack very similar to that of Bryan Olson?
>
> Bryan (apologies to him for misspelling his name earlier) has
> already covered this in great detail, in the post with message ID
> <8s95ea$7eu$[EMAIL PROTECTED]>. The only thing I have to add is
> that if the permutation to be omitted was the last permutation,
> rather than in the middle, then the equations to be solved would
> involve four Feistel rounds rather than two, given the assumptions
> stated in Bryan's post. That's what I meant by breaking twice as many
> rounds of the cipher.
>
> It should also be obvious that omitting more than one of the
> permutations would not help either; the problem is that the security
> of the block cipher depends on not leaking information between rounds,
> and adding intermediate permutations breaks that requirement.
Bryan Olson has proposed to discuss a new attack invented
by him. We are currently continuing to discuss that which
in the next time would lead to some results, I expect.
M. K. Shen
------------------------------
From: "John A. Malley" <[EMAIL PROTECTED]>
Subject: Re: MS's fast modular exponentiation claims II
Date: Mon, 16 Oct 2000 22:45:15 -0700
JCA wrote:
>
> I asked a few days ago a question about some claims the MS made (at
> Crypto '95, I believe) to the effect that they possess an algorithm that outperforms
> Montgomery's techniques when doing modular exponentiation. Much to my surprise, given
> the high caliber of some of the regulars in this group, nobody has said anything
> yet.
>
> At the risk of coming across as pig-headed allow me please to
> restate my question: does anybody know if such claims have been independently
>substantiated?
> Has anybody got more information about them?
There was a Technical Report reference (URL) on the Microsoft Research
web site in 1999 that (should memory serve) described such an algorithm
- I tried to download the paper 3, 4 times but the URL never worked.
Checked again today and Microsoft Research no longer mentions the paper.
I found on Goolge, at
http://henry.ee.rochester.edu:8080/users/ee492/project/projdesc.html
in a list of projects for a EE492 at U. Rochester, in a project abstract
on Modular multiplication using the Montgomery method, this quote:
"At the ramp session of the last CRYPTO'95 Josh Benaloh announced that a
faster algorithm was developed in Microsoft, but the details were not
revealed, and the algorithm remains proprietary."
I checked Mr. Benaloh's web site at
http://www.research.microsoft.com/users/benaloh/
He doesn't list anything about it. He doesn't list any contact info
except for employment by Microsoft Research.
Hope this helps,
John A. Malley
[EMAIL PROTECTED]
------------------------------
Date: Tue, 17 Oct 2000 07:32:54 +0100
From: Richard Heathfield <[EMAIL PROTECTED]>
Subject: Re: DNA encoding
binary digit wrote:
>
> Hey, if any of you heard last year the winner of the inetl science research
> contest took a message and encoded it in DNA. When I first heard this I was
> skeptical on how she did this task. I searched around to see if theer was
> any explanatyion on how she did it and i found a video of her at the rewards
> explaining how it worked. She said she took a group of acids and made them
> reprtesent a letter of the alphabet. for ie 'ccc' = x and so on. I also
> read that she claimed her encryption to be 'unbreakable', which i giggled at
> cause if thats the way she actually did her project, how did she win the
> intel contest and how could she even claim that was unbreakable. Can anyone
> verify any of this, on how she actually encoded a message 'into' dna?
DNA tagging is a well-established technology. TTBOMKAB it is not only
perfectly possible but (relatively) easy to do what she has done (given
the right equipment and expertise, of course). If she really is claiming
to be doing encryption, whether that encryption is unbreakable is a
separate issue from the technology used for storing the ciphertext.
--
Richard Heathfield
"Usenet is a strange place." - Dennis M Ritchie, 29 July 1999.
C FAQ: http://www.eskimo.com/~scs/C-faq/top.html
66 K&R Answers: http://users.powernet.co.uk/eton/kandr2/index.html (31
to go)
------------------------------
Date: Tue, 17 Oct 2000 07:27:13 +0100
From: Richard Heathfield <[EMAIL PROTECTED]>
Subject: Re: Algorithm Performance
[Posted and mailed]
[EMAIL PROTECTED] wrote, in sci.crypt:
>
> I was curious if anyone had a quick and easy application to measure the
> speed of crypto algorithms.
>
> That way if I wanted to test Seal and RC4, or perhaps an rsa signature
> vs. a DSA signature.
>
> I would greatly appreciate any help.
>
You also asked this in comp.programming and comp.lang.c.
You will find an answer in comp.lang.c.
If you must post to more than one group, please use cross-posting rather
than posting once in each newsgroup.
But better still would be to focus your question on the most appropriate
group. In this case, even though you wanted to test C programs and even
though those programs were cryptographic in nature, the primary focus of
the question was performance measurement, which is a comp.programming
issue.
--
Richard Heathfield
"Usenet is a strange place." - Dennis M Ritchie, 29 July 1999.
C FAQ: http://www.eskimo.com/~scs/C-faq/top.html
66 K&R Answers: http://users.powernet.co.uk/eton/kandr2/index.html (31
to go)
------------------------------
From: "Joseph Ashwood" <[EMAIL PROTECTED]>
Subject: Re: pseudo random test
Date: Tue, 17 Oct 2000 00:49:01 -0500
> I took a look at what they have, unfortunately that runs
on Unix ( .tar
> ) extension.
>
> I have a Macintosh
The NIST test should be portable, it's standard C.
> What would be the most important test for an PRNG to pass.
The one it would fail. Sorry about the rather blunt answer
there, but it's true, there's no useful information to be
gleaned from knowing which tests it passes, but knowing
which ones it fails can lead you to improvements to the
PRNG.
Joe
------------------------------
From: [EMAIL PROTECTED]
Subject: Works the md5 hash also for large datafiles (4GB) ?
Date: Tue, 17 Oct 2000 07:50:09 GMT
I have to compare diskimages. To save diskspace I want to use
a hash (md5).
Work md5 for such large files?
I know I would generate a 128bit signature, what I mean is, is
the probability that two different large files have the same
signature as low as for smaller files.
In other words, is the algorthm of md5 only designed for "small"
files?
Mike
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Wei Dai <[EMAIL PROTECTED]>
Subject: Re: Algorithm Performance
Date: Tue, 17 Oct 2000 01:18:55 -0700
In article <8sg4qr$djd$[EMAIL PROTECTED]>, [EMAIL PROTECTED] says...
> I was curious if anyone had a quick and easy application to measure the
> speed of crypto algorithms.
>
> That way if I wanted to test Seal and RC4, or perhaps an rsa signature
> vs. a DSA signature.
Get Crypto++, compile it, and run "cryptest b". It will generate a
table of results for you. Or you can take a look at some existing
results at weidai.com/benchmarks.html.
--
cryptopp.com - a free C++ class library of cryptographic schemes
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: DNA encoding
Date: Tue, 17 Oct 2000 08:37:36 GMT
In article <[EMAIL PROTECTED]>,
"John A. Malley" <[EMAIL PROTECTED]> wrote:
> The young scientist is Ms.Viviana Risca. Here's the abstract for her
> work, at
>
http://www.siemens-foundation.org/science/99_abstracts/risca_vivianna_ny.htm
>
> This paper presents an implementation of steganography using DNA
> molecules.
> We first encode a plaintext message into a DNA sequence using a
> randomly
> generated single-substitution key. An oligonucleotide containing
> the encoded
> message, designated the message strand, is synthesized and mixed
> with a large
> amount of background DNA. To retrieve the message, the intended
> recipient must
> know the sequences of two primers that anneal to target regions
> present on the
> message strand. Polymerase chain reaction (PCR) and sequencing
are
> used to
> retrieve the encoded sequence, which is decoded into the original
> plaintext via the
> single substitution key. This study shows that the
> steganographically hidden
> message can only be retrieved by using the two secret primers,
> meaning that the
> only applicable cryptanalytic approach is a brute-force search
for
> the two primer
> sequences. Since each primer can have 420 different possible
> sequences, the
> amount of time required to crack DNA-based steganography is long
> enough to
> qualify the technique as essentially unbreakable.
>
> Technically she hid a substitution encrypted plaintext as a secretly
> marked ciphertext in a jumble of other ciphertexts.
There's an obvious typo in her abstract: I'm guessing that
the number of primers should be 4^20, as 20-bp primers is a
common length.
I'm not convinced that a brute-force approach with all primer
sets is the the only way to find the message, but the alternatives
I can think of are also slow, if not as slow.
Ingrid
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Wei Dai <[EMAIL PROTECTED]>
Subject: Re: MS's fast modular exponentiation claims II
Date: Tue, 17 Oct 2000 02:07:20 -0700
In article <8sgdik$kpc$[EMAIL PROTECTED]>, [EMAIL PROTECTED]
says...
> The original post mentioned that this was a presentation at the rump
> session, so it's unlikely that the table of contents would reveal it.
> The question arises because it seems that MS decided to not to publish the
> algorithm in the next series of conferences. So it's a "where is it now?"
> kind of question.
Microsoft patented the algorithm and used it in their CryptoAPI RSA
base provider. The details of the algorithm are available at
http://www.delphion.com/details?pn=US05724279__.
--
cryptopp.com - a free C++ class library of cryptographic schemes
------------------------------
From: Andre van Straaten <[EMAIL PROTECTED]>
Subject: Re: Simple Intro Encryption Info Wanted
Date: Tue, 17 Oct 2000 09:17:53 GMT
Chris Frost <[EMAIL PROTECTED]> wrote:
> I've read some about computer-targeted methods of encryption, but have only
> really dabbeled. I'd like to start learning more, starting with more
> human-targetted methods and see what is like. Anyway, to spur my interests
> a friend gave me these two messages:
> C2d73bAB11c9CA6
> 42175484c2bB 1CF6b359C
> Without any other info. I'd guess they are indead human-targeted algorthiums
> (or at least they use only letters and numbers and not all of ascii or binary,
> etc). What are some good [online] resources that I should begin reading
> to enable myself to decrypt the two snippets?
For these particular snippets without any other info, you can try the NG:
alt.witchcraft
;-)
If it has been encrypted with a One-Time-Pad in that way that each
character of your message xor'ed with a character of a key with the length
of that message gives your resulting snippet, it can mean everything as
different keys give a myriad of different possible original plaintexts.
If it's a task from your friend, maybe it's a simple rotation or
substitution. But then you must make assumptions about the plaintext.
Combine the snippets, and it might come out something useful.
But it depends on you, if you accept the solution.
Most people start with "Applied Cryptography" from Bruce Schneier.
The first pages might explain the dilemma of your task.
Somewhat more advanced, what I found interesting is the implementation of
the RC5 cipher in C++, and a brute-force program to crack a ciphertext,
knowing a small part of the plaintext.
http://students.washington.edu/zippy/ee/ee-modern_cipher/ee-modern_cipher.htm
After have done this, you might see the need for learning a lot about more
sophisticated mathematical algorithms.
Try then to analyze simple Vignere ciphers. Search for Friedman and
Kasiski.
Well, this is how I started. Cryptoanalysis is a large field and depends
on what you are intended to do, like programming computers.
Some people of this NG have very good and comprehensive Web sites to start
with.
Their names are:
Terry Ritter
Joe Peschel
John Savard
Search their articles in this NG. The URLs are in their footer.
-- avs
Andre van Straaten
http://www.vanstraatensoft.com
______________________________________________
flames please to [EMAIL PROTECTED]
------------------------------
From: Daniel James <[EMAIL PROTECTED]>
Subject: Re: Rijndael implementations
Date: Tue, 17 Oct 2000 10:25:14 +0100
Reply-To: [EMAIL PROTECTED]
In article <[EMAIL PROTECTED]>, Runu Knips wrote:
> Using the term 'byte' for the smallest directly addressable storage
> unit is IMHO extremely contraproductive. A byte are 8 bits, point.
> One can read this in any textbook about computer science. And
> Wordaddressable machines can't address bytes.
The use of the term "byte" is much older than the current trend for all
machines to be based about wordlengths that are multiples of 8-bits,
and has been used to describe non-8-bit units of storage on several
architectures. There's been soe discussion of this elsewhere in the
thread.
My first practical encounter with the term byte was on an ICL 1900
mainframe which had 24-bit words, and used the term "BYTES" to mean a
group of 4 6-bit characters packed into such a word. Nothing was 8-bit
on that architecture (though I must admit that here my own defintion
falls down, as individual characters in a BYTES were not separately
addressable).
> And before I've read your posting I wouldn't have the tiniest clue
> what 'octett' means.
Well - apart from the fact that I was not the first person in this
discussion to use the term - I would have expected regular contributors
to sci.crypt to know that ASN.1 uses "OCTET" to mean what you want to
call a "byte". It's also the French word for a byte.
Cheers,
Daniel.
------------------------------
From: "Tim Tyler" <[EMAIL PROTECTED]>
Subject: Re: algo to generate permutations
Date: Tue, 17 Oct 2000 10:25:26 +0100
"Mok-Kong Shen" <[EMAIL PROTECTED]> wrote:
> Tim Tyler wrote:
> > http://mandala.co.uk/permutations/ contains an exhaustive permutation
> > generator, in the form of a Java applet.
>
> Dumb question: Is its output in lexicographical order?
It is. I should have stated this on the page, really.
--
__________ Lotus Artificial Life http://alife.co.uk/ [EMAIL PROTECTED]
|im |yler The Mandala Centre http://mandala.co.uk/ Namaste.
------------------------------
Date: Tue, 17 Oct 2000 11:28:12 +0200
From: Runu Knips <[EMAIL PROTECTED]>
Subject: Re: Works the md5 hash also for large datafiles (4GB) ?
[EMAIL PROTECTED] wrote:
> I have to compare diskimages. To save diskspace I want to use
> a hash (md5).
>
> Work md5 for such large files?
> I know I would generate a 128bit signature, what I mean is, is
> the probability that two different large files have the same
> signature as low as for smaller files.
>
> In other words, is the algorthm of md5 only designed for "small"
> files?
AFAIK MD5, SHA-1, RIPE MD160 and Tiger/192 all work with 64 bit
size counters. I guess SHA256 does, too.
------------------------------
From: "Antonio Merlo" <[EMAIL PROTECTED]>
Subject: x509
Date: Tue, 17 Oct 2000 11:29:26 +0200
x509 certificate has the following syntax:
Certificate ::= SIGNED { SEQUENCE {
version [0] Version DEFAULT v1,
serialNumber CertificateSerialNumber,
signature AlgorithmIdentifier,
issuer Name,
validity Validity,
subject Name,
subjectPublicKeyInfo SubjectPublicKeyInfo,
issuerUniqueIdentifier [1] IMPLICIT UniqueIdentifier OPTIONAL,
subjectUniqueIdentifier [2] IMPLICIT UniqueIdentifier OPTIONAL
extensions [3] Extensions OPTIONAL
}
where signed mean:
SIGNED { ToBeSigned } ::= SEQUENCE {
toBeSigned ToBeSigned,
COMPONENTS OF SIGNATURE { ToBeSigned }}
SIGNATURE { ToBeSigned } ::= SEQUENCE {
algorithmIdentifier AlgorithmIdentifier,
encrypted ENCRYPTED-HASH { ToBeSigned }}
Does anybody know why it is included algorithmIdentifier on the certificate
date if it is present on data signature? Currently this information is
duplicated on all certificates and I don't know why?
------------------------------
From: "Tim Tyler" <[EMAIL PROTECTED]>
Subject: Re: What is meant by non-Linear...
Date: Tue, 17 Oct 2000 10:36:18 +0100
"Stephen M. Gardner" <[EMAIL PROTECTED]> wrote:
> Tim Tyler wrote:
> Draw some linear equations defined on a finite field
> (use a cylinder as the drawing surface if you want).
> Compare them to similar equations defined on an interval
> of the field of reals [...] You will find that the finite field
> equations jump around instead of staying on the line.
> Don't argue, just draw. ;-)
I can plot "straight lines" through the points in the finite field.
The "straight lines" curve on the surface of the cylinder - but they have a
fixed
local gradient with respect to the {theta,x} co-ordinate system, and don't
"jump around".
> > "a straight line mapped onto the surface of a
> > cylinder" is defined as having an equation in the form of either x = k,
> > or theta = a.x + b.
>
> Where did you get this definition?
Well, I made it up out of my own head, to be consistent with my thesis.
> How general is it?
Pretty general, AFAICS.
> Hint: What assumptions are you making here about the field that the
equations are defined on?
Not a good enough hint for me - unless you're talking about field where "*"
and "+"
don't behave themselves. Perhaps you can spell out what you're getting at.
--
__________ Lotus Artificial Life http://alife.co.uk/ [EMAIL PROTECTED]
|im |yler The Mandala Centre http://mandala.co.uk/ Namaste.
------------------------------
From: "Florian Peterl" <[EMAIL PROTECTED]>
Subject: useful literature?
Date: Tue, 17 Oct 2000 11:44:09 +0200
Hello Guys,
has anybody any recommendation concerning literature in cryptography?
I'm not a rookie but I'm not a professional in that subject.
Thanks for your help
Florian
------------------------------
From: "Tim Tyler" <[EMAIL PROTECTED]>
Subject: Re: Counting one bits is used how?
Date: Tue, 17 Oct 2000 10:52:44 +0100
"Peter van der Linden" <[EMAIL PROTECTED]> wrote in message
news:8sgehk$2eha$[EMAIL PROTECTED]...
> How does counting the number of 1 bits in a word
> relate to crypto?
>
> Just curious about why this seemingly recondite instruction
> pops up in various instruction sets. How is it useful?
I'm not sure about cryptography - but it makes for a fast, bitwise "~=" -
which may well have uses in cryptanalysis.
``There was a strange instruction on Cybers called the Population Count
instruction.
It returned the number of "1" bits in the argument. It was rumored that
this instruction
was added to Cybers by the designer, Seymour Cray, at the request of the
National Security Agency (NSA). There is some validity to this rumor, but
it may
never be proven.'' - http://w3.uwyo.edu/~jimkirk/cyber_era.html says.
The instruction is sometimes known as the "NSA instruction" as a
consequence -
no doubt to the irritation of those who were brought up to believe that the
NSA instruction should perform a "Nibble Swap" on the "Accumulator".
One alternative looks something like:
#define BITCOUNT(x) (((BX_(x)+(BX_(x)>>4)) & 0x0F0F0F0F) % 255)
#define BX_(x) ((x) - (((x)>>1)&0x77777777) \
- (((x)>>2)&0x33333333) \
- (((x)>>3)&0x11111111))
;-)
--
__________ Lotus Artificial Life http://alife.co.uk/ [EMAIL PROTECTED]
|im |yler The Mandala Centre http://mandala.co.uk/ Namaste.
------------------------------
From: "Tim Tyler" <[EMAIL PROTECTED]>
Subject: Re: pseudo random test
Date: Tue, 17 Oct 2000 11:02:01 +0100
"Jacques Th�riault" <[EMAIL PROTECTED]> wrote:
> maybe this is still not enough, but a little bit more substantial than
> the previous
>
> followin are 20,000 character from a set of 94 ( ie: printable )
[large snip]
The fact that "most good statistical tests for randomness require much
more than what you've just provided" should ***NOT*** be taken as
an invitation to post large binaries to sci.crypt.
Posting binary data to non-binary usenet groups is liable to get you
lynched.
See http://www.newsreaders.com/guide/netiquette.html for this, and
a list of other things to avoid doing.
--
__________ http://alife.co.uk/ http://mandala.co.uk/
|im |yler [EMAIL PROTECTED] http://hex.org.uk/ http://atoms.org.uk/
------------------------------
** 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
******************************
