Cryptography-Digest Digest #164, Volume #10 Thu, 2 Sep 99 23:13:03 EDT
Contents:
Re: I too need an algorithm :o) (was: Re: I need an algorithm!!!!) ("Vedat Hallac")
Re: Ways to steal cookies in HTTP and HTTPS (Barry Margolin)
Graphical Passwords (AlainNYC)
Re: I need an algorithm!!!! ("Steven Alexander")
Re: Odp: THINK PEOPLE ([EMAIL PROTECTED])
Re: THINK PEOPLE (Frank Gifford)
Re: 512 bit number factored (Wei Dai)
Re: SQ Announcement (David Wagner)
Re: How weak is a large non-prime diffie-hellman modulus? (Bob Silverman)
Re: THINK PEOPLE (John Savard)
Help on Yarrow Please! (Michael Heumann)
Re: Public/Private Encryption Win32 Control? (Paul Rubin)
Re: I need an algorithm!!!! ("Micha�l Chass�")
Re: Using Diffie-Hellman to encode keys (Nicol So)
Re: THINK PEOPLE (David A Molnar)
Re: I need an algorithm!!!! (David A Molnar)
Re: Using Diffie-Hellman to encode keys ("rosi")
Re: Vigenere Variant Problem (JTong1995)
----------------------------------------------------------------------------
From: "Vedat Hallac" <[EMAIL PROTECTED]>
Subject: Re: I too need an algorithm :o) (was: Re: I need an algorithm!!!!)
Date: Fri, 3 Sep 1999 09:17:23 +1000
>my previous messages were ignore, maybe they were not understood, maybe
they were too simple, maybe nobody knows?
As long as you only look for an algorithm, and not one without any
weaknesses, I can direct you to an answer I have provided for a similar
thread. It was a variation of the RSA scheme with three primes instead of
two. I haven't done any analysis on the algorithm to prove that it always
works (I suspect that it does), or its security (in the sense of no
weaknesses introduced during the algorithm tweaking, apart from the smaller
message domain, which is what you want anyway). Nobody commented on the
algorithm, and I am not surprised about it, because what the algorithm does
is not something used around. :-)
Anyway, if you want to have a look at the thing, I suggest you search
sci.crypt in dejanews for messages posted by "mvhallac". You will only get a
handful messages, so it should be easy to locate the thing.
Have fun.
------------------------------
From: Barry Margolin <[EMAIL PROTECTED]>
Crossposted-To: comp.infosystems.www.misc,comp.security.misc
Subject: Re: Ways to steal cookies in HTTP and HTTPS
Date: Thu, 02 Sep 1999 23:52:14 GMT
In article <[EMAIL PROTECTED]>,
isoma <[EMAIL PROTECTED]> wrote:
>I understand that some sites use cookies to store sensitive information,
>but not the mechanism by which a malicious site owner obtains it.
I think the original post presumed that the malicious site was spoofing
traffic from the site you were connecting to, and inserting HTML tags that
would cause your browser to connect to his site for some images and send
your cookie information to him as part of that transaction. That's why
he's concerned about 3rd-party cookies.
--
Barry Margolin, [EMAIL PROTECTED]
GTE Internetworking, Powered by BBN, Burlington, MA
*** DON'T SEND TECHNICAL QUESTIONS DIRECTLY TO ME, post them to newsgroups.
Please DON'T copy followups to me -- I'll assume it wasn't posted to the group.
------------------------------
From: [EMAIL PROTECTED] (AlainNYC)
Subject: Graphical Passwords
Date: 02 Sep 1999 23:57:32 GMT
Hi,
we are a group of researchers from Bell Labs, AT&T Labs and
NYU. We implemented "graphical passwords" for the PalmPilot.
That is, you can simply draw a little figure as your password
rather than trying to remember some funky textual password.
his password is then use to encrypt data in the memopad
application.
We have an alpha release ready to download for free.
See http://cs.nyu.edu/fabian/pilot/gpw.html
for more details.
------------------------------
From: "Steven Alexander" <[EMAIL PROTECTED]>
Subject: Re: I need an algorithm!!!!
Date: Thu, 2 Sep 1999 17:17:18 -0700
It is conjectured in "The Handbook of Applied Cryptography" that Chor-Rivest
can be secure if its parameters are carefully chosen, however this creates a
very large public key. In the aforementioned book it cites the public key
with the paramters of p=197 and h=24 to be 36,000 bits. I haven't studied
knapsacks enough to offer more than this.
-steven
David A Molnar <[EMAIL PROTECTED]> wrote in message
news:7qmtov$c4f$[EMAIL PROTECTED]...
> Steven Alexander <[EMAIL PROTECTED]> wrote:
> > If you're not so mathematically inclined, you could implement a knapsack
> > algorithm as the public key side of your system. Be warned that
knapsacks
> > are not secure.
>
> More precisely, the original Merkle-Hellman knapsack (which is what you
> get out of Applied Cryptography) can be broken in minutes by an
> Apple II. The Chor-Rivest knapsack was reported broken in 15 minutes on
> "an old laptop." Those are the only two reports I know off the top of my
> head.
>
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Odp: THINK PEOPLE
Date: Fri, 03 Sep 1999 00:31:17 GMT
In article <[EMAIL PROTECTED]>,
[EMAIL PROTECTED] (John Savard) wrote:
> "Bartek Z." <[EMAIL PROTECTED]> wrote, in part:
>
> >Geee... I have a strange feeling during reding Mr. SCOTT19...
(whatever)
> >postings that I'm wasting my precious time. Don't You?
> >Shall sci.crypt be available for everyone? Aren't there any filters
for such
> >boring and annoying people?
>
> He is improving, though. In the past week, he has had a couple of
> posts that made sense.
>
> I am saddened that he is making it harder for his valid ideas, when
> expressed by others, to be taken seriously: that it's a good idea to
> use larger keys than strictly necessary, and large key-dependent
> S-boxes are good for safety.
>
> John Savard ( teneerf<- )
> http://www.ecn.ab.ca/~jsavard/crypto.htm
It is very sad, since this time David is correct. His
method would secure the message, the other ones lack that
ability in this case. However; it's kind of like bringing a gun to a
judo match. David just wants to play by his own rules.
But still his method is to slow for practical applications,
and is not really that much more secure for most uses,
except in rare cases like this. There really is no need for
this level of security. He just does not get it! Small block
sizes and keys will be safe for millions of years.
I have tested his method a lot and it seems secure. But any of
us could design a method that treats the whole file as a
single block. It is just that this level of security is not needed
any time in our lifetimes.
Please Dave, on the next contest, make sure the solution is unique.
It bugs me that I can't even find one solution of the desired form
and I know that many exist.
Take Care
Sent via Deja.com http://www.deja.com/
Share what you know. Learn what you don't.
------------------------------
From: [EMAIL PROTECTED] (Frank Gifford)
Subject: Re: THINK PEOPLE
Date: 2 Sep 1999 19:52:18 -0400
In article <yQzz3.112$[EMAIL PROTECTED]>,
Steven Alexander <[EMAIL PROTECTED]> wrote:
>According to the way you described this, they don't need the last 100 bytes
>of the message anyway. The information that is different from the other
>messages happens to be in the middle. The attackers can of course decrypt
>up until the point that one of the blocks in incomplete. How would
>Scott1X_U work any differently to prevent this? I don't see why they
>couldn't still recover the message. Also, if they already have 2/3
>messages, the key, and they're raiding your house, be very afraid.
David's point is exactly what you are thinking. If you use the common
methods of encryption, you recover all of that initial portion except the
last 100 bytes. However, his program is one of the versions which iterate
over the entire message multiple times. So if you have all except the last
100 bytes of the encryption, you are unable to decrypt anything at all.
His further point is that if you are using an AES candidate in (say) CBC
mode, your data can be recovered given the above conditions ("They" know
the encryption key!). So having a super strong algorithm encrypting a
single block is not good enough in some instances.
-Giff
--
Too busy for a .sig
------------------------------
From: [EMAIL PROTECTED] (Wei Dai)
Subject: Re: 512 bit number factored
Date: Thu, 2 Sep 1999 17:02:08 -0700
In article <[EMAIL PROTECTED]>, [EMAIL PROTECTED]
says...
> Bob Silverman <[EMAIL PROTECTED]> writes
> > It has been well known since 1990 that 512 bit keys were breakable
> > and within computer capabilities.
>
> So, supposing you write a similar comment 9 years from now, how could
> you fill in the blank:
>
> It has been well known since 1999 that _____ bit keys were breakable
> and within computer capabilities.
>
> What is the largest value which you would feel comfortable putting in the
> blank today, with the same level of assurance as with the 1990 statement?
> In other words, what size keys appear equally as breakable today as 512
> bit keys appeared in 1990?
I'm not Bob Silverman, but I'll give it a shot.
In 1990, a 512 bit number could have been factored using 5000 computers
(10 MIPS each) for a year. (It would have used more than 8000 MIPS-years
because factoring related algorithms have improved since then.) Today, 20
thousand computers (500 MIPS each at 1/4 the price of a 1990 computer)
for a year lets you factor a 700 bit number.
If we assume no further algorithmic improvements and that computing power
per dollar continues to increase at a factor of 1.5 per year, then 9
years from now an effort similar to RSA-155 (about 50 CPU-years) should
be able to break 600-650 bit numbers. With further algorithmic
improvements or an effort similar to RSA-129 (about 500 CPU-years), 700
bits can be factored 9 years from now.
So if I had to put a single number in the blank I would put in 700. RSA-
210 (about 700 bits) can be factored today by anyone who really wanted
to, but will most likely be done in about 9 years.
Now a question of my own: does anyone actually use 512-bit keys for e-
commerce, as CWI's press release claims?
------------------------------
From: [EMAIL PROTECTED] (David Wagner)
Subject: Re: SQ Announcement
Date: 2 Sep 1999 16:54:31 -0700
In article <7qmt0k$[EMAIL PROTECTED]>,
Kostadin Bajalcaliev <[EMAIL PROTECTED]> wrote:
> Sr<<1 (should be Sr<<<1) this is standard notation
This isn't standard notation. Elsewhere in your thesis you define
the notation `P<<<1' to mean that you take the permutation P and you
shift it left by one. But Sr isn't a permutation; it's a single byte,
right?
> Information Lose theory is:
>
> If we need more information than the output carry about them inner state of
> the generator in order to reconstruct the inner state then the Cipher is
> "secure".
If I understand correctly, you're talking about whether the cipher is
information-theoretically secure. Trivially, when the output keystream
length is longer than the key length, the cipher _cannot_ be
information-theoretically secure. Ever. (Read Shannon, or the FAQ.)
------------------------------
From: Bob Silverman <[EMAIL PROTECTED]>
Subject: Re: How weak is a large non-prime diffie-hellman modulus?
Date: Fri, 03 Sep 1999 01:22:09 GMT
In article <[EMAIL PROTECTED]>,
Medical Electronics Lab <[EMAIL PROTECTED]> wrote:
> John Matzen wrote:
> >
> > I have a raft of questions here I hope someone can clear up for me.
> >
> > For all practical purposes, does it really make sense to spend all that CPU
> > time to come up with a 2048-bit prime number, or just use a completely
> > random number? Would a 512-bit strong prime be more secure than a 2048-bit
> > weak prime? Would a 512-bit weak prime truly be stronger than a 2048-bit
> > odd non-prime? Is there really a quick attack against any non-prime modulus?
>
> Yes. It's called "index calculus" attack. If
> the factors of your 2048 bit number are less than
> 512 bits, then the 512 bit prime is stronger.
No.
When solving a discrete log problem mod N, when N is composite,
the only way to apply an index calculus attack is to know the
order of the cyclic subgroup generated by g. This requires factoring
N first.
Or, one can apply Pollard Rho, and then the time is proportional
to the square root of the size of the subgroup generated by g.
But to do an index calculus attack over a finite ring, rather than
field, first requires factoring N.
Allow me to ask the original poster why he believes 2048 bit random N is
needed?? 1024 bit primes are more than sufficient provided that g generates
a sufficiently large subgroup. You determine this by knowing the
factorization of p-1.
The rest of your questions about 512 bit 'strong' prime vs. 2048 bit 'weak'
primes make no sense. Your basic assumptions are wrong. The Number Field
Sieve's run time only depends on the size of the number and nothing else.
You only need make certain that your field is sufficiently large
and that g generates a sufficiently large subgroup. You can insure
this (and guard against Pohlig-Hellman) by having p-1 have a
sufficiently large prime factor .
2048 bits is MASSIVE, MASSIVE, overkill.
--
Bob Silverman
"You can lead a horse's ass to knowledge, but you can't make him think"
Sent via Deja.com http://www.deja.com/
Share what you know. Learn what you don't.
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: THINK PEOPLE
Date: Thu, 02 Sep 1999 19:30:30 GMT
David A Molnar <[EMAIL PROTECTED]> wrote, in part:
>At the IEEE P1363 web site, there's a letter from Bellare and Rogaway
>indicating that they did not patent OAEP :
the URL should be
http://grouper.ieee.org/groups/1363/letters/BellareRogawayMar98.txt
John Savard ( teneerf<- )
http://www.ecn.ab.ca/~jsavard/crypto.htm
------------------------------
From: Michael Heumann <[EMAIL PROTECTED]>
Subject: Help on Yarrow Please!
Date: Fri, 03 Sep 1999 01:06:04 GMT
Hi,
I already posted a couple of days ago on this subject, but nobody
replied :-( (Subject: How to use Yarrow?)
I really need help here soon, because until now I haven't even been
able to get the testapp to work. All the prngOutput(buf,13) calls don't
change buf at all. What am I missing? I've been having the frontend
running all day, there should be enough entropy, shouldn't there?
Tom St Denis, I've seen you post on several PRNG issues before. Do you
have any experience with Yarrow?
Please somebody read my previous post and try to help me.
Thanks,
Michael
Sent via Deja.com http://www.deja.com/
Share what you know. Learn what you don't.
------------------------------
From: [EMAIL PROTECTED] (Paul Rubin)
Subject: Re: Public/Private Encryption Win32 Control?
Date: 3 Sep 1999 01:53:15 GMT
In article <7qmtji$kur$[EMAIL PROTECTED]>, forq <[EMAIL PROTECTED]> wrote:
>I suppose I could make external calls to PGP, but I'd rather not, as it
>isn't nearly as elegant, and I'm not even sure I can do that from .ASP
>pages. Why am I using NT & ASP? Well, that isn't my choice...
>
>Any ideas or suggestions on how I might accomplish these goals?
Somebody posted a URL for a PGP COM object on sci.crypt a couple
weeks ago. Check dejanews.
------------------------------
From: "Micha�l Chass�" <[EMAIL PROTECTED]>
Subject: Re: I need an algorithm!!!!
Date: Thu, 2 Sep 1999 21:53:44 -0400
Thank's everybody for these very usefull answers... Finally I'll use modulos
algo... :O)
Micha�l Chass�
Qu�bec,Canada
Micha�l Chass� <[EMAIL PROTECTED]> a �crit dans le message :
apkz3.1696$[EMAIL PROTECTED]
> Hello,
>
> I'm a programmer student and I really need a strong Public/private key
> system algorithm that is unpatented and that do not use mod... Does
someone
> has a suggestion for me? In case that doesn't exist, an algorith other
than
> Diffie/Hellman or RSA should be appreciated....
>
> Sincerely,
>
> Micha�l Chass�
> Qu�bec, Canada
>
>
------------------------------
From: Nicol So <[EMAIL PROTECTED]>
Subject: Re: Using Diffie-Hellman to encode keys
Date: Thu, 02 Sep 1999 21:05:04 -0400
David Wagner wrote:
>
> In article <[EMAIL PROTECTED]>,
> Nicol So <[EMAIL PROTECTED]> wrote:
> > Eric Lee Green wrote:
> > > The problem I'm trying to figure out is using the resulting 'k' to transfer an
> > > initial 56-bit DES key (the max allowed for US export). k is not suitable for
> > > use as a DES key because it is sparsely distributed over field n.
> >
> > Some possibilities:
> >
> > 1. Truncate 'k' to the desire size and use it as the encryption key.
> > 2. Hash 'k' to the desire size using a good hash function (not
> > necessarily a cryptographically strong one).
> > 3. Use the result of 1 or 2 above as an XOR mask to cover the encryption
> > key.
>
> #3 is a bad idea, because it opens up the possibility of related-key attacks.
> I'm also a bit wary of #1, because of the potential for algebraic attacks.
> I suggest #2. (Better still is to hash not only g^{xy} but also g^x,g^y.)
>
> By the way, I'm not clear on why you aren't willing to just use the result
> of the hash as a DES key directly. What am I missing?
I don't have any problem with using the hash value as the DES key, but
since I'm not in a position to choose a solution for the original
poster, all I did was to point out possibilities, and the fact that
there are many of them.
Related key attacks are a potential problem, but whether they are
feasible or not depends on details not stated in the original message.
I do, however, agree that it would be better if the problem can be
prevented without relying on assumptions external to the key agreement
protocol.
Regarding #1, I did consider the possibility of algebraic properties
being exploited, but I couldn't come up with a specific feasible
attack. I think if 'k' as a whole is secure at all, the middle portions
of the bits should be safe.
I consider #2 (or some embellishment of it) the natural solution, or at
least a natural one.
Nicol
------------------------------
From: David A Molnar <[EMAIL PROTECTED]>
Subject: Re: THINK PEOPLE
Date: 3 Sep 1999 02:33:52 GMT
Frank Gifford <[EMAIL PROTECTED]> wrote:
> over the entire message multiple times. So if you have all except the last
> 100 bytes of the encryption, you are unable to decrypt anything at all.
If you have another message which you know has an identical last 100
bytes to the message you want to recover, _and_ a deterministic encryption
scheme + all or nothing transform, then you cut and paste and it'll work.
-David
------------------------------
From: David A Molnar <[EMAIL PROTECTED]>
Subject: Re: I need an algorithm!!!!
Date: 3 Sep 1999 02:49:48 GMT
Steven Alexander <[EMAIL PROTECTED]> wrote:
> It is conjectured in "The Handbook of Applied Cryptography" that Chor-Rivest
> can be secure if its parameters are carefully chosen, however this creates a
I don't doubt that. It's just that a new attack came out at CRYPTO '98
which applied to parameters previously thought to be secure.
"Cryptanalysis of the Chor-Rivest Cryptosystem" Serge Vaudenay
paper should be at http://www.dmi.ens.fr/~vaudenay/pub.html
> very large public key. In the aforementioned book it cites the public key
> with the paramters of p=197 and h=24 to be 36,000 bits. I haven't studied
> knapsacks enough to offer more than this.
Yeah...not easy stuff. :-\ If I'm reading the last part of the above paper
correctly, the "15 minute to recover secret key from public key" report
was for the parameters.
-David
------------------------------
From: "rosi" <[EMAIL PROTECTED]>
Subject: Re: Using Diffie-Hellman to encode keys
Date: Thu, 2 Sep 1999 22:25:53 -0400
Eric Lee Green wrote in message <[EMAIL PROTECTED]>...
[snip]
>
>The problem I'm trying to figure out is using the resulting 'k' to transfer
an
>initial 56-bit DES key (the max allowed for US export). k is not suitable
for
>use as a DES key because it is sparsely distributed over field n. The first
>obvious choice is to use an operation that is easily reversed if you know
'k',
>but is a Hard Problem if you don't know k, such as:
>
> Jack Jill Shared
> d (random DES key) D=d*k
> d=D/k
>
Could have missed something.
1. As Nicol and others pointed out the active type attacks.
2. Go something like SPEKE, but then you already have this shared
secrect. If you can do one 'unit' of that, the cost should not be too
out-of-control to do two...
3. Don pointed out the methods of deriving session keys. I think it is
much easier to get one-way when compress.
4. You may not (under the premise of 'property' of k) want to do d=D/k
and D=d*k. You may want E=D*k, implying (computationally) 'there is
no' /.
--- (My Signature)
------------------------------
From: [EMAIL PROTECTED] (JTong1995)
Subject: Re: Vigenere Variant Problem
Date: 03 Sep 1999 03:06:31 GMT
The good news is that I finally broke the message. It had some nulls at the
end that initially prevented me from determining who signed the message. I
found a repeat that I assumed was "STOP", which was the begining of what turned
out to be a sterotypical ending with the unit commander's name, followed by the
3 letter abrev for his rank (COL = Colonel) and then the 3 letter abrev for his
branch (INF = Infantry). The twist was the remaining letters used to fill the
final five letter group were X's, which were enciphered polyalphabetically.
That gave me enough plaintext - ciphertext equivilants to use direct symetery
of position. In retrospect, I should have seen that sooner, but I kept looking
for other, more complex things (probable word: Pershing or Chapparal
missile...). Thanks for the suggestions.
Jeffrey Tong [EMAIL PROTECTED]<Jeffrey Tong>
PGP 5 Key available for download at WWW.PGP.COM Key ID: BFF6BFC1
Fingerprint: 6B29 1A18 A89A CB54 90B9 BEA3 E3F0 7FFE BFF6 BFC1
------------------------------
** 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
******************************
