Re: Brumley & Boneh timing attack on OpenSSL

2003-03-24 Thread Nomen Nescio
Regarding using blinding to defend against timing attacks, and supposing
that a crypto library is going to have support for blinding:

 - Should it do blinding for RSA signatures as well as RSA decryption?

 - How about for ElGamal decryption?

 - Non-ephemeral (static) DH key exchange?

 - Ephemeral DH key exchange?

 - How about for DSS signatures?

In other words, what do we need as far as blinding support either in
developing a crypto library or in evaluating a crypto library for use?

Suppose we are running a non-SSL protocol but it is across a real-time
Internet or LAN connection where timing attacks are possible.  And suppose
our goal is not to see a paper and exploit published within the next
three years telling how to break the protocol's security with a few
hours of connect time.

-
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]


Re: Proven Primes

2003-03-11 Thread Nomen Nescio
Tom St Denis writes:
> What is the benefit of having leading/trailing bits fixed?  As far as I
> know it doesn't make any form of index calculus attack any harder to
> apply.

The Handbook of Applied Cryptography, http://www.cacr.math.uwaterloo.ca/hac/,
has a chapter on efficient implementations which might provide some
insight.

You can take advantage of the left FFF's by using the modular reduction
algorithm described in section 14.3.4 of the HAC.  This is good for the
case where the modulus is slightly less than a power of 2.  Or you can
take advantage of the right FFF's by using Montgomery exponentiation,
described in section 14.3.2 of the HAC and also in algorithm 14.94.
Montgomery multiplication uses a value m' = - m^(-1) mod b, where m is
the modulus and b is the bignum base, typically 2^32 or 2^64.  With these
moduli m' becomes 1, simplifying the calculations.

-
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]


RIAA turns against Hollings bill

2003-01-14 Thread Nomen Nescio
The New York Times is reporting at
http://www.nytimes.com/2003/01/14/technology/14CND-PIRACY.html that
the Recording Industry Association of America, along with two computer
and technology industry trade groups, has agreed not to seek new
government regulations to mandate technological controls for copyright
protection.  This appears to refer primarily to the Hollings bill,
the CBDTPA, which had already been struck a blow when Hollings lost his
committee chairmanship due to the Democrats losing Senate leadership.
Most observers see this latest step as being the last nail in the coffin
for the CBDTPA.

Some months ago there were those who were predicting that Trusted
Computing technology, as embodied in the TCPA and Palladium proposals,
would be mandated by the Hollings bill.  They said that all this talk of
"voluntary" implementations was just a smoke screen while the players
worked behind the scenes to pass laws that would mandate TCPA and
Palladium in their most restrictive forms.  It was said that Linux would
be banned, that computers would no longer be able to run software that
we can use today.  We would cease to be the real owners of our computers,
others would be "root" on them.  A whole host of calamaties were forecast.

How does this latest development change the picture?  If there is no
Hollings bill, does this mean that Trusted Computing will be voluntary,
as its proponents have always claimed?  And if we no longer have such
a threat of a mandated Trusted Computing technology, how bad is it for
the system to be offered in a free market?

Let technology companies decide whether to offer Palladium technology
on their computers or not.  Let content producers decide whether to use
Palladium to protect their content or not.  Let consumers decide whether
to purchase and enable Palladium on their systems or not.

Why is it so bad for people to freely make their own decisions about
how best to live their lives?  Cypherpunks of all people should be the
last to advocate limiting the choices of others.  Thankfully, it looks
like freedom may win this round, despite the efforts of cypherpunks and
"online freedom" advocates to eliminate this new technology option.

-
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]



Re: DeCSS, crypto, law, and economics

2003-01-07 Thread Nomen Nescio
John S. Denker writes:
> The main thing the industry really had at stake in
> this case is the "zone locking" aka "region code"
> system.

I don't see much evidence for this.  As you go on to admit, multi-region
players are easily available overseas.  You seem to be claiming that the
industry's main goal was to protect zone locking when that is already
being widely defeated.

Isn't it about a million times more probable that the industry's main
concern was PEOPLE RIPPING DVDS AND TRADING THE FILES?  Movies are
freely available on the net, just like MP3s, and the DeCSS software was
the initial technology that made ripping DVD's possible.  Many people
would rather get something for free than to pay for it, and DVD ripping
allows that for movies.  The MPAA obviously is afraid of following the
RIAA into oblivion.

-
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]



Hooray for TIA

2002-12-10 Thread Nomen Nescio
[I'm not happy with the tone of this, but I'm forwarding it as privacy
 politics is pretty clearly on topic... --Perry]

For years we cypherpunks have been telling you people that you are
responsible for protecting your own privacy.  Use cash for purchases, look
into offshore accounts, protect your online privacy with cryptography
and anonymizing proxies.  But did you listen?  No.  You thought to
trust the government.  You believed in transparency.  You passed laws,
for Freedom of Information, and Protection of Privacy, and Insurance
Accountability, and Fair Lending Practices.

And now the government has turned against you.  It's Total Information
Awareness program is being set up to collect data from every database
possible.  Medical records, financial data, favorite web sites and email
addresses, all will be brought together into a centralized office where
every detail can be studied in order to build a profile about you.
All those laws you passed, those government regulations, are being
bypassed, ignored, flushed away, all in the name of National Security.

Well, we fucking told you so.

And don't try blaming the people in charge.  You liberals are cursing
Bush, and Ashcroft, and Poindexter.  These laws were passed by the entire
U.S. Congress, Republicans and Democrats alike.  Representatives have
the full support of the American people; most were re-elected with
large margins.  It's not Bush and company who are at fault, it's the
whole idea that you can trust government to protect your privacy.

All that data out there has been begging to be used.  It was only a
matter of time.

And you know what?  It's good that this has happened.  Not only has
it shown the intellectual bankruptcy of trust-the-government privacy
advocates, it proves what cypherpunks have been saying all along, that
people must protect their own privacy.  The only way to keep your privacy
safe is to keep the data from getting out there in the first place.

Cypherpunks have consistently promoted two seemingly contradictory
ideas.  The first is that people should protect data about themselves.
The second is that they should have full access and usability for
data they acquire about others.  Cypherpunks have supported ideas like
Blacknet, and offshore data havens, places where data could be collected,
consolidated and sold irrespective of government regulations.  The same
encryption technologies which help people protect their privacy can be
used to bypass attempts by government to control the flow of data.

This two-pronged approach to the problem produces a sort of Darwinian
competition between privacy protectors and data collectors.  It's not
unlike the competition between code makers and code breakers, which has
led to amazing enhancements in cryptography technology over the past
few decades.  There is every reason to expect that a similar level of
improvement and innovation can and will eventually develop in privacy
protection and data management as these technologies continue to be
deployed.

But in the mean time, three cheers for TIA.  It's too bad that it's the
government doing it rather than a shadowy offshore agency with virtual
tentacles into the net, but the point is being made all the same.
Now more than ever, people need privacy technology.  Government is not
the answer.  It's time to start protecting ourselves, because nobody
else is going to do it for us.

-
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]



Re: patent free(?) anonymous credential system pre-print

2002-11-05 Thread Nomen Nescio
Stefan Brands writes regarding http://eprint.iacr.org/2002/151/:

> The paper shows some promise but, apart from being insecure, has other
> drawbacks that should be addressed:
>
> ... My work... introduced by myself... my MIT press book...
>
> In addition to various other drawbacks pointed out by of Dr. Adam Back
> (see [EMAIL PROTECTED]/msg02752.html),
> the proposal does not  offer a wallet-with-observer mode, discarding
> protection, anonymous recertification /  updating, multi-application
> certificates, etcetera.

And balanced against all these numerous shortcomings, there is one
inescapable, overwhelming fact:

THE AUTHORS ARE MAKING THE FRUITS OF THEIR LABOR AVAILABLE FREELY FOR
THE WORLD TO USE.

With all of your patents, and your writings, and your self-promotion,
how many people are using your certificates in the real world?  Think how
much you could have accomplished, how much of a difference you could have
made, if you had been willing to sacrifice the hope of great riches.
Instead you have followed in the footsteps of your mentor Chaum, and
both of you have withheld your talent from the world.

What is it about cash and credential systems that everyone who works
in the area thinks they should patent their results?  All you have
accomplished is to make sure that no implementations exist!  What good
are your great ideas if no one can use them?

Look at Chaum!  Is that where you want to be in 20 years?  Bitter and
barren?  Cut off from the cryptographic community?  Reduced to publishing
via the government patent office?

That's no life for a great mind.  Creativity demands interaction with
an active and vital intellectual community.  You have to give in order
to take.  Building walls around your intellectual property shuts others
out even as you shut yourself in.

If you really want to accomplish something meaningful, rather than
continuing to hype and shill for a system which no one can use without
entering into delicate financial negotiations, why not make it available
on some basis for people to experiment with?  Maybe a non-commercial,
open-source GPL implementation could be a starting point.  There is
considerable interest in reputation systems among the P2P community
and credentials could be a part of that.  You can still protect your
commercial interests while letting people get familiar with the technology
by making a non-commercial library available.

That's just one possibility.  The point is, your ideas are going nowhere
using your present strategy.  Either this technology won't be used at
all, or inferior but unrestricted implementations will be explored,
as in the recent work.  If you want things to happen differently, you
must change your strategy.

-
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]



Re: Cryptogram: Palladium Only for DRM

2002-09-18 Thread Nomen Nescio

Peter Biddle writes:
> Pd is designed to fail well - failures in SW design shouldn't result in
> compromised secrets, and compromised secrets shouldn't result in a BORE
> attack.

Could you say something about the sense in which Palladium achieves
BORE ("break once run everywhere") resistance?  It seems that although
Palladium is supposed to be able to provide content security (among
other things), a broken Palladium implementation would allow extracting
the content from the "virtual vault" where it is kept sealed.  In that
case the now-decrypted content can indeed run everywhere.

This seems to present an inconsistency between the claimed strength of the
system and the description of its security behavior.  This discrepancy
may be why Palladium critics like Ross Anderson charge that Microsoft
intends to implement "document revocation lists" which would let Palladium
systems seek out and destroy illicitly shared documents and even programs.

Some have claimed that Microsoft is talking out of both sides of its
mouth, promising the content industry that it will be protected against
BORE attacks, while assuring the security/privacy community that the
system is limited in its capabilities.  If you could clear up this
discrepancy that would be helpful.  Thanks...

-
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]



Re: Cryptographic privacy protection in TCPA

2002-09-01 Thread Nomen Nescio

It looks like Camenisch & Lysyanskaya are patenting their credential
system.  This is from the online patent applications database:

http://appft1.uspto.gov/netacgi/nph-Parser?Sect1=PTO2&Sect2=HITOFF&p=1&u=/netahtml/PTO/search-bool.html&r=1&f=G&l=50&co1=AND&d=PG01&s1=camenisch&OS=camenisch&RS=camenisch

> Non-transferable anonymous credential system with optional anonymity
> revocation
>
> Abstract
>
> The present invention relates to a method and system for securely
> proving ownership of pseudonymous or anonymous electronic credentials. A
> credential system is described consisting of users and organizations. An
> organization knows a user only by a pseudonym.  The pseudonyms of the
> same user, established for use with different organizations, cannot be
> linked. An organization can issue a credential to a pseudonym, and the
> corresponding user can prove possession of this credential to another
> organization that knows him under another pseudonym. During the prove of
> possession of the credential nothing besides the fact that he owns such
> a credential is revealed. A refinement of the credential system provides
> credentials for unlimited use, so called multiple-show credentials,
> and credentials for one-time use, so called one-show credentials.

Some of the claims seem a little broad, like this first one:

> 1. A method for establishing a pseudonym system by having a certificate
> authority accepting a user as a new participant in said pseudonym system,
> the method comprising the steps of: receiving a first public key provided
> by said user; verifying that said user is allowed to join the system;
> computing a credential by signing the first public key using a secret
> key owned by said certificate authority; publishing said first public
> key and said credential.

Wouldn't this general description cover most proposed credential systems
in the past, such as those by Chaum or Brands?

Does anyone know how to contact the PTO regarding proposed patents,
perhaps to point out prior art?

-
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]



Re: Palladium and malware

2002-08-31 Thread Nomen Nescio

Bill Frantz writes, regarding the possibility that the Palladium
architecture could be designed to resist the use of encrypted 
code:

> All general purpose computers require a way to move data space to code
> space to support compilation.

Well, this is usually done by storing the data to the disk, and
then later loading it as a program file.  It does not prevent data
and code memory from being distinct, which was the proposal for how
Palladium could reduce the risk of being used to run encrypted code.
If a Palladium program was forced to go through the disk, that is, to
load data, decrypt it, store it to the disk, and then load it as code,
then that would provide a means to get access to the unencrypted code,
defeating the goal of keeping the code within the "vault".

> Even if you don't allow compilation, most
> modern systems have enough different powerful scripting languages that
> interpretation is sufficient to support viruses.

It's not clear why these languages would use the Palladium features and
run their scripts in the shielded mode.  But you're right that if they
did, this could provide a mechanism for disassembly-resistant code.

-
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]



Re: Palladium and malware

2002-08-30 Thread Nomen Nescio

Paul Crowley asks: > I'm informed that malware authors often go to some
lengths to prevent > their software from being disassembled.  Could they
use Palladium for > this end?  Are there any ways in which the facilities
that Palladium > and TCPA provide could be useful to a malware author
who wants to > frustrate legitimate attempts to understand and defeat
their software?

Palladium provides a "curtained" memory area where software is supposed to
be relatively free from being accessed or modified.  (Apparently it can be
configured to be debugged when in this area by the use of "test keys".)
If disassembling a program requires access to it in memory, then this
curtained memory region could present an obstacle to disassembling.

However in most cases the memory would be loaded from the disk so having
access to the program on disk would allow you to disassemble it just as
well as if it were in memory.  From what has been said about Palladium,
it will not support encrypted programs.

However that might not stop a determined malware author from having the
program encrypt itself when it first runs (using the "virtual vault"
concept) and store the encrypted version on the disk, deleting the
original plaintext version.  The Palladium vault technology would
then make it impossible for any other software to decrypt that data.
The malware might not be able to use the regular Palladium program loader
to run its encrypted portion, but conceivably it could "manually" load
that encrypted data into the curtained area, decrypt it using a key
accessible only to itself, and then run.

This would still leave the program vulnerable until the first time it
runs, but afterwards it would be impossible to get at the program text
in the clear.

A program could reduce its window of vulnerability if it were distributed
in encrypted form, using a key that would be provided by a remote server
- which could even be any other infected computer!  The program stub
would start up, use Palladium attestation to connect reliably to another
virus-corrupted instance of itself on the net, and receive a global,
system-wide key.  This key would be kept locked in the "virtual vault"
and would decrypt the remainder of the program, which could then run in
the curtained area.  Even if all instances of the virus shared the same
key or set of keys, it would be impossible for non-virus programs or
programmers to get access to the key except by hacking their hardware,
scraping out a key, and creating a virtual Palladium system.

So the main question at this point is how program code and/or data gets
loaded into the curtained area, and whether it would be possible to
load encrypted data into that area, decrypt it and then run it as code.
There is a computer design called the Harvard architecture which has a
strict separation between code and data space, and conceivably Palladium
could use a similar approach to make it impossible to run decrypted code.
Adopting this approach would add credibility to Microsoft's promises
not to use Palladium for software copy protection.  But if they don't
go to such an extreme, it is likely that Palladium would allow the use
of various techniques to help malware hide from its opponents.

-
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]



Re: Cryptographic privacy protection in TCPA

2002-08-28 Thread Nomen Nescio

Carl Ellison suggested an alternate way that TCPA could work to allow
for revoking virtualized TPMs without the privacy problems associated
with the present systems, and the technical problems of the elaborate
cryptographic methods.

Consider first the simplest possible method, which is just to put a
single signature key in each TPM and allow the TPM to use that to sign
its messages on the net.  This is reliable and allows TPM keys to be
revoked, but it obviously offers no privacy.  Every usage of a TPM key
can be correlated as coming from a single system.

TCPA fixed this by adding a trusted third party, the "Identity CA" who
would be the only one to see the TPM key.  But Carl offers a different
solution.

Instead of burning only one key into the TPM, burn several.  Maybe even
a hundred.  And let these keys be shared with other TPMs.  Each TPM has
many keys, and each key has copies in many TPMs.

Now let the TPMs use their various keys to identify themselves in
transactions on the net.  Because each key belongs to many different
TPMs, and the set of TPMs varies for each key, this protects privacy.
Any given usage of a key can be narrowed down only to a large set of
TPMs that possess that key.

If a key is misused, i.e. "scraped" out of the TPM and used to create a
virtualized, rule-breaking software TPM, it can be revoked.  This means
that all the TPMs that share that one key lose the use of that key.
But it doesn't matter much, because they each have many more they can use.
Since it is expected that only a small percentage of TPMs will ever need
their keys revoked, most TPMs should always have plenty of keys to use.

One problem is that a virtualized TPM which loses one of its keys will
still have others that it can use.  Eventually those keys will also be
recognized as being mis-used and be revoked as well.  But it may take
quite a while before all the keys on its list are exhausted.

To fix this, Carl suggests that the TPM manufacturer keep a list of all
the public keys that are in each TPM.  Then when a particular TPM has
some substantial fraction of its keys revoked, that would be a sign that
the TPM itself had been virtualized and all the rest of the keys could be
immediately revoked.  The precise threshold for this would depend on the
details of the system, the number of keys per TPM, the number of TPMs that
share a key, the percentage of revoked keys, etc.  But it should not be
necessary to allow each TPM to go through its entire repertoire of keys,
one at a time, before a virtualized TPM can be removed from the system.

Carl indicated that he suggested this alternative early in the TCPA
planning process, but it was not accepted.  It does seem that while
the system has advantages, in some ways it shares the problems of the
alternatives.  It provides privacy, but not complete privacy, not as
much as the cryptographic schemes.  And it provides security to the TPM
issuers, but not complete security, not as much as the Privacy CA method.
In this way it can be seen as a compromise.  Often, compromise solutions
are perceived more in terms of their disadvantages than their benefits.

-
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]



Re: Chaum's unpatented ecash scheme

2002-08-22 Thread Nomen Nescio

Ben Laurie writes:

> Note that the scheme as described (and corrected) is vulnerable to 
> marking by the bank, and so is not anonymous. This is discussed and 
> fixed in my paper on Lucre 
> (http://anoncvs.aldigital.co.uk/lucre/theory2.pdf).

Actually the scheme described based on Chaum's talk (corrected for
probable typos) is essentially what you describe in your paper as the
Type II Defence, in section 5.  Your analysis shows that it is not
vulnerable to marking and is anonymous.

Speaking of anonymous, you should give credit in your paper to Anonymous
for discovering the possibility of marking Lucre coins, in a coderpunks
posting at
http://www.mail-archive.com/coderpunks@toad.com/msg02186.html, and for
inventing the Type II Defence, both in the posting above and amplifed
at http://www.mail-archive.com/coderpunks@toad.com/msg02323.html.

It may seem pointless to credit anonymous postings, but it makes the
historical record more clear.

-
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]



Chaum's unpatented ecash scheme

2002-08-20 Thread Nomen Nescio

David Chaum gave a talk at the Crypto 2002 conference recently in which
he briefly presented a number of interesting ideas, including an approach
to digital cash which he himself said would "avoid the ecash patents".

The diagram he showed was as follows:


Optimistic Authenticator

 z = x^s

Payer f(m)^a z^b Bank
  ->

[f(m)^a z^b]^s
  <-

   m, f(m)^s
  ->


It's hard to figure out what this means, but it bears resemblance to a
scheme discussed on the Coderpunks list in 1999, a variant on a blinding
method developed by David Wagner.  See
http://www.mail-archive.com/coderpunks@toad.com/msg02323.html for a
description, with a sketch of a proof of blindness at
http://www.mail-archive.com/coderpunks@toad.com/msg02387.html and
http://www.mail-archive.com/coderpunks@toad.com/msg02388.html.

In Chaum's diagram it is not clear which parts of the key are private and
which public, although z is presumably public.  Since the bank's action
is apparently to raise to the s power, s must be secret.  That suggests
that x is public.  However Chaum's system seems to require dividing by
(z^b)^s in order to unblind the value, and if s is secret, that doesn't
seem possible.

In Wagner's scheme everything was like this except that the bank's key
would be expressed as x = z^s, again with x and z public and s secret.
f(m) would be a one-way function, which gets doubly-blinded by being
raised to the a power and multiplied by z^b, where a and b are randomly
chosen blinding factors.  The bank raises this to its secret power s,
and the user unblinds to form f(m)^s.  To later deposit the coin he does
as in the third step, sending m and f(m)^s to the bank.

For the unblinding, the user can divide by (z^b)^s, which equals z^(b*s),
which equals (z^s)^b, which equals x^b.  Since x is public and the user
chose b, he can unblind the value.  Maybe the transcription above of the
Chaum scheme had a typo and it was actually similar to the Wagner method.

Chaum commented that the payer does not receive a signature in this
system, and that he doesn't need one because he is protected against
misbehavior by the bank.  This is apparently where the scheme gets
its name.

-
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]



Re: adding noise blob to data before signing

2002-08-10 Thread Nomen Nescio

Eugen Leitl asked:
> 1) What's the name of the technique of salting/padding an small integer 
>I'm signing with random data?

You shouldn't need to salt/pad with random data, fixed data should be
OK.

> 2) If I'm signing above short (~1 kBit) sequences, can I sign them 
>directly, or am I supposed to hash them first? (i.e. does a presence
>of an essentially fixed field weaken the signature)

Derek Atkins replied:
> It depends on the signature algorithm.  With RSA you can sign any
> message "directly" if said message is smaller than the public key size
> (N).  DSA, however, requires the use of a hash.

Actually, depending on the data being signed, it can be important to
hash for RSA.  After all, RSA is existentially forgeable: anyone can
forge a signature on a *random* value (if C=M^e mod n, then M is a
signature on C).  They might be able to try some large number of sigs
until they got a random value which looked enough like legitimate data
to be accepted - especially possible if the 1kbit value being signed
holds dense, random-ish binary data.

-
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]



Re: Montgomery Multiplication

2002-07-04 Thread Nomen Nescio

On Tue, 2 Jul 2002, Damien O'Rourke wrote:

> I was just wondering if anyone knew where to get a good explanation of
> Montgomery multiplication for the non-mathematician?  I have a fair bit
> of maths but not what is needed to understand his paper.

Bear replied:

> Montgomery Multiplication is explained for the computer scientist
> in Knuth, _Seminumerical Methods_.
>
> Briefly: The chinese remainder theorem proves that for any set
> A1...AN of integers with no common divisors, any integer X which is
> less than their product can be represented as a series of remainders
> X1...XN, where Xn is equal to X modulo An.
>
> if you're using the same set of integers with no common divisors
> A1...AN to represent two integers X and Y, you have a pair of series
> of remainders X1...XN and Y1...YN.
>
> Montgomery proved that Z, the product of X and Y, if it's in the
> representable range, is Z1...ZN where Zn equals (Xn * Yn) mod An.

That's not Montgomery multiplication; that's what Knuth called modular
arithmetic, described in section 4.3.2 of Seminumerical Methods.

Montgomery multiplication is well described at
http://www.ciphergoth.org/writing/postings/news-992.txt, as Paul Crowley
posted.

-
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]



Re: Ross's TCPA paper

2002-06-24 Thread Nomen Nescio

Ross Anderson writes:

> During my investigations into TCPA, I learned that HP has started a
> development program to produce a TCPA-compliant version of GNU/linux.
> I couldn't figure out how they planned to make money out of this. On
> Thursday, at the Open Source Software Economics conference, I figured
> out how they might.
> ...
> The business model, I believe, is this. HP will not dispute that the
> resulting `pruned code' is covered by the GPL. You will be able to
> download it, compile it, check it against the binary, and do what you
> like with it. However, to make it into TCPA-linux, to run it on a
> TCPA-enabled machine in privileged mode, you need more than the code.
> You need a valid signature on the binary, plus a cert to use the TCPA
> PKI. That will cost you money (if not at first, then eventually).

H Not clear that this really works to make money.  The GPL
allows everyone to redistribute HP's software verbatim, right?  So a
cert on one copy of the software will work on everyone's.  How can HP
make money on a product that everyone can copy freely, when they can
all share the same cert?

It's true that modified versions of the software would not be able to
use that cert, and it would no doubt be expensive to get a new cert for
the modified software.  But that still gives HP no monopoly on selling
or supporting its own version.  Anyone can step in and do that.

Is the cert itself supposed to be somehow copyrighted?  Kept secret?
Will it be illegal to publish the cert, to share it with someone else?
This seems pretty questionable both in terms of copyright law (since
a cert is a functional component) and in terms of the GPL (which would
arguably cover the cert and forbid restrictively licensing it).

It seems more likely that the real purpose is to bring the benefits of
TCPA to the Linux world.  As an innovator in this technology HP will gain
in reputation and be the source that people turn to for development and
support in this growing area.  The key to making money from open source
is reputation.  Being first makes good economic sense.  You don't need
conspiracy theories.

-
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]



Re: Ross's TCPA paper

2002-06-23 Thread Nomen Nescio

Lucky Green writes regarding Ross Anderson's paper at:
http://www.ftp.cl.cam.ac.uk/ftp/users/rja14/toulouse.pdf

> I must confess that after reading the paper I am quite relieved to
> finally have solid confirmation that at least one other person has
> realized (outside the authors and proponents of the bill) that the
> Hollings bill, while failing to mention TCPA anywhere in the text of the
> bill, was written with the specific technology provided by the TCPA in
> mind for the purpose of mandating the inclusion of this technology in
> all future general-purpose computing platforms, now that the technology
> has been tested, is ready to ship, and the BIOS vendors are on side.

It's an interesting claim, but there is only one small problem.
Neither Ross Anderson nor Lucky Green offers any evidence that the TCPA
(http://www.trustedcomputing.org) is being designed for the support of
digital rights management (DRM) applications.

In fact if you look at the documents on the TCPA web site you see much
discussion of applications such as platform-based ecommerce (so that
even if a user's keys get stolen they can't be used on another PC),
securing corporate networks (assuring that each workstation is running
an IT-approved configuration), detecting viruses, and enhancing the
security of VPNs.

DRM is not mentioned.

Is the claim by Ross and Lucky that the TCPA is a fraud, secretly designed
for the purpose of supporting DRM while using the applications above
merely as a cover to hide their true purposes?  If so, shouldn't we expect
to see the media content companies as supporters of this effort?  But the
membership list at http://www.trustedcomputing.org/tcpaasp4/members.asp
shows none of the usual suspects.  Disney's not there.  Sony's not there.
No Viacom, no AOL/Time/Warner, no News Corp.  The members are all
technology companies, including crypto companies like RSA, Verisign
and nCipher.

Contrast this for example with the Brodcast Protection Discussion
Group whose ongoing efforts are being monitored by the EFF at
http://www.eff.org/IP/Video/HDTV/.  There you do find the big media
companies.  That effort is plainly aimed at protecting information and
supporting DRM, so it makes sense that the companies most interested in
those goals are involved.

But with the TCPA, the players are completely different.  And unlike
with the BPDG, the rationale being offered is not based on DRM but on
improving the trustworthiness of software for many applications.

Ross and Lucky should justify their claims to the community in general
and to the members of the TCPA in particular.  If you're going to make
accusations, you are obliged to offer evidence.  Is the TCPA really, as
they claim, a secretive effort to get DRM hardware into consumer PCs?
Or is it, as the documents on the web site claim, a general effort to
improve the security in systems and to provide new capabilities for
improving the trustworthiness of computing platforms?

-
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]



Re: Shortcut digital signature verification failure

2002-06-22 Thread Nomen Nescio

David Wagner describes a trick from Dan Bernstein to speed up
RSA signature verification with e = 3:

> One of the nicest ideas from his work is easy to describe.  In plain
> RSA, s is a valid signature on m if H(m) = s^3 (mod n).  Now suppose we
> ask the signer to also supply an integer k such that 0 <= s^3 - kn < n;
> clearly this can't hurt security, as k can be publicly computed from s.
> Then the recipient can efficiently verify the validity of the claimed
> signature (t,k) on m as follows: verify that 0 <= s^3 - kn < n; then

So the signer supplies s and k.  And our first step is to verify that
0 <= s^3 - kn < n.  But given that we've computed S = s^3 - kn and it
is in this range, isn't it the case that S = s^3 mod n?  And so we can
test test that H(m) = S = s^3 mod n and that verifies the signature
directly.

> secretly pick a random 31-bit prime p, compute t' = s^3 mod p, n' =
> n mod p, k' = k mod p, h' = H(m) mod p, and verify that t' - k'n' = h'
> (mod p).

-
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]



Re: Lucky's 1024-bit post [was: RE: objectivity and factoring analysis

2002-05-13 Thread Nomen Nescio

Wei Dai writes:
> Using a factor base size of 10^9, in the relationship finding phase you
> would have to check the smoothness of 2^89 numbers, each around 46 bits
> long. (See Frog3's analysis posted at
> http://www.mail-archive.com/cryptography%40wasabisystems.com/msg01833.html.  
> Those numbers look correct to me.)  If you assume a chip that can check
> one number per microsecond, you would need 10^13 chips to be able to
> complete the relationship finding phase in 4 months. Even at one dollar
> per chip this would cost ten trillion dollars (approximately the U.S. 
> GDP).

This is probably not the right way to approach the problem.  Bernstein's
relation-finding proposal to directly use ECM on each value, while
asymptotically superior to conventional sieving, is unlikely to be
cost-effective for 1024 bit keys.  Better to extrapolate from the recent
sieving results.

http://citeseer.nj.nec.com/cavallar00factorization.html is the paper
from Eurocrypt 2000 describing the first 512 bit RSA factorization.
The relation-finding phase took about 8000 MIPS years.  Based on the
conventional asymptotic formula, doing the work for a 1024 bit key
should take about 10^7 times as long or 80 billion MIPS years.

For about $200 you can buy a 1000 MIPS CPU, and the memory needed for
sieving is probably another couple of hundred dollars.  So call it $500
to get a computer that can sieve 1000 MIPS years in a year.

If we are willing to take one year to generate the relations then
($500 / 1000) x 8 x 10^10 is $40 billion dollars, used to buy
approximately 80 million cpu+memory combinations.  This will generate
the relations to break a 1024 bit key in a year.  If you need it in less
time you can spend proportionately more.  A $400 billion dollare machine
could generate the relations in about a month.  This would be about 20%
of the current annual U.S. federal government budget.

However if you were limited to a $1 billion budget as the matrix
solver estimate assumed, the machine would take 40 years to generate
the relations.

> BTW, if we assume one watt per chip, the machine would consume 87 trillion
> kWh of eletricity per year. The U.S. electricity production was only 3.678 
> trillion kWh in 1999.

The $40 billion, 1-year sieving machine draws on the order of 10 watts
per CPU so would draw about 800 megawatts in total, adequately supplied
by a dedicated nuclear reactor.

-
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]



ecash news: Brands & credentica.com

2002-03-29 Thread Nomen Nescio

For cpunxnews/cryptography:

Seems people missed this anonymous note about Dr Stefan Brands new
company http://www.credentica.com on cypherpunks -- interesting news
-- will Credentica persue ecash, private credentials, more liberal
licensing terms than digicash and ecash-technologies/infospace.

(Brands ecash and credential patent suite is the only major contender
to Chaum's patent suite.  Chaum's patent suite was recently acquired
by Infospace for an undisclosed amount from ecash-technologies which
earlier bought the patents when digicash filed for chapter 11
bankruptcy.)

>
To: [EMAIL PROTECTED]
Cc: [EMAIL PROTECTED]
Cc: [EMAIL PROTECTED]
Subject: Brands credentica (Re: [Tsg] Micropayments & VISA?)

Your information is out of date: Brands is no longer at ZKS, last
month a new company was launched in which Brands is involved, see
www.credentica.com, the rights are not tangled up in any way (legal
separation, all rights cleared).

Paul Holman wrote:
> [...]  There are possible alternatives; Brands' patents, now tied up
> at ZKS, and other schemes which try to body swerve Chaum, but
> nothing comforting.
<

-
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]



Re: Bernstein's NFS machine

2002-03-04 Thread Nomen Nescio

James Donald writes:
> On Tue, Feb 26, 2002 at 02:04:16AM -, Frog3 wrote:
> > The cost [To factor RSA 1024] is the need to build a 
> > machine that can do 53 billion simultaneous, independent 
> > ECM factorizations for smoothness testing. It's not clear 
> > how amenable this would be to hardware implementation.
> >
> > A time of 2^71 is considerably less threatening than 2^53.
>
> If I understand frog3's numbers correctly:
>
> If one builds extraordinarily massive hardware capable of
> dowing 53 billion simultaneous independent ECM
> factorizations, Bernstein's method wil take 2^71 steps.
>
> Assuming that the massively parallel hardware does fifty
> billion factorizations each microsecond, then it will take 
> Bernstein's super duper hardware about one hundred million
> years to factor an RSA 1024 modulus. 

No, this is not quite right.  The 2^71 is the cost in terms of elementary
operations (add, xor, etc.).  This is based on 2^53 ECM factorizations
per machine times 2^18 operations per factorization.

James' quoted time would be correct if the machine could do 50 billion
*operations* per microsecond (a clock rate of 50,000,000 gigahertz
(50 petahertz), compared to 1-2 gigahertz available today).  This fast
machine would then take 100 million years to break a 1024 bit key.

Even though these are "back of the envelope" calculations which ignore
o(1) terms that could theoretically be negative, the basic principles seem
sound.  The need to do 2^89 tests to get enough relations for a factor base
of 2^36 is based on the known fraction of multi-hundred bit numbers that
are going to be smooth.  This value doesn't have much "wiggle room".  You
could try to use a smaller factor base, but the size of the values to be
tested for smoothness is going to be in the hundreds of bits, and reducing
the factor base will make it even harder to find smooth values.

The 2^18 estimate for the cost of the ECM smoothness test will likewise
be hard to improve on significantly.  In addition, with a factor base of
size 2^36 and testing numbers up to ten times longer, each ECM factorizer
will have to do approximately 10 factorizations before it can determine
smoothness.

Even with the uncertainties, this calculation seems to be strong enough
to say that this machine cannot pose a threat to 1024 bit keys using
near-term technology.  You can assume impossibly large numbers of an
impossibly fast machine, and it still takes an impossibly large time.

-
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]



Re: Bernstein's NFS machine

2002-03-03 Thread Nomen Nescio

David Wagner writes:
> Bernstein's analysis is based on space*time as your cost metric.
> What happens if we assume that space comes for free, and we use simply
> time as our cost metric?  Do his techniques lead to an improvement in
> this case?

Bernstein basically treats memory and processing elements as
interchangeable to a first approximation.  After all, it's just different
ways of laying out silicon.  So assuming that space comes for free is
equivalent to assuming that you have an infinite number of processors
to bring to bear on the problem.

> It looks to me like there is no improvement in the first phase, but
> there is some improvement in the second phase (reduction in time from
> B^2 to B^1.5).

If you had an unlimited number of processors for the first phase, and
you have X number of values to check for smoothness, then you can use X
processors and run one test on each value, completing the whole thing in
time L^o(1).  This does not reduce Bernstein's cost metric but it would
reduce the time considerably.  I don't think such a speedup is possible
with the sieving approach.

However this is not physically reasonable, as the number of values to
be tested for smoothness is approximately L^2, which would be on the
order of 2^90 for a 1024 bit key.  If each cell were .01 microns on a
side you would still need 100,000 square kilometers of chip area.  So
this extrapolation is not very meaningful.

-
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]



Re: Bernstein's NFS machine

2002-03-02 Thread Nomen Nescio

More analysis of Dan Bernstein's factoring machine from
http://cr.yp.to/papers.html#nfscircuit.;

The NFS algorithm has two phases.  The first searches for coefficients
(a,b) from some interval which are relatively prime and which satisfy
two smoothness bounds.  The smoothness is with respect to a factor base
consisting of all primes less than some bound.  (Actually there may be
two or more bounds used for different tests, but that complication will
be ignored here.)  Each success produces one relation and will be one
row of a matrix whose columns correspond to the primes in the factor
base.

Once enough relations are collected (more rows than columns) the second
phase begins.  This involves looking for linear dependencies among the
rows of the matrix, where the math is in GF(2).  Once a dependency is
found, the corresponding rows can be combined to produce a value with
two different square roots, which with good probability will lead to
a factorization of n.

Dan Bernstein proposes methods to significantly reduce the cost (defined
as space times time) of both phases.

L is defined as exp(log(n)^(1/3) * log(log(n))^(2/3)), where n is the
number to be factored.  It is a key parameter for the work cost of the
NFS class of algorithms.

n  L
-
 2^512   2^33
 2^1024  2^45
 2^1536  2^54
 2^2048  2^61

Let E represent the bound on the (a,b) coefficient values which are
searched.  Then E^2 values will be checked for relative primality and
smoothness.  Let B represent the bounds on the factor base.  A smooth
value is one for which all of its factors are less than B.

In previous work, sieving is used to test for smoothness, which is in
part where the Number Field Sieve algorithm gets its name.  Sieving
E^2 values over a factor base of size B takes roughly E^2 log log B
time and B space.  We will ignore the log log B factor and just say
E^2 and B space, for a total work factor of B*E^2.

With a factor base of size B, roughly B relations have to be found.
Then a sparse B by B matrix must be solved in the second phase.
Using conventional algorithms this solution takes roughly B^2 work on
a machine that has B space.  The total work factor is B^3.

For optimum balance, the work factor of these two phases is set equal,
giving B^3 = B*E^2, or B=E.  It is also necessary that E be large
enough to produce at least B relations.  This leads to the solution
E = B = L^0.961.  The corresponding work factor is this value cubed,
or L^2.883.  (Dan Bernstein gives a slightly lower figure due to an
improvement by Don Coppersmith.)

Bernstein improves on both of these phases.  He points out that for
sufficiently large n, it will be less work to determine smoothness by
simply trying to factor each value using the Elliptic Curve factoring
method (ECM).  This is the best factoring method known for finding
relatively small factors, as is required here.  Attempting to factor
E^2 values over a factor base of size B takes time proportional to
E^2 times a function of B which is larger than that in the sieve
case, but still asymptotically small compared to E^2.  So the time
is basically proportional to E^2 as with the sieve.

The savings comes in the space.  The sieve requires an array to hold
the primes in the factor base, and an array to represent the values
being sieved.  The most efficient approach is to set these two arrays
to roughly the same size, breaking the input into pieces of size B.
This does not slow the algorithm but allows it to run in space B as
assumed above.

In contrast, the ECM algorithm requires no large storage spaces.
It does not have to store the factor base or any representation of a
large block of numbers to be checked.  It simply runs the ECM factoring
algorithm on each value to be checked until it either finds a factor or
times out.  If it finds one, it divides it out and repeats the process
with the residue.  Eventually the residue is small enough that we know
the number is smooth, or the algorithm fails indicating that the value
is not smooth.  Storage requirements are minimal.  Based on this, the ECM
approach takes time proportional to E^2 and space essentially a constant,
for a total work of E^2.  This is compared with B*E^2 for the sieve.

Bernstein also improves on the second phase, finding a dependency among
the rows of the matrix.  It still requires space of size B to hold the
sparse matrix of size B by B.  But by making the matrix elements be active
instead of dumb memory cells, he can accelerate the matrix operations
that are necessary.  The result is that finding the dependencies is
reduced to taking time B^1.5 rather than B^2.  The total work is then
B^2.5.

For optimality these two phases are balanced with E^2 = B^2.5 or
E=B^1.25.  Incorporating the requirement that E be big enough to
generate the necessary B relations, the solution is E=L^0.988 and
B=L^0.790.  The total work is E^2 or L^1.976.  This is compared to the
L^2.883 value above, a significant savings.

It is interesting t

Re: CFP: PKI research workshop

2001-12-26 Thread Nomen Nescio

PHB:
> PKI is in widespread use, it is just not that noticeable when you use it.
> This is how it should be. SSL is widely used to secure internet payment
> transactions.

PM:
> HTTPS SSL does not use PKI.

Could someone define PKI (beyond just what it stands for, Public Key
Infrastructure)?  It looks like you are all talking past each other by
using the term to mean different things.



-
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]



Re: "Pirate Utopia," FEED, February 20, 2001

2001-09-24 Thread Nomen Nescio

Adam Back wrote:
> To elaborate on this slightly.  There are inherent reasons why
> steganography is harder than encryption: the arms race of hiding data
> in noise is based on which side (the hider vs the detecter) has the
> best understanding of the characteristics of the host signal.  The
> problem is the host signal is not something with clear definition,
> what is known is primarily empirical statistical analysis.
> Manipulating signals with noise in them to replace noise with the
> stego text is not so hard, but knowing and modeling the signal and the
> source noise is not a solvable problem.

If you read the report at
http://www.citi.umich.edu/techreports/reports/citi-tr-01-11.ps.gz you
will find that the authors, Niels Provos and Peter Honeyman, you find
that they actually found a great many images with statistical indication
of steganographic content: "After processing the two million images
with Stegdetect, we find that over 1% of all images seem to contain
hidden content."  That is, these images seemed to depart from normal
statistics to a significant degree.

The question is whether these are random variations from the norm or
are they actual embedded content?  This is the factor which the analysis
above seems to neglect.  Any statistical test is going to have a certain
number of false positives.  This provides a background of "noise"
(that is, false positives) in which a true signal (a true positive,
an image with actual steganographic content) can hide.

The Stegdetect paper proceeded to further analyze the 2+ images by
looking for passwords that would produce meaningful messages from the
hypothesized hidden content, via dictionary attack.  No valid passwords
were found, and the authors concluded therefore that these were all
false positives.  This does not seem to be a fully supported conclusion.



-
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]



Re: "Pirate Utopia," FEED, February 20, 2001

2001-09-21 Thread Nomen Nescio

Adam Back writes:
> Also it's interesting to note that it appears from Niels Provos and
> Peter Honeymans paper that none of the currently available stego
> encoding programs are secure.  They have broken them all (at least I
> recognise the main stego programs available in their list of systems
> their tools can attack), and it appears that all of the stego encoders
> are naive attempts.

No, Provos' own system, Outguess, www.outguess.org, is secure in the
latest version.  At least, he can't break it.  It remains to be seen
whether anyone else can.  See the papers on that site.



-
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]



Re: chip-level randomness?

2001-09-20 Thread Nomen Nescio

Ted Tso writes:
> It turns out that with the Intel 810 RNG, it's even worse because
> there's no way to bypass the hardware "whitening" which the 810 chip
> uses.  Hence, if the 810 random number generator fails, and starts
> sending something that's close to a pure 60 HZ sine wave to the
> whitening circuitry, it may be very difficult to detect that this has
> happened.

The "whitener" is just a slightly improved von Neumann bias remover.

The tradition vN state machine looks at pairs of bits and does something
like this:

0 0  ->  discard
0 1  ->  output 1
1 0  ->  output 0
1 1  ->  discard

This removes a static bias.  I.e. if you are producing say 55% 0's
and 45% 1's, after this whitener you will output 50% 0's and 1's.
However it is at the cost of discarding a considerable fraction of
the bits.

The improved version in the Intel RNG has a 3 bit window and this
lets it remove the bias just as well while discarding somewhat
fewer bits.

If the internal circuitry did output a 60Hz sine wave then regularities
would still be visible after this kind of whitener.  It is a rather
mild cleanup of the signal.

It doesn't seem right to object to them including a bias remover.
They have done other things to reduce bias.  For example they use a pair
of thermal resistors located next to each other on the chip and use the
difference of the values from each of them, to reduce sensitivity to
environmental influences.  This reduces bias, but should they have left
the differencing out so that you could more easily measure a possible
influence?

Suppose the voltage were to drop to this part of the chip; the
differencing will hide this fact and prevent you from detecting that maybe
some other parts aren't working well.  Here is an example of a possible
partial-failure mode which the chip internal design will tend to hide.
It should not be considered a design flaw for the chip to do this.
It improves the random numbers which the chip produces.  And similarly,
the digital bias remover does the same thing.

The bottom line is the quality of the random numbers produced by the
device.  It is designed internally to withstand various kinds of noise
and bias, so as to produce the best random numbers possible.

See http://www.cryptography.com/intelRNG.pdf for information on the
design of the RNG.  See if you can identify a plausible failure mode
which could be detected if the whitener was not present, but which will
be undetectable with the vN whitener in place.



-
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]