Cryptography-Digest Digest #142, Volume #10 Mon, 30 Aug 99 18:13:04 EDT
Contents:
Re: What if RSA / factoring really breaks? (DJohn37050)
Re: What if RSA / factoring really breaks? (Anton Stiglic)
Re: Workshop in Paris on Watermarking and Copyright enforcement (Robert Harley)
Re: What if RSA / factoring really breaks? (Anton Stiglic)
Re: On employing message-decoys (Eric Lee Green)
Re: Can I export software that uses encryption as copy protection? (Eric Lee Green)
Re: 512 bit number factored (DJohn37050)
Re: All I find the topic fascinating how might I learn.. (Jim Dunnett)
Cryptography Items and Issues ("Markku J. Saarelainen")
Re: What if RSA / factoring really breaks? (Keith A Monahan)
Re: Cryptography Items and Issues (John Savard)
Re: What if RSA / factoring really breaks? (Keith A Monahan)
Re: On employing message-decoys (Mike Bell)
Re: The Reversal of NetNanny ([EMAIL PROTECTED])
Re: RC4 question ("John E. Kuslich")
Newbiehelp ("B3avis")
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (DJohn37050)
Subject: Re: What if RSA / factoring really breaks?
Date: 30 Aug 1999 18:57:26 GMT
Note that the Certicom ECC challenges are different from the RSA Lab's RSA
challenges as no one ever knew the ECC private keys associated with the public
keys in the challenge. This was deliberate.
Don Johnson
------------------------------
From: Anton Stiglic <[EMAIL PROTECTED]>
Subject: Re: What if RSA / factoring really breaks?
Date: Mon, 30 Aug 1999 15:03:06 -0400
> > > What would this contibute to the NP vs. P problem?
> >
> > It shows us that a problem not known to be NP-complete is in P.
>
> Huh? Justify this statement!!
I think that he was just trying to say that it is not known if FACTOR is in
NP-hard
(or, that the corresponding yes/no problem is not known to be in
NP-complete).
This beeing said, if FACTORING is in P, this does not mean that NP = P .
In fact, an article of Brassard states that FACTOR is not NP-hard, so no
collapsation
of NP would arise if FACTOR would be in P.
------------------------------
From: Robert Harley <[EMAIL PROTECTED]>
Crossposted-To: comp.lang.java.security,comp.graphics.misc,rec.arts.movies.tech
Subject: Re: Workshop in Paris on Watermarking and Copyright enforcement
Date: 30 Aug 1999 18:37:43 +0200
Louis Granboulan <[EMAIL PROTECTED]> writes:
> Workshop on Watermarking and Copyright enforcement
> [...] We will focus on the following issues:
>
> * Insertion of a watermark in a document (image, music, java bytecode,
> etc.). Ideally, this mark should be invisible and impossible to erase.
This is clearly impossible and such claims for watermarking should be
ranked alongside similar bogus claims, like compression programs
that can supposedly compress every file.
A lesser claim like "almost invisible and quite difficult to erase"
would have the distinct advantage of not being nonsense.
Bye,
Rob.
------------------------------
From: Anton Stiglic <[EMAIL PROTECTED]>
Crossposted-To: alt.math,sci.math
Subject: Re: What if RSA / factoring really breaks?
Date: Mon, 30 Aug 1999 15:05:10 -0400
[EMAIL PROTECTED] wrote:
> From "David J Whalen-Robinson" <[EMAIL PROTECTED]>:
>
> [entire article elided]
>
> Bill Payne, PhD, of Albuquerque, NM already broke RSA several years ago, and his real
> time method using Euler's tuotient was disclosed at that time. RSA is broken
>already.
>
> Use non inversive encryption instead, such as licensing US Patent No. 5,926,815, a
> two-phase random number generator which is the fastest known.
Yeah right!!
Anton Stiglic, M.Sc, of Montreal broke everything there exists.
Use One-Time pad only.
:)
as
------------------------------
From: Eric Lee Green <[EMAIL PROTECTED]>
Subject: Re: On employing message-decoys
Date: Mon, 30 Aug 1999 12:57:06 -0700
Mok-Kong Shen wrote:
> this time frame is just within the capability of the adversary. She
> sends in addition to the true message 9 dummy messages with random
> or bogous contents, employing different keys. Doesn't this increases
> the security of her message tenfold because the chance of analysis
> is reduced to 1/10 of the original? If she sends 99 dummy messages,
> doesn't she have a legitimate hope that the adversary would probably
> give up?
What is the difference between sending ten different messages, and
adding 4 bits to the encryption key (multiplies the number of possible
keys to brute-force by a factor of 16)?
--
Eric Lee Green http://members.tripod.com/e_l_green
mail: [EMAIL PROTECTED]
^^^^^^^ Burdening Microsoft with SPAM!
------------------------------
From: Eric Lee Green <[EMAIL PROTECTED]>
Crossposted-To: misc.legal.computing
Subject: Re: Can I export software that uses encryption as copy protection?
Date: Mon, 30 Aug 1999 12:47:18 -0700
"Trevor Jackson, III" wrote:
> Eric Lee Green wrote:
> > Timur Tabi wrote:
> > Yes, that is legal, but note that I could crack this "registration"
> > scheme within minutes using a normal binary editor to change the output
> > of your verification routine to always say "verified!".
>
> What if there is no such routine? What if the security routine simply decrypts the
> operable binary image?
Yes, that was a common copy protection scheme back in the early 80's.
They would encrypt major portions of the binary image, including the
portions that examined the copy protection on the disk. All it did was
make it a nuisance, because we had to set a breakpoint at the end of the
decrypt routine and then save the decrypted binary before continuing. In
retaliation, the copy protection vendors added multiple levels of
decryption, i.e., they decrypted the binary, but then other portions of
the binary were similarly encrypted and had to be decrypted using a
different key, etc. This made it a nuisance, but5 the same process could
be done.
> To circumvent this you have to intercept the "plaintext binary" and replay it.
> That can be made difficult.
Not if it is physically on my disk. I don't even necessarily have to
replay it. The first major program that I ever wrote was a commenting
disassembler (i.e., you could add comments that went with various memory
addresses), and then I could patch the binary directly on the disk prior
to loading it.
> > Back in the early 80's software publishers tried to create "unbreakable"
> > copy protection schemes. They failed. If I have physical access to your
> > software, I can load it into a binary debugger, trace its execution, and
> > 'break' it.
>
> In theory this is always possible, but in some cases it requires enormous hardware
> support.
It requires enormous hardware support only if it's not on your disk
drive. As I mentioned, I can disassemble it while it's not running, and
patch the binary directly to put a breakpoint after the end of the
decryption routine that jumps into the debugger.
> a few of the more interesting interrupt vectors. An application can make this
> difficult by using those vectors for other purposes
Not on most modern operating systems. For example, Unix runs all
programs in a virtual machine, and the debugger operates outside of that
virtual machine. But even on more primitive operating systems, all you
have done is inconvenience me, not stop me.
> In theory one can provide a perfect virtualization of any environment, single
> stepping the application as necessary. But this will skew the instruction rate in
> a manner detectable to the application. In order to prevent the skew the attacker
> needs the equivalent of an extremely fast in-circuit-emulator.
Poppycock. All I need is access to the program on my hard drive, a
commenting disassembler, and a debugger. How many programs have you
cracked anyhow? (I'll take the 5th on how many I cracked back in my
childhood).
> It's not impossible, but, like most modern crypto, it can be made unreasonably
> expensive. The failure of the software vendors around the time PCs were introduced
> does not indicate the difficulty of creating debug-proof software. It indicates
> the amateurishness of the software vendors.
Again: How many programs did you attempt to crack? How can you tell us
that the software vendors were amateruish, when you have zero (zilch)
experience in cracking programs? If you are talking about programs that
run directly on the hardware you may be correct. But programs which are
on disk and which run under the control of an operating system can
always be attacked.
The fact of the matter is that if I have physical access to the actual
decryption part of the program, I can always (ALWAYS) rig it to spit out
the plaintext to disk. Assuming the decryption key is embedded in the
program somewhere, I have your plaintext. The most you can do is encrypt
the program using a key that must be received from external sources, but
that is either a distribution nightmare or useless (i.e., either each
copy of the program is encrypted with a different key, or all copies are
encrypted with the same key, i.e. one person posting the key on alt.2600
just rendered your encrypted license stuff useless).
Cryptographic systems can only secure communications. They cannot stop
an attacker from viewing the plaintext by "tapping" the decryption
engine. Given physical access to the decryption engine, it can be rigged
to spit out the plaintext to me at the same time that you view it.
Without understanding this, you will never be able to create a secure
cryptographic system.
My own licensing system uses strong authentication to make sure that
script kiddies cannot type just anything for the license key and have
the program work, but I have no illusions about this being secure
against crackers with binary editors, disassemblers, and debuggers.
--
Eric Lee Green http://members.tripod.com/e_l_green
mail: [EMAIL PROTECTED]
^^^^^^^ Burdening Microsoft with SPAM!
------------------------------
From: [EMAIL PROTECTED] (DJohn37050)
Subject: Re: 512 bit number factored
Date: 30 Aug 1999 19:09:31 GMT
See RSA Labs Cryptobytes, the one with Odlysko's estimates for factoring, this
would be the general dissemination of this information, I think. Just before
that came out Matt Robshaw wrote a paper dated June 29. 1995 "Security
Estimates for 512-bit RSA." That is also on the RSA web site.
>I would also be interested in seeing such an article! An article that "backs
>up" its
>statements.
Don Johnson
------------------------------
From: [EMAIL PROTECTED] (Jim Dunnett)
Subject: Re: All I find the topic fascinating how might I learn..
Date: Mon, 30 Aug 1999 19:01:33 GMT
Reply-To: Jim Dunnett
On Mon, 30 Aug 1999 16:00:56 GMT, [EMAIL PROTECTED] (John
Savard) wrote:
>JC <[EMAIL PROTECTED]> wrote, in part:
>
>>What books or web sites or magazines or whatever do all of you reccomend
>>so that I may learn more. I have always wanted to do it.
>
>Well, my web site is free (and designed not to demand a lot of
>knowledge about mathematics to understand) - and it recommends three
>of the best books, The Codebreakers, by David Kahn, Elementary
>Cryptanalysis, by Helen Fouche Gaines, and Applied Cryptography by
>Bruce Schneier. You won't always find all three of these at every
>library, but there are other good introductory books as well.
>
>John Savard ( teneerf<- )
>http://www.ecn.ab.ca/~jsavard/crypto.htm
It's a good site, (I am painstakingly downloading John's treatise on
cryptography) and the books recommended cannot be bettered as
introductions to a fascinating subject.
--
Regards, Jim. | We have decided not to go to France
amadeus%netcomuk.co.uk | this summer as it is too full of
dynastic%cwcom.net | unattractive, shirtless Englishmen
| talking into mobile 'phones.
PGP Key: pgpkeys.mit.edu:11371 | - Auberon Waugh.
------------------------------
From: "Markku J. Saarelainen" <[EMAIL PROTECTED]>
Subject: Cryptography Items and Issues
Date: Mon, 30 Aug 1999 15:31:38 +0000
NOTE: Before you have read this message, it has been intercepted,
analyzed and processed by several intelligence agencies.
Specific Cryptography Items:
1. Support the strongest encryption in all Internet and other electronic
transactions globally.
2. Reject the Wassenaar Agreement and its controls
3. Remove all encryption controls and restrictions
4. Improve the understanding of information security practices on the
Internet
5. Avoid any free so called "strong" encryption applications - these
have backdoors.
Specific Reasons for These Items:
1. Some so called "strong" encryption products are compromised and have
designed backdoors to allow access to all private communication. Some
designers are actively working with some crypto agencies.
2. Intelligence agencies are using the Internet and its communication
protocols to collect the business information from other companies and
are providing this information for some specific corporations.
3. To secure electronic transactions and communications in the future.
4. Some encryption and cryptography standardization activities are
purely covert encryption control projects.
5. Most Internet communications are being monitored by certain major
intelligence agencies.
------------------------------
From: [EMAIL PROTECTED] (Keith A Monahan)
Crossposted-To: sci.math
Subject: Re: What if RSA / factoring really breaks?
Date: 30 Aug 1999 12:31:24 GMT
[EMAIL PROTECTED] wrote:
: : (obviously you can't just release it, every cracker would have an
: : info-looting-spree before anybody could react. )
: Actually, I think it is felt that the spree would be briefest if exactly
: that course of action were taken.
I agree that full disclosure will bring the fastest fix possible to the
problem. This is especially true if someone writes an actual implementation
and distributes it as a win32 application. :)
We could compare this theoretical situation to the security situation
in unix systems. Despite manufacturers being notified WELL in advance
of security related issues on their operating systems, they typically
do not take action UNTIL there is an exploit released showing the public
how insecure their system is. http://www.rootshell.org has examples.
Keith
: John Savard
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: Cryptography Items and Issues
Date: Mon, 30 Aug 1999 20:58:07 GMT
"Markku J. Saarelainen" <[EMAIL PROTECTED]> wrote, in part:
>NOTE: Before you have read this message, it has been intercepted,
>analyzed and processed by several intelligence agencies.
I wonder if it's been rewritten by any of them too, because...
>Specific Cryptography Items:
>5. Avoid any free so called "strong" encryption applications - these
>have backdoors.
>Specific Reasons for These Items:
>1. Some so called "strong" encryption products are compromised and have
>designed backdoors to allow access to all private communication. Some
>designers are actively working with some crypto agencies.
If there *are* encryption programs out there with backdoors put in at
the request of intelligence agencies - I will not hazard an opinion on
this, except to note that it isn't technically infeasible -
then, wouldn't applications that are sold for money,
the source code of which is, for obvious reasons (or at least as is
the usual practice - the necessity of which is sometimes debated), not
available,
be more likely to be in this category than ones whose source code is
out there too - which are usually the free ones?
John Savard ( teneerf<- )
http://www.ecn.ab.ca/~jsavard/crypto.htm
------------------------------
From: [EMAIL PROTECTED] (Keith A Monahan)
Crossposted-To: sci.math
Subject: Re: What if RSA / factoring really breaks?
Date: 30 Aug 1999 12:41:41 GMT
Nicolas,
Nicolas Bray ([EMAIL PROTECTED]) wrote:
: On 30 Aug 1999 [EMAIL PROTECTED] wrote:
: > : (obviously you can't just release it, every cracker would have an
: > : info-looting-spree before anybody could react. )
: >
: > Actually, I think it is felt that the spree would be briefest if exactly
: > that course of action were taken.
: How so? It seems to me that there are a lot of institutions which would
: require time to switch over to a new crypto system. It seems to me that
: the best way would be demonstration that a method exists followed by total
: secrecy(of course, a lot of people would probably start trying to kill
: you...)
Because these institutions are not going to act until they are put into
a situation where they must act in order to remain secure. Total secrecy
never works, I think some guy named Kerckhoff mentioned this someplace.
The secrets WILL get out, and what will happen is the hackers will develop
a tool to exploit the situation, and meanwhile the corporations are
not using their time wisely - because they assume full disclosure has not
happened.
If it was me, as soon as something like that is released, you do one
of two things, either secure the data, or take it offline - make it
inaccessible until you fix the problem.
Keith
------------------------------
From: [EMAIL PROTECTED] (Mike Bell)
Subject: Re: On employing message-decoys
Date: Mon, 30 Aug 1999 20:48:06 GMT
On Sun, 29 Aug 1999 19:59:59 +0200, Mok-Kong Shen
<[EMAIL PROTECTED]> wrote:
>Alice wants to send a message to Bob. The content of the message
>needs to be kept secret only within 24 hours (e.g. stuffs concerning
>decision making in commercial negotiations) and estimates that
>this time frame is just within the capability of the adversary. She
>sends in addition to the true message 9 dummy messages with random
>or bogous contents, employing different keys. Doesn't this increases
>the security of her message tenfold because the chance of analysis
>is reduced to 1/10 of the original? If she sends 99 dummy messages,
>doesn't she have a legitimate hope that the adversary would probably
>give up?
>
The underlying assumption here is that the adversary does not have
sufficient resources to analyze all the messages. e.g. If I have
100 DES crackers currently sitting idle, then this approach adds
no security - I just use more of my spare resources.
Also this assumes that there are no speed-ups available to me from
processing N messages in parallel. Assuming a brute force known
plaintext attack (searching the entire key space), then attacking
N messages simultaneously takes little longer than attacking a
single message, since each guessed key can be checked against all N
messages for little extra cost.
An interesting sidebar to this are the "numbers" stations which
were/are used for communication to/from agents in Cuba/USA.
Here an interminable sequence of random numbers is read over the
radio in a continuous broadcast. At some point, known only to
the sender/receiver, the random numbers are replaced with an
encrypted message. The attacker has to guess where the message
starts and stops (if anywhere).
Even this approach (on its own) may not help much. Assuming 1 message
is passed per day, and 1 number is uttered per second, there are only
86,400 possible start points. Assuming there is a better attack than
brute force (where all 86,400 possibilities can be attacked in
parallel) - then this is only equivalent to extending the key length
by some 16 bits. (Assumes ciphertext indistinguishable from random,
which it should be).
Unless a weak algorithm must be used (e.g. to fit in with US export
policy), then extending the keylength is probably a better
way to add security.
-- Mike --
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: The Reversal of NetNanny
Date: Mon, 30 Aug 1999 21:33:58 GMT
> native speaker of English, I know). For instance, I caught several
> occurances of "or" when I'm pretty sure you meant "our".
I did a quick search for ' or' and indeed there were many such errors. I
think I've corrected most of them now. I have a hard time explaining that
particular error, it's nothing I usually do. I'll blame <looks in index>
"fatigue due to late night hacking."
> I wrote a somewhat more formal paper with some relevance to censorware
Downloaded and queued for reading.
> One might well ask whether it's a good idea to give the bad people > ideas
I struggled with this too, but basically it like this; Since I'm _for_
sharing of information, thoughts and ideas, then it would be odd - even
hypocritical - if I were to chose _not_ to share my own ideas and thoughts on
things.
Also, if they improve their protection, it'll more fun to reverse, and I'm
all for 'more fun' :-)
Sent via Deja.com http://www.deja.com/
Share what you know. Learn what you don't.
------------------------------
From: "John E. Kuslich" <[EMAIL PROTECTED]>
Subject: Re: RC4 question
Date: Mon, 30 Aug 1999 14:20:55 -0700
We routinely break 40 bit RC4 keys in just a few days (including 2^40 MD5
hashes) using a special Beowolf array of 4 overclocked Celeron processors
operating under Linux. The whole array was put together for less than
$1200. We minimized cost by using overclocked, cheap 300 MHz Celeron
processors, cheap 10Mbit NE2000 ethernet cards and BH6 motherboards. Only
one processor uses a hard disk, all the others boot disklessly from the
master node on the network.
This arrangement uses special Pentium optimized assembler code and takes
advantage of the full clock speed cache memory operation of the Celeron. It
tests keys like Mario Andretti drives race cars!! Intel is nuts to sell
this processor at such a low price.
Imagine what a well funded code cracker could do with 40 bit RC4. 40 bit
RC4 is a joke. Thank you Louis ("No, I won't wear a dress") Freeh and Janet
("I don't see any evidence!" and "My pencil is my word processor") Reno.
JK Http://www.crak.com
___________________________________________________________
Red_Blue wrote:
> Could someone please shed some light on the following issue:
>
> What is the difference in required brute force computing power for
> breaking RC4-40 vs. RC4-128 export (40 secret) keys?
>
> I have run into estimates of 64 MIPS-years for RC4-40, so do these 88
> non-secret 'salt' bits add significantly to that value?
>
> When the recent RSA-155 factoring breakthrough reached me, I also found
> out that my bank's www-self-service here in Finland still uses these
> 'medium-grade' keys with SSL v3 to secure the transactions.
> So it makes me wonder if the strength of the session keys there are a
> bigger problem than someone breaking the key exchange RSA with those
> 8000 or whatever MIPS-years. I don't understand why they are so slow to
> implement stronger encryption when it's now available for banks
> (imported from US)...
>
> Thanks in advance,
>
> Jere Hakanen
--
John E. Kuslich
Password Recovery Software
CRAK Software
http://www.crak.com
------------------------------
From: "B3avis" <[EMAIL PROTECTED]>
Subject: Newbiehelp
Date: Mon, 30 Aug 1999 23:32:14 +0200
Hey there,
I am pretty new at encryption, but I am VERY interested. Does anyone of you
know where to find some good sites that handle about it ? Please reply soon,
B3avis
http://come.to/bchicken
------------------------------
** 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
******************************
