Elliptic Curve Cryptography algorithm unencumbered?
cwright_bl...@zoinks.ne.mediaone.net
I have a simple question: Is ECC unencumbered by patents or other
restrictions that would require me to pay someone to use it, as is the
case now for RC4? I'v been checking out Certicom's web page, but I
find nothing to confirm either way. The one encouraging sign is that
it's being incorporated into various standards, but that doesn't
necessarily imply that it's license-free....
Thanks,
Charles R. Wright
(Delete the _blahblahblah from my username to reply)
George Barwood
cwright_bl...@zoinks.ne.mediaone.net wrote:
>I have a simple question: Is ECC unencumbered by patents or other
>restrictions that would require me to pay someone to use it, as is the
>case now for RC4? I'v been checking out Certicom's web page, but I
>find nothing to confirm either way. The one encouraging sign is that
>it's being incorporated into various standards, but that doesn't
>necessarily imply that it's license-free....
As far as is known, ECC is relatively unencumbered. You should be able
to avoid the patents. Watch out for point compression though, also
Nyberg-Rueppel signatures.
For the info I managed to find,see section 17 of my FAQ at
http://ds.dial.pipex.com/george.barwood/ec_faq.htm
George Barwood
bo...@rsa.com
george....@dial.pipex.com (George Barwood) wrote:
> On 1 Oct 1998 16:41:39 GMT,
> cwright_bl...@zoinks.ne.mediaone.net wrote:
>
> >I have a simple question: Is ECC unencumbered by patents or other
> >restrictions that would require me to pay someone to use it, as is the
> >case now for RC4? I'v been checking out Certicom's web page, but I
> >find nothing to confirm either way. The one encouraging sign is that
> >it's being incorporated into various standards, but that doesn't
> >necessarily imply that it's license-free....
>
> As far as is known, ECC is relatively unencumbered. You should be able
> to avoid the patents. Watch out for point compression though, also
> Nyberg-Rueppel signatures.
There have been some specialized instances which have been patented.
e.g.
ECC over prime fields close to a power of 2, i.e. 2^n + k for small k
ECC over GF(2^r) for certain representations of the underlying field and
certain ways of doing the arithmetic
I also believe Koblitz curves may have a patent pending.
-----------== Posted via Deja News, The Discussion Network ==----------
http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own
Ted Rallis
The straghtforward answer is no, ECC is not unencumbered (To say it is
encumbered sounds so negative...) by patents or patents pending.
Certicom's letter to the P1363 working group regarding ECC may answer your
question in more detail:
http://grouper.ieee.org/groups/1363/letters/Certicom.txt.
Ted Rallis
Certicom Corp.
cwright_bl...@zoinks.ne.mediaone.net wrote:
> Hello,
>
> I have a simple question: Is ECC unencumbered by patents or other
> restrictions that would require me to pay someone to use it, as is the
> case now for RC4? I'v been checking out Certicom's web page, but I
> find nothing to confirm either way. The one encouraging sign is that
> it's being incorporated into various standards, but that doesn't
> necessarily imply that it's license-free....
>
Eric W Braeden
I believe in IP (Intellectual Property) rights, but it looks
like Certicom is just getting in the way of progress. Just
another hog at the trough trying to build a gravy train.
"Encumbered" IS the correct word!!!
Eric
Ted Rallis wrote in message <3613EA58...@certicom.com>...
John Savard
>I have a simple question: Is ECC unencumbered by patents or other
>restrictions that would require me to pay someone to use it, as is the
>case now for RC4?
The short (and somewhat oversimplified) answer is that while using
elliptic curves in cryptography is not _itself_ patented, to do so you
may need to use certain techniques for doing efficient elliptic curve
arithmetic which _are_ patented.
John Savard
http://members.xoom.com/quadibloc/index.html
Ted Rallis
consideration of the fact that I work for Certicom. Thus my response appears to
be company pandering which is against this group's spirit. My own interests in
reading this group is education. At the same time the preceding message demands
a response. Apologies to the offended.]
Hi Eric,
With respect I must disagree.
Certicom Corp. is not inhibiting 'progress'. Our team of top ECC experts have
worked for thirteen years (and counting) to perfect and advocate ECC
technology. Some of the obvious benefits of this are the ANSI and IEEE ECC
standards (which we wrote).
If you interpret this as an inhibition you must be concerned that your
independent implementation may collide with our interests. Yes, we have
intellectual investments to protect. At the same time we do not wish to inhibit
your ECC interests. I think you will be very surprised at how little we ask in
compensation for our years of research. You see, both Certicom as a company and
myself personally wish to be more than 'reasonable and non-discriminatory' in
licensing out technologies. We explicitly and in a premeditated fashion wish to
avoid being a 'progress inhibitor'. For example, we will be releasing ECC
products soon for educational and non-commercial use.
If Certicom's involvement with ECC is an issue to a potential developer, then I
suppose it could be considered 'encumbered'. But not in terms of acceptance,
effectiveness, ease of adoption, or cost. We're trying to be nice. Please don't
cry wolf until you see who we are.
Cheers!
Ted Rallis
Certicom Corp.
PS Thanks to Bruce Schneier for the cryptanalysis course he posted yesterday.
Eric W Braeden
Perhaps I was too quick on the keyboard, but it is very frustrating
for developers to even know what has been or is being patented.
Development costs for small companies are a big deal and a full
time legal staff is out of the question. Heck it's even possible to
re-invent the wheel only to find out that the ideas have been
covered by a "patent applied" for by some other company. But
how would anybody else know until the patent is actually granted.
I really hate it when companies do "shotgun patents" where every
possible angle is covered by the lawyers and legit developers
are forced out.
I don't know what the solution is, but what we have now is
a big mess. And that's before we even think about foreign patents.
I do believe in IP rights, but I wish we could stamps out BS
patents.
Eric
Ted Rallis wrote in message <36151D52...@certicom.com>...
Roger Schlafly
have
>worked for thirteen years (and counting) to perfect and advocate ECC
>technology. Some of the obvious benefits of this are the ANSI and IEEE ECC
>standards (which we wrote).
Unfortunately, Certicom also wrote in dependencies on unissued
submarine patents. It would have been possible for those
standards to be unencumbered, but Certicom was firmly
against it.
Eric
Certicom appears to have very good rights in regard to practical
implementations of ECC, especially efficient ones. This does not mean that
there is no way to do possibly-inefficient ECC and circumvent Certicom
rights, but it would seem to be a legal argument at the least.
If anyone knows a qualified (not quackified or self-certified) patent
attorney who would like to comment on this matter in this global forum,
that would be beneficial to many.
cwright_bl...@zoinks.ne.mediaone.net wrote in article
<6v0bc3$efr$1...@wbnws01.ne.highway1.com>...
> Hello,
>
> I have a simple question: Is ECC unencumbered by patents or other
> restrictions that would require me to pay someone to use it, as is the
crypt...@my-dejanews.com
cwright_bl...@zoinks.ne.mediaone.net wrote:
> Hello,
>
> I have a simple question: Is ECC unencumbered by patents or other
> restrictions that would require me to pay someone to use it, as is the
> case now for RC4? I'v been checking out Certicom's web page, but I
> find nothing to confirm either way. The one encouraging sign is that
> it's being incorporated into various standards, but that doesn't
> necessarily imply that it's license-free....
>
> Thanks,
>
> Charles R. Wright
Charles,
ECC is not patented as a mathematical concept. The discovers
of ECC, Koblitz and Miller, never filed patents for their invention.
Many companies like Certicom and others exploited this discovery and
worked on optimizing implementations of ECC. Some of these companies
made great advances in the area of ECC including Certicom.
Even though Certicom's name pops up every time ECC is mentioned, this
does not mean that Certicom has a monopoly over ECC. There are numerous
implementations of ECC that are at least as good as Certicom's and they
are not patented and are FREE. There are free ECC implementations
where no royalty is due; except, may be, for the owners of Public Key
Partnership if their patent is still valid.
If I want to use a good ECC implementation, I will look for FREE ECC
implementations which could be obtained from academic sites and I will
get a couple of good software developers to optimize them without worrying
about any body who claims patents over ECC.
I made a search on http://www.patents.ibm.com/ibm.html for those
who have patents on ECC. Certicom's name comes up the least on that
list. May be Certicom's claims are for pending patents. Certicom has
no will or resources to enforce any of its claims over any ECC patents.
What is Certicom doing to stop Sony, Intel and others who are implementing
ECC in the P1394 UBS standard?
ECC patents have not been contested in any court of law because ECC patents
are not clear and since the patents are over implementations and not over
the concept, I do not believe any legal action will be successful.
Your best bet is to find a good academic ECC implementations, there are
many sites that have good implementations, for example Worcester
Polytechic, Catholic University of Belgium. There are even free
commercial implementations. If I were you I will talk to Cylink
who are willing to offer their implementations for free. May be you
can talk to Hitachi for a free licence.
CryptoNEWS -- Cryptographic Consulting
Sam Kamille -- Manchester, England
-----== Posted via Deja News, The Leader in Internet Discussion ==-----
http://www.dejanews.com/rg_mkgrp.xp Create Your Own Free Member Forum
crypt...@my-dejanews.com
and encryption algorithm, to help him/her get some information about
the decryption keys using the encrypted text.
Assuming that the malicious code and the way it works is only known
to the agency or the person who inserted it into the encryption
algorithm. How difficult is it to tell if the code from X origin
is contaminated and the code from Y origin is not?
Do we need the source code to determine if any malicious code is
inserted?
Can we test for malicious code in the object code or the restructured
sources code from the object code?
Malicious code (not viruses or rouge applets) seem to be a big problem
that might render encryption useless if it is not detected properly.
Cheers,
Sam
Sandy Harris
>An agency or a person can insert few lines of malicious code into
>and encryption algorithm, . . .
> . . . How difficult is it to tell if the code from X origin
>is contaminated and the code from Y origin is not?
A digital signature can provide some assurance about the source of the
code & a checksum some assurance that it hasn't been altered. Of
course, then there are questions about reliability of the algorithms,
protocols, servers, . . . used in the sig & checksum.
>Do we need the source code to determine if any malicious code is
>inserted?
Yes, but it's not clear you can be entirely certain even then:
http://www.ece.cmu.edu/~tardis/thompson/hack.html
Douglas A. Gwyn
> Do we need the source code to determine if any malicious code is
> inserted?
Either that, or a secure hash from a trusted provider
of the master copy of the executable code.
crypt...@my-dejanews.com
sandy....@sympatico.ca (Sandy Harris) wrote:
> A digital signature can provide some assurance about the source of the
> code & a checksum some assurance that it hasn't been altered. Of
> course, then there are questions about reliability of the algorithms,
> protocols, servers, . . . used in the sig & checksum.
A digital signature can only help if we are sure that the
source or the company which supplied the original code was
supplying clean code and nothing malicious was added.
If you look at this scenario, company (X) from a country (A)
agrees with agency (AG) from country (A) to include malicious
code in the crypto which will be shipped to country (B). Now
when company (Y) from country (B) imports the contaminated
crypto from company (X) and uses it in communication sysytems
of country (B)all the communications in country (B) that use
the crypto from company (X) can be decrypted by agency (AG)
from country (A).
Now when the code was shipped from company (X) to country (B)
it never was changed because it was infected from the start.
Any digital signature check on it will show no change since
no alteration on the code was done after it was shipped.
Now are there any methods available to check for the malicious
code and make sure the imported software includes only the
encryption algorithm and not the inserted malicious code?
I hope I made myself clear.
Adam Young
a way which benefits only the person who compromises the code and no
one else. In such scenarios, only a person skilled in both programming
and crypto can tell that the code is compromised. For more information,
see http://www.cs.columbia.edu/~ayoung. It is shown how a system like
PGP can be modified to produce a system which leaks RSA private keys
securely and exclusively to the person who modifies it, and no one
else, even if the source code is publicly available.
Adam
Crypt...@hotmail.com
adam...@earthlink.net wrote:
> There are some scenarios in which crypto code can be compromised in
> a way which benefits only the person who compromises the code and no
> one else. In such scenarios, only a person skilled in both programming
> and crypto can tell that the code is compromised. For more information,
> see http://www.cs.columbia.edu/~ayoung. It is shown how a system like
> PGP can be modified to produce a system which leaks RSA private keys
> securely and exclusively to the person who modifies it, and no one
> else, even if the source code is publicly available.
>
> Adam
Adam,
Are you aware of any ongoing research that tries to identify such
modifications in crypto code? If any body knows of any existing
algorithms that can look into malicious modification of code
please let me know.
I am working with a client in Europe who is evaluating three Crypto
products from three different suppliers in North America. Two of
the suppliers are willing to disclose their source code and the third
company is unwilling to disclose its source code because they do
not want to reveal their source code. My clienets are very concerned
about the scenario which you described in your response.
From you experince can you say that the crypto which we can see its
source code is safer that the crypto which we cannot see its source
coded?
Adam Young
>
> In article <362894...@earthlink.net>,
> adam...@earthlink.net wrote:
> > There are some scenarios in which crypto code can be compromised in
> > a way which benefits only the person who compromises the code and no
> > one else. In such scenarios, only a person skilled in both programming
> > and crypto can tell that the code is compromised. For more information,
> > see http://www.cs.columbia.edu/~ayoung. It is shown how a system like
> > PGP can be modified to produce a system which leaks RSA private keys
> > securely and exclusively to the person who modifies it, and no one
> > else, even if the source code is publicly available.
> >
> > Adam
>
> Adam,
>
> Are you aware of any ongoing research that tries to identify such
> modifications in crypto code? If any body knows of any existing
> algorithms that can look into malicious modification of code
> please let me know.
I know of no systematic way to thoroughly check black boxes
for malicious modifications, and I don't know off hand of anyone who
is working on it.
> I am working with a client in Europe who is evaluating three Crypto
> products from three different suppliers in North America. Two of
> the suppliers are willing to disclose their source code and the third
> company is unwilling to disclose its source code because they do
> not want to reveal their source code. My clienets are very concerned
> about the scenario which you described in your response.
As well they should be. The papers at the site listed above describe
how to leak a public key encrypted private key within the upper order
bits of an RSA modulus. Thus, when a user publishes his public key,
he is also publishing the ciphertext of his private key, which only the
attacker can decrypt (the attacker being the one who modified the
RSA key generation algorithm). The papers also describe how, if a
diffie-hellman black box device is able to store state information
between key exchanges, one out of every two key exchanges leaks one of
the DH keys to the attacker (implementor). This attack is extended to
leaking (t,t+1) keys. A similar attack is presented that leaks a DSA
private key using merely two DSA signatures. These attacks assume
modifications to the respective systems, but are undetectable when
implemented in black boxes (e.g., microchips).
> From you experince can you say that the crypto which we can see its
> source code is safer that the crypto which we cannot see its source
> coded?
Yes, that can make all the difference in the world. But it's not the be
all and end all. Recall the Turing award lecture "Reflections on
Trusting Trust" in which Ken Thompson exlains essentially how a
compiler can insert any sort of malicious code, code not even aparent
in your own source. The lecture also explains how even if you recompile
the compiler with that bad compiler, the `new' compiler could still
behave in this way. Now you can see why to be certain a computer
system is secure, it must be heavily guarded, even when it is being
built.
Adam
dian...@tecapro.com
Crypt...@Hotmail.COM wrote:
> [...]
> From you experince can you say that the crypto which we can see its
> source code is safer that the crypto which we cannot see its source
> coded?
Any software company producing security related products should be
willing to give you their source code, at least under
nondisclosure agreements. If they don't they *may* want to hide
something, which surely is not the strength of their program.
Having said that, I think that getting the source code of a
security related system is not particularly useful for the
following reasons:
1. Real world source code is complex; if you can really read and
verify others' source code you can probably write the program
yourself and at a lower cost.
2. If you don't intend to check on the source code, but only want
to recompile it then you must first trust your source code
supplier. If so, you might as well trust your supplier's
executable code. Whether you get source or executable, a
digital signature will guarantee that you get the real thing.
3. People think that source code is transparent and always reveals
the programmer's intentions. It is possible to implement
"steganography" like techniques to actually hide malicious code
in the source code (for example, code that leaks key material
to the virtual memory's swap-file). In other words a competent
programmer can introduce malicious code in the source so that:
a) it is very difficult to discover, b) if discovered it will
look like a subtle bug.
4. Even if having the source code were useful, you should have
*all* source code. This includes the code of your computer's
operating system as well as all memory resident programs such
as screen savers, etc. People who trust a Windows version of
PGP because PGP's source code is available are in a state of
delusion. It's like a passenger of the Titanic feeling secure
because his cabin door is locked.
Rather than fixating on the source code, I think it is more
practical to check a security system as if it were a black box,
i.e. check whether it outputs what is should. For example, if you
are testing a PC based communication system, then you may want to
consider the whole PC (including CPU, memory, O.S. and
electromagnetic radiation) as a black box you trust and only check
the information transmitted: Is it ciphertext produced by the
appropriate cipher? Does it include any other information - if so,
check it down to the last bit, including "garbage" fields. Or, you
may prefer to consider the program's execution as a black box.
Then you can check how the computer's internal state (both RAM and
hard-disc memory) is affected by the security program's execution.
Beware that hard-disc memory includes rarely checked spaces such
as the slack at the end of files, partition and boot sectors, etc.
Ideally, a good security related program should clean after
itself; this means that after its execution all disc or RAM memory
changed should be filled with zeros.
--
http://www.tecapro.com
email: dian...@tecapro.com
crypt...@my-dejanews.com
dian...@tecapro.com wrote:
> Any software company producing security related products
> should be willing to give you their source code, at least under
> nondisclosure agreements. If they don't they *may* want to hide
> something, which surely is not the strength of their program.
I am in the business of evaluating crypto products from technical
and market point of views. I see a lot of claims on how many billions
of years it takes to break a crypto system using all the computing
power available. Integer factorization and the discrete log problems
are well established to be unbreakable "relatively speaking," bragging
about the un-breakabaility of your cryptosystem, being it an RSA or
elliptic curve cryptosystem (ECC) is misleading and a waste of time.
Proper implementations of RSA and ECC are well established beyond
any doubt.
Since the security of the cryptosystems is well established by the
intractability of (IF) and (DL) problems, we need to look at is
how these algorithms are implemented. We have to ask the question:
if company (X) or company (Y) collaborated with Agency (A1) or
Agency (A2) on including invisible malicious code in their
implementations. May be a question like this will not be important
in North America but in Europe there is a lot of concern that there
are some Agencies out there that want to see all the communications
that goes on between commercial parties and others.
In the difficult task of evaluating imported crypto this is the most
important issue that arises. Do companies compromise their code to
get an export license and achieve their projected revenues?
While there is a lot of research on discovering new algorithms to break
or to cut the time needed to break (IF) and (DL) problems, which is very
important research as it stands, I am unable to identify at least 10%
of the cryptanalysis effort on identifying malicious code in crypto
implementations. This Scenario has been proven to be possible with PGP
as was referred to earlier by another message, this means it is possible
to do that in all (IF) and (DL) problems including (ECC).
May be this question should be aimed at crypto vendors:
Which companies are willing to disclose their source code?
If they do not disclose their code, why is that?
Cheers,
Sam
Michael Voytinsky
dian...@tecapro.com writes in <70fff8$umr$1...@nnrp1.dejanews.com> ...
> 1. Real world source code is complex; if you can really read and
> verify others' source code you can probably write the program
> yourself and at a lower cost.
However, if a company is willing to provide its source code (under an NDA)
it is an indicator that they are fairly confident there is nothing
objectionable there. (Or, if you are pessimistic, they are confident that
they obfuscated it even in source code form.)
To summarize - it makes them more trustworthy - even if you can't read the
whole thing. Its a useful datapoint when evaluting the trustworthiness of
a company.
> Rather than fixating on the source code, I think it is more
> practical to check a security system as if it were a black box,
> i.e. check whether it outputs what is should.
However, you could not do this with all possible inputs. This leaves open
the possibility of "backdoors".
One of the questions I would ask a vendor of security products is "What code
review procedures do you utilize" to make sure that your developers do not
put in undocumented features?
Cheers
Michael
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Michael Voytinsky, SP4, KoX
Ottawa Ontario Canada
http://www.igs.net/~michaelv
***** Question Authority? Sez Who!? *****
PGP Key at: ldap://certserver.pgp.com
PGP Fingerprint: AA61 BD6A 11CB 926A ED1E B135 9938 200E 0D8C 56F9
Mok-Kong Shen
> However, if a company is willing to provide its source code (under an NDA)
> it is an indicator that they are fairly confident there is nothing
> objectionable there. (Or, if you are pessimistic, they are confident that
> they obfuscated it even in source code form.)
>
> To summarize - it makes them more trustworthy - even if you can't read the
> whole thing. Its a useful datapoint when evaluting the trustworthiness of
> a company.
However, it IS a serious problem that very few people can well
understand large pieces of code written by others or have the time
to do so. (I can write correct C programs but currently I am
desperate in 'decrypting' a rather short piece of C code of somebody
else.) If codes are only available under NDA, the number of people
that have the opportunity of examining them would be fairly small
from the outset. Thus in my view, for extremely critical applications
one has virtually to write ones codes (the kernel part at least) all
oneself, using available codes as helps.
M. K. Shen
----------------------------------------------
Apply not techniques that you haven't fully understood. Use only
subprograms that you have thoroughly verified. Never blindly trust
what your colleagues claim. (a programmer advising novices, ~1970)
Lincoln Yeoh
> 4. Even if having the source code were useful, you should have
> *all* source code. This includes the code of your computer's
> operating system as well as all memory resident programs such
> as screen savers, etc. People who trust a Windows version of
> PGP because PGP's source code is available are in a state of
> delusion. It's like a passenger of the Titanic feeling secure
> because his cabin door is locked.
>
> Rather than fixating on the source code, I think it is more
> practical to check a security system as if it were a black box,
> i.e. check whether it outputs what is should. For example, if you
I still believe having the recipe to my cake and being able to bake it and
then eat it myself is safer than buying a cake where the company refuses to
give me their secret recipe. And this is even though I don't have the
design of the oven and the other stuff. Sure, maybe the oven can insert
nasties into my cake. But then it is less likely that the oven would be
designed just to put those nasties into the cake.
To me having the source code is preferable to checking a system as if it
were a black box. If there is a backdoor it is highly unlikely you will
guess the correct input to trigger it. e.g. if user tries to decrypt a
particular message, the program subsequently chooses message/session keys
from a 40 bit subset.
You will have to reverse engineer it, which is even more difficult than
scanning through source code. In fact you might as well rewrite everything
by the time you're through.
It is a greater delusion to think that we can find out if something is
secure just by treating it as a blackbox, varying the inputs and checking
the outputs. Before you finish sticking all the inputs into your blackbox,
the sun would have gone out. Much easier to check the source code.
I'm aware of the risks. I think that no source at all is riskier.
You can use Microsoft's crypto stuff running on Microsoft's OS, or you can
go use PGP running on Microsoft's OS. Or you could use PGP on Linux.
Link.
****************************
Reply to: @Spam to
lyeoh at @peo...@uu.net
pop.jaring.my @
*******************************
dian...@tecapro.com
> On Mon, 19 Oct 1998 13:39:52 GMT, dian...@tecapro.com wrote:
> > 4. Even if having the source code were useful, you should have
> > *all* source code. This includes the code of your computer's
> > operating system as well as all memory resident programs such
> > as screen savers, etc. People who trust a Windows version of
> > PGP because PGP's source code is available are in a state of
> > delusion. It's like a passenger of the Titanic feeling secure
> > because his cabin door is locked.
> >
> > Rather than fixating on the source code, I think it is more
> > practical to check a security system as if it were a black box,
> > i.e. check whether it outputs what is should. For example, if you
>
> I still believe having the recipe to my cake and being able to bake it and
> then eat it myself is safer than buying a cake where the company refuses to
I agree. My whole point was that you *should* have the source
code; also that having the source code is not very useful and
gives an exaggerated sense of security to many people.
> [...] And this is even though I don't have the
> design of the oven and the other stuff. Sure, maybe the oven can insert
> nasties into my cake. But then it is less likely that the oven would be
> designed just to put those nasties into the cake.
I think this is not a good analogy. Mine corresponds much closer
to normal operational environment of a security application in a
typical PC; it is indeed like sailing in a fragile ship and
feeling secure because the cabin's door is well build and locked.
For example, in a typical PC, PGP is there as well as the
gargantuan Windows code and also an assortment of drivers, screen
savers, utility applets, Internet applications - all running
concurrently. Any one of these can in principle steal your
password as you type it, which makes of course the question of
whether PGP uses CAST or IDEA or 1024 bit RSA pretty irrelevant.
> To me having the source code is preferable to checking a system as if it
> were a black box. If there is a backdoor it is highly unlikely you will
> guess the correct input to trigger it. e.g. if user tries to decrypt a
> particular message, the program subsequently chooses message/session keys
> from a 40 bit subset.
I had not thought of a malicious program that is triggered by a
particular input. This mechanism is interesting but does have the
disadvantage that if source code is available (a pre-requisite in
our discussion) it will be difficult to hide the malicious code.
Security is always a matter of probabilities and context. In my
model I take it that you worry *only* about the security program
itself. If you do worry about trojan horses or that other
malicious code, able to produce spurious inputs, lurks within your
operating environment, then the whole question about how to check
a security application is moot. The only other possibility for
inputting a trigger to your security program is by means of a
malicious human actor; in many situations this is considered
improbable. If this is not the case, i.e. if a hacker can
penetrate your system and control the inputs to your application,
then security is almost hopelessly compromized anyway.
So let us stick to the premise: the whole operational environment
of your system (hardware, software, humans) is trustworthy and you
worry only about the security application itself. Now you have two
alternatives: check its source code or check its output. I think
in most situations checking the output is a more practical
proposition.
> It is a greater delusion to think that we can find out if something is
> secure just by treating it as a blackbox, varying the inputs and checking
> the outputs. Before you finish sticking all the inputs into your blackbox,
> the sun would have gone out. Much easier to check the source code.
I understand you point but I wonder. At least a black box can be
checked automatically with billions of inputs randomly selected
from the legal inputs set - source code validation requires lots
of time of expensive specialists.
> I'm aware of the risks. I think that no source at all is riskier.
>
> You can use Microsoft's crypto stuff running on Microsoft's OS, or you can
> go use PGP running on Microsoft's OS. Or you could use PGP on Linux.
Agreed. I always thought a DOS e-mail client that boots directly
from diskette would be nice too.
I think that really tight security requires the use of a separate
specialized metal box, running only the encryption software (no
standard O.S) and with its own independent keyboard and low
emission screen, connected to your PC's parallel port or bus. I
suppose such a box can be constructed and will be used as a local
and personal security server tightly integrated with your O.S.
environment. The idea is that all sensitive plaintext would exist
only within this box. I suppose in the net-centric world of
tomorrow there is a market for such a box.
--
email: dian...@tecapro.com
http://www.tecapro.com
crypt...@my-dejanews.com
1- How large is the deployed base for Elliptic Curve
Cryptosystem (ECC)?
2- Which flavor of ECC is more deployed? F(2^m) or F(p)?
3- What is the flavor that is more likely to dominate relying on
the Standards?
4- Are there any technical advantage of using F(2^m) or F(p)?
5- What companies are willing to ship source code to the clients?
Cheers,
Sam
Robert Harley
crypt...@my-dejanews.com writes:
> 1- How large is the deployed base for Elliptic Curve Cryptosystem (ECC)?
Pretty small, I imagine.
> 2- Which flavor of ECC is more deployed? F(2^m) or F(p)?
No idea.
> 3- What is the flavor that is more likely to dominate relying on
> the Standards?
The standards have basically been hijacked by people promoting the
F(2^m) variety, and even then using curves defined over F(2). The use
of such a thin set of curves with such special properties strikes me
as criminally insane.
> 4- Are there any technical advantage of using F(2^m) or F(p)?
There's not a whole lot of difference.
In software the latter is usually a bit faster since chips tend to
have integer multiplication instructions.
In hardware a multiplication "without carries" is simpler than one
with so in theory the former ought to be a bit better if you did
dedicated hardware.
There is a nice algorithm for multiplying in normal bases that can be
used: build a multiplication table as usual but observe that you only
need one row because the others are obtained by rotation. This works
in any field extension with a cyclic Galois group. The algorithm,
is described in standard textbooks, such as van der Waerden's "Modern
Algebra" (it's section 54 in the sixth printing of the English
translation of the second edition that I have before me, along with
some worked examples).
This algorithm is sometimes used as an argument in favor of F(2^m) but
the algorithm was patented in the 80's for the extensions F(2^m)/F(2),
at least, and for composite extensions very recently. Apparently
American patent examiners don't search math books back to 1803 or
whenever it was that Gauss invented it (he covered prime-conductor
cyclotomic extensions of Q, which is much more difficult than the
trivial characteristic-two case, and even gave explicit formulae for
the basis elements and multiplication table...)
> 5- What companies are willing to ship source code to the clients?
No idea.
Rob.
bo...@rsa.com
> Cryptosystem (ECC)?
I doubt anyone knows. I know how many copies of our toolbox have sold
since we made EC available, but as to whether anyone uses EC vs.
other methods is a proprietary issue for each customer. And companies
selling crypto don't generally share sales info. One also has large sales
of EC based smart cards.
Furthermore, customers don't WANT it known how many EC smart cards
they have (for example).
>
> 2- Which flavor of ECC is more deployed? F(2^m) or F(p)?
Noone knows. It is likely to be F(2^m).
>
> 3- What is the flavor that is more likely to dominate relying on
> the Standards?
Assumes facts not in evidence. to wit: that one flavor does dominate.
I expect even characteristic to be more prevalent in the long run because
I expect more smart cards than other hardware to use EC in the long run.
Even characteristic requires less power and less hardware.
>
> 4- Are there any technical advantage of using F(2^m) or F(p)?
>
Yes. and disadvantages. It depends on the application.
> 5- What companies are willing to ship source code to the clients?
We do. Under certain restrictions.
Medical Electronics Lab
> 1- How large is the deployed base for Elliptic Curve
> Cryptosystem (ECC)?
Small but growing. As pointed out by Bob, security by
obscurity makes the attackers life more difficult.
> 2- Which flavor of ECC is more deployed? F(2^m) or F(p)?
Why does that matter? If you have a choice of hardware
that works, you'll look at the specs which interest your
application.
> 3- What is the flavor that is more likely to dominate relying on
> the Standards?
It depends on the application. The standards are open
so you can adjust the flavor.
> 4- Are there any technical advantage of using F(2^m) or F(p)?
On binary ASIC's F(2^m). On binary computers, usually F(2^m).
Finding the group size over F(p) is trivial for random p, so
that's an advantage. The application will usually determine
which is better for overall performance.
> 5- What companies are willing to ship source code to the clients?
My code is free :-) For a good size fee and NDA, I suspect any
company will discuss it with you. If you want something to
test with, check out http://www.msn.fullfeed.com/~eresrch
Patience, persistence, truth,
Dr. mike
Mika R S Kojo
> crypt...@my-dejanews.com wrote:
> > 4- Are there any technical advantage of using F(2^m) or F(p)?
>
> On binary ASIC's F(2^m). On binary computers, usually F(2^m).
> Finding the group size over F(p) is trivial for random p, so
> that's an advantage. The application will usually determine
> which is better for overall performance.
Is this really true? Is computing the number of points of an elliptic curve
over F(p) for random p a trivial exercise. I think not :)
(If it is true, then what about for curves over Z(n), n any positive
integer. I believe that such a result would mean the end of public key
cryptography.)
The group order is fast to compute for classes of elliptic curves
over F(2^m) which is a significant advantage on many applications.
Certainly there are also classes of elliptic curves over F(p) for
which you can trivially find the group order (by definition), such as
supersingular curves, but these are not safe.
Mika Kojo <mrs...@cc.helsinki.fi>
Funny mode on.
George Barwood
<mrs...@kruuna.helsinki.fi> wrote:
>Medical Electronics Lab <ros...@physiology.wisc.edu> writes:
>> crypt...@my-dejanews.com wrote:
>Is this really true? Is computing the number of points of an elliptic curve
>over F(p) for random p a trivial exercise. I think not :)
I agree - it is hardly trivial - although a mathematician might
disagree :) AFAIK only Francois Morain's group have done it for the
size of p which is desirable for good security say ~ 256 bits. You
need Schoof's algorithm with various delicate refinements.
bo...@rsa.com
Mika R S Kojo <mrs...@kruuna.helsinki.fi> wrote:
> Medical Electronics Lab <ros...@physiology.wisc.edu> writes:
> > crypt...@my-dejanews.com wrote:
> >
> > On binary ASIC's F(2^m). On binary computers, usually F(2^m).
> > Finding the group size over F(p) is trivial for random p, so
> > that's an advantage. The application will usually determine
> > which is better for overall performance.
>
> over F(p) for random p a trivial exercise. I think not :)
Not trivial, but not hard either. Improvements to Schoof's algorithm
have made it quite practical.
>
> (If it is true, then what about for curves over Z(n), n any positive
> integer. I believe that such a result would mean the end of public key
> cryptography.)
This is irrelevant. An elliptic curve over Z/NZ where N is composite does
not form a group. And your *belief* is wrong.
>
> The group order is fast to compute for classes of elliptic curves
> over F(2^m) which is a significant advantage on many applications.
For certain m, yes, but I would be wary of such fields. They have
too much structure.
One generally doesn't need to change curves frequently. This makes
the issue of how long it takes to compute group orders somewhat moot.
Can we stop this silly debate? There are advantages and disadvantages
to F(2^M) and F(p). Choose the one which suits your hardware and
application. Neither one is "better".
Christof Paar
:
: >Is this really true? Is computing the number of points of an elliptic curve
: >over F(p) for random p a trivial exercise. I think not :)
:
: I agree - it is hardly trivial - although a mathematician might
: disagree :) AFAIK only Francois Morain's group have done it for the
: size of p which is desirable for good security say ~ 256 bits. You
: need Schoof's algorithm with various delicate refinements.
:
It's not only the Morain group. The people in Johannes Buchmann's group
in Darmstadt, most notably Volker Mueller, have been doing point counting
for quite a while.
Christof
--
*************************************************************************
Christof Paar http://ee.wpi.edu/People/faculty/cxp.html
Assistant Professor email: chri...@ece.wpi.edu
Cryptography Group phone: (508) 831 5061
ECE Department, WPI fax: (508) 831 5491
100 Institute Road
Worcester, MA 01609, USA
*************************************************************************
George Barwood
wrote:
>It's not only the Morain group. The people in Johannes Buchmann's group
>in Darmstadt, most notably Volker Mueller, have been doing point counting
>for quite a while.
Indeed, they apparently have a (commercial?) package available:
http://www.informatik.tu-darmstadt.de/TI/LiDIA/Welcome.html
Point counting package
There is an implementation of the Atkin/Elkies algorithm for counting
the number of points on a elliptic curve over a finite prime field
with large characteristic. This package uses the LiDIA library, but is
not part of the free distribution. For details, please contact the
LiDIA-Administrator
They don't seem to have tackled the small characteristic case.
George
Mika R S Kojo
> Mika R S Kojo <mrs...@kruuna.helsinki.fi> wrote:
> > (If it is true, then what about for curves over Z(n), n any positive
> > integer. I believe that such a result would mean the end of public key
> > cryptography.)
>
> This is irrelevant. An elliptic curve over Z/NZ where N is composite does
> not form a group. And your *belief* is wrong.
I tried to be funny, failing miserably it seems.
I still *believe* that if you can trivially compute the number of
points of an elliptic curve over Z/nZ, n general, you can pretty much
factor that n.
> One generally doesn't need to change curves frequently. This makes
> the issue of how long it takes to compute group orders somewhat moot.
Yes. Nevertheless, some people don't like to spend hours or more
generating curves, not even once.
> Can we stop this silly debate? There are advantages and disadvantages
> to F(2^M) and F(p). Choose the one which suits your hardware and
> application. Neither one is "better".
I agree.
Mika Kojo
<mrs...@cc.helsinki.fi>, <mk...@ssh.fi>