Cryptomathic Blog

Fully Homomorphic Encryption

Mon, 06 Feb 2012 13:06:12 GMT

- hype or the answer to all our
prayers?

A couple of years ago, Craig Gentry produced a break-through
result in cryptography: what researchers had been dreaming about
for more than 25 years was finally possible: Gentry had shown how
to do so-called Fully Homomorphic Encryption (FHE). What this
allows is for a party A to receive encryptions of a set of inputs
to some computation. A does not have the key for decryption and so
has no idea what the inputs are. Nevertheless, he can perform ANY
computation he wants on the data while they are encrypted, and in
the end come up with the desired result in encrypted form. This can
then be sent to one or more parties who have access to the
decryption key and they will then learn the results in the
clear.

This sounds like the ultimate solution for doing cloud computing
while preserving privacy of all input data. And indeed it is - at
least in principle, and if we conveniently forget about issues such
as how we know that the results are correctly computed. However, we
are still very far from being able to realize such an application
in practice. Current FHE schemes are extremely inefficient and in
fact much too slow for any real application. Recent implementations
take up to 30 minutes on a powerful 64-bit machine to do a basic
operation (see href="http://eprint.iacr.org/2010/520">http://eprint.iacr.org/2010/520).
Lots of research effort is being spent to do something about this,
and it is beyond doubt that we will have more efficient solutions
in the future. Whether we will ever be able to use FHE directly for
real applications is still an open question, however.

A common misunderstanding is that secure computing on
confidential data suddenly became possible when FHE was invented.
This is not true at all, we have known how to do this since the
late 80's: if several parties are involved in the computation, they
can collaborate to do any computation securely: just as when using
FHE, the inputs will remain private and only the intended results
will be released. These multiparty solutions are very practical
indeed, and are already being used for industrial applications (see
href="http://www.springerlink.com/content/j4772m44r05x0527/">http://www.springerlink.com/content/j4772m44r05x0527/.)
Interestingly, ideas and techniques derived from FHE are now being
used to make these solutions even better, for a recent example of
this, see href="http://eprint.iacr.org/2011/535">http://eprint.iacr.org/2011/535.

To conclude: yes, FHE was an amazing breakthrough in theoretical
cryptography and as such it deserves all the attention is has been
given. But it is not yet an immediate answer to practical secure
computing. Fortunately, however, for this we already have solutions
that will become even better when combined with techniques derived
from FHE, and such combinations look like the best answer to the
actual needs of applications.

Q: What's in a Logo? A: Mathematics

Thu, 02 Feb 2012 11:06:02 GMT

Maybe you have wondered where our logo comes from
and what it actually means. If you have, we hope the
following will answer these questions.

Just as our name suggests, mathematics is the strong foundation
on which our company has been built. The same applies to our
logo.

The Cryptomathic logo is a 4D (4-dimensional) cube projected
onto a 2D (2-dimensional) plane, with one 3D (3-dimensional) cube
highlighted. However, we, as terrestrial beings, can only see
things in 3D it is hard to visualise something with more
dimensions. The 4D cube is obtained by taking a (shadow) copy of
the highlighted 3D cube, and joining all the corresponding corners
of the two 3D cubes.

At Cryptomathic's previous anniversary, a mathematical
challenge was put forward to all employees, centred on our logo.
The challenge was to answer the following 3 questions:

How many cubes are contained in our logo?

How many squares are contained in our logo?

How many edges are contained in our logo?

We only had about 1 minute (really!) to write down our answers,
so basically had to guess, and in fact nobody managed to get all
three answers correct. This lead on to an even bigger challenge for
some of us. For the rest of the day (and some of the next
day) we devoted much of our time to deriving formulas for
calculating these numbers - of course without cheating by looking
at textbooks!

As it is very difficult to imagine things in four (or more)
dimensions, it's often an advantage to re-formulate such questions
using mathematical notation, and also to refer to the question in
more general terms. Thus, we'll generalise into looking at cubes of
n dimensions, and ask how many sub-cubes of k
dimensions are contained within these, for 0 ≤
k ≤.

The cube of n dimensions (the n-cube) is
defined mathematically by its corners:

x =
(x₁, x₂, …,
x_n), for x_i ε
{0, 1}.

A sub-cube of k dimensions (a k-cube contained
in the n-cube) is defined by fixing n-k
of the x_i's to chosen values, while letting the
k remaining x_i's vary. For example, a
2-cube (square) on the 3-cube (cube) is given by fixing one
x_i, and a 1-cube (edge) is given by fixing two
x_i's. Actually, it is the 1-cubes (edges) that
are usually drawn when trying to picture an n-cube.

Obviously, there are 2n 0-cubes (corner points) in the
n-cube, and only 1 n-cube (the n-cube
itself). The argument below shows that in general the number of
k-cubes contained in the n-cube is given by:

f_n,k = 2^n-k ×
(ⁿ_k)

where (ⁿ_k) is the usual
combinatorial function for selecting k out of n
possibilities, given by:

(ⁿ_k) = n! /
k!×(n-k)!

The argument goes as follows:

There are 2ⁿ corners in the n-cube.

Each corner has (ⁿ_k) k-cubes
touching it (choosing which k x_i's to
vary)

Each k-cube touches 2^k corners

Multiplying the first two of these counts each k-cube
2^k times, thus giving the result above by dividing this
out. A similar argument would just say that we could choose the
n-k x_i's to fix in
(ⁿ_k) ways, and then choose the actual values
of these in 2^n-k ways.

Alternatively, if one is very good at imagining things in
n dimensions the result can also be found by observing
that generally the n-cube can be constructed from the
(n-1)-cube by taking a (shadow) copy of it and then
combining all corresponding corners in the two copies. Besides from
doubling all contained k-cubes this also gives an
additional k-cube for each (k-1)-cube in the
original (n-1)-cube. Combined with the previous
observations for k = 0 and k = n, this
gives the recursive formulas*:

f_n,k =
1
, for k = n

f_n,k =
2ⁿ

, for k = 0

f_n,k = 2 ×
f_n-1,k + f_n-1,k-1 , for 0
< k < n

The formula for f_n,k derived earlier can easily be
proved to be the unique solution to these equations.

The answer to the original challenge can now be calculated
as:

f_4,3 = 2¹ × (⁴₃) =
8

f_4,2 = 2² × (⁴₂) =
24

f_4,1 = 2³ × (⁴₁) =
32

Delivering Advanced Electronic Signatures - via a central signing server

Fri, 21 Oct 2011 12:03:23 GMT

The notion of Advanced Electronic Signature was introduced
in the European Directive for electronic signatures[1], which
remains today an important milestone for the standardisation and
legal recognition of electronic signatures. Advanced Electronic
Signatures (hereinafter AdES) offer a very practical method to
protect information and provide trust in electronic business. They
can be embedded in popular document formats such as PDF, XML and
CMS messages[2] and are also the base stone for creating
qualified electronic signatures (QES)[3]

Art. 2 of the directive contains some requirements on signatory
identification and. This paper describes how a central signature
server can fulfill these requirements. This article relates to the
European Commission Standardisation mandate m460 to CEN and ETSI on
electronic signatures and is proposed as input for the ETSI
standard prTS 14167-5.

What is Advanced Electronic Signature?

The directive broadly defines an electronic signature as data
that can be associated with and authenticate other data. To be
considered Advanced, an electronic signature must

a) be uniquely linked to
the signatory;

b) be capable of identifying the signatory;

c) be created using means that the signatory can maintain
under their sole control;

d) be linked to the data to which it relates in such a
manner that any subsequent change in the data is
detectable.

In practice advanced electronic signatures are therefore
implemented using digital signatures based on asymmetric
cryptography with the private key uniquely linked to the signatory.
The signature is verified using the public key of the signatory and
by setting up a proper PKI (typically using certificates) the
signature identifies the signatory. Existing signature methods[4]
ensure that the signature is linked to the data to be signed in a
secure way.

These aspects of advanced electronic signatures are also
discussed by the Forum of European Supervisory Authorities for
Electronic Signatures (FESA)[5]. However their paper ignores the
case where the user/signatory key is stored on a central signature
server.

In this analysis, we will look more precisely at the impact of
central user key storage which, at a first glance, may seem not to
comply with the requirement c) that AdES signature must be
created using means that the signatory can maintain under his
sole control. In other words, how can the key be solely
controlled (I.e. accessed and used for signature purposes) by its
owner while it is being stored on a remote server?

First of all it is paramount that the signatory private key is
protected by a hardware security module (HSM) on the remote
server.

A simple approach would then be to authenticate the signatory
using standard username/password and open a SSL/TLS session to the
server in order for the user to get access to his private key. This
causes a number of issues:

a) Username/Password is a
method vulnerable to simple attacks such as phishing or replay
attacks and cannot be considered secure enough to ensure sole
control

b) if the TLS channel is
terminated outside the HSM the password will occur in clear on the
remote server in order to be used for getting access to using the
private key of the signatory. Access to the key is therefore
subject to memory snapshots by a fraudulent system administrator,
thus once again defeating the sole control.

How to achieve sole control?

In order to prevent (a), it is recommended to implement a
stronger signatory authentication, i.e. implement 2-factor
authentication, where the password constitutes one factor. The
second factor could be a (preferably) dynamic authentication method
based on e.g. OTP. This implies that a trustworthy href="/products/authentication-signing"
title="Authentication & Signing">2-Factor authentication
service is introduced to the solution.

(b) is more difficult of achieve. We need to ensure that no
single system administrator can get access to the signatory key (i)
or use the key (ii).

For (i) to be fulfilled, the
signatory private key shall be protected by an HSM so that the key
may never appear in clear outside the HSM.

(ii) can be solved in different
ways, ideally by implementing many of the following measures:

Make physical AND logical access
to the HSM under dual control so that single administrator cannot
sign data on behalf of the signatory.

Access to use of the key is
exclusively possible after successful authentication of the
signatory (procedures shall be in place to ensure the system
administrators, including HSM administrators, cannot get access to
the signatory authentication values, such as passwords or
OTPs).

The signatory private key can only
be applied to (hashes of) messages that are authenticated by the
signatory

It is also recommended to implement strong logging functionality
in order to securely monitor all actions related to the management
of signatory keys and authentication secrets.

Conclusion

This paper shows that there is no reason to restrict the
creation of AdES to local smart card/workstation. Trust Service
Providers implementing the above measures can perfectly supply
advanced electronic signatures in cloud based environments where
Application Service Providers rely on such service so that users
can sign (web) documents remotely and securely. This offers a
number of benefits including:

Centralised key management: easier
process for generating, storing, backing up and renewing keys -
immediate disablement upon key revocation

Value added services: to enhance the
value offered to the signatory, the centralized approach allows the
Trust Service Provider to mediate connection to time stamping,
archival, notary services.

Reduced costs: no smart card / smart
card readers needed, reduced dependency towards the workstation,
reduced hotline costs / leverage infrastructures costs for large
number of signatories and application service providers.

Such a solution has been implemented by Cryptomathic in the
Signer solution. As noted in the introduction, higher assurance
levels can be achieved when the associated certificate is qualified
and if the central signing service is SSCD certified. Though the
Cryptomathic Signer has not undergone a formal SSCD certification
process, we have carried out together an external law firm a study
showing that it the solution fulfills the SSCD requirements. We are
happy to share the findings upon href="/contact/contact-us">request.

References

[1] Directive 1999/93/EC of the European Parliament and the
Council of 13 December 1999 on a Community framework for electronic
signatures

[2] The European Telecommunications Standards Institute (ETSI)
has published standards for AdES including:

- PaDES:
ETSI TS 102 778 "Electronic Signatures and Infrastructures
(ESI); PDF Advanced Electronic Signature Profiles

- XaDES:
ETSI TS 101 903 "Electronic Signatures and Infrastructures
(ESI); XML Advanced Electronic Signature Profiles

- CaDES
RFC 5126 "CMS Advanced Electronic Signatures" and ETSI TS
101 733 "Electronic Signatures and Infrastructures (ESI); CMS
based Advanced Electronic Signature Profiles

[3] Advanced electronic signatures based on a qualified
certificate and generated using a secure signature creation device
must according to the directive be considered equivalent to
handwritten signatures. Such signatures are called Qualified
Electronic Signature (QES).

[4] E.g., using RSA, DSA og ECDSA.

[5] Working Paper on Advanced Electronic Signatures of October
12 2004 href="http://www.fesa.eu/public-documents/WorkingPaper-AdvancedSignature-20041012.pdf">
http://www.fesa.eu/public-documents/WorkingPaper-AdvancedSignature-20041012.pdf

EMV: The Fraud Bulldozer

Thu, 06 Oct 2011 17:04:28 GMT

These days everyone has a stake in Chip and PIN security -
it can be the topic of the over-the-counter conversation as you
pay, of the boardroom executives at a bank, or over a pint at the
pub. So how is EMV, the electronic payments standard underlying
Chip and PIN shaping up? And what is the modern landscape of
payments fraud? Here, Mike Bond, Technical Director at
Cryptomathic, shares his opinion.

First of all, EMV truly is a new age in electronic payment. EMV
brings together two familiar security concepts into one heavyweight
architecture: a payment token which is hard to counterfeit - the
chip; and an authentication method which does not depend upon human
judgement - the PIN. Neither of these factors in themselves is
intrinsically new, but it is a third factor which heralds the new
age: the scale of deployment. The potential is for billions of
cardholders, millions of terminals.

Because of the size of EMV, the fundamental concepts upon which
it is founded can actually be shifted by its deployment, as if in a
never-ending feedback loop. For example, the chip models currently
used for EMV may have been hard to counterfeit when they were first
issued, but advances in technology, for instance in electromagnetic
emissions analysis, could reduce their security. This is an
external factor. But consider now the amount of money protected by
EMV and the significance of its security for our economies - such a
driver actually prompts research, be it in criminal communities,
industry, or academia. Such research activities when focussed could
quickly undermine the security of one design of chip.

The defence built into EMV is support for diversity. While such
a level of complexity brings other worrying security implications,
it enables EMV to tread the fine line between global
interoperability and diversity. We get security, but when one piece
does inevitably break, the whole system does not crumble. Thus EMV
supports both offline and online transactions, transactions based
upon symmetric and asymmetric cryptography, multiple routes and
methods for verifying the PIN, and each issuer can customise the
issuer to card protocols within the EMV framework. The level of
support for customised risk management is unprecedented.

Yet why, despite these strengths, is there such dispute over
whether EMV is being successful, and if Chip and PIN (as customers
know it) is a good thing or a bad thing? Why did Shell pull the
plug on Chip and PIN at 500 or so petrol stations after a spate of
phantom withdrawals [1]? Why do some militant customers cut up
their cards and demand Chip and Signature replacements? Put simply,
EMV is a fraud bulldozer. It is a large earth-moving tool for
changing the landscape of payments security.

In the UK, EMV has already changed the landscape substantially:
stolen card fraud is down and collusive merchants are no longer a
problem (because they take the liability when the PIN is not
verified). Instances of card skimming, phantom withdrawals and
card-not-present fraud, however, are all increasing; some radically
so.

Financial crime is like the illegal narcotics trade. It is such
a significant part of the global economy that it's here to stay.
No change in the payments landscape will dam the flow, there
will simply be an overspill of fraud elsewhere. The recent UK news
stories about fraud at Shell Garages may claim to expose Chip and
PIN failures, but are in fact reporting the first signs of change
in the landscape; Chip and PIN has not broken, but its strength has
made the ATM system of "magstripe and PIN" considerably weaker.
This is one of the places to which fraud is now flowing, and when a
flow passes through a different player's back yard that player
inevitably gets upset.

So often in electronic payments, debates about the effectiveness
of the bulldozer are muddled up with debates about what sort of
landscape we should build. Everyone wants to have a say on what is
built next to their housing estate, but the availability of the
tools to do the job is rarely in question. Partly this blurring is
a plain mistake, but sometimes it arises from the genuine blurring
of business and technology. Just as our tastes and concepts of
music evolve in parallel with marketing models for music (singles,
albums, charts, ringtones), so the technological architectures of
payments systems are evolving in parallel with business models for
the payments industry. This is why, for instance, there is so much
risk management built into EMV at a protocol level.

There are indeed shortcomings of EMV as a bulldozer --
landscapes it cannot build -- but they are few. The first arises
from the chosen form-factor of the smart-card: it is a device with
no trusted user interface. The cardholder thus has no way to be
100% certain who the card is doing business with, and how much
money is being transacted whenever the card is proffered. This
gives rise to the relay attacks described by Anderson, Bond and
Murdoch [2]. Mobile phones as portable trusted interfaces, or
specialised card readers such as those planned for use with the CAP
internet banking scheme could be the solutions here. A third
hi-tech option which could raise the bar without demanding a
trusted interface could be electronic range bounding, where the
time it takes the electronic signals to travel (at the speed of
light) can be measured with exceptional accuracy, bounding a card's
location within 10 metres or so. Such technology is still under
development but could certainly mitigate the relay attack
threat.

So don't believe that EMV is anything other than successful:
there is just some inevitable conflict to be ironed out about what
the payments landscape of the future should look like.

[1] "Petrol Firm Suspends Chip and PIN", BBC News Online, href="http://news.bbc.co.uk/1/hi/england/4980190.stm">http://news.bbc.co.uk/1/hi/england/4980190.stm

[2] "Chip and Spin", R. J. Anderson, M. K. Bond, S. J. Murdoch
href="http://www.chipandspin.co.uk/spin.pdf">http://www.chipandspin.co.uk/spin.pdf

Previously published in Cryptomathic NewsOnInk,
2006

Where 2FA and PKI Meet

Mon, 19 Sep 2011 12:49:55 GMT

Under pressure from sophisticated attacks and rising fraud, many
B2C organisations of the financial industry are currently enhancing
the static password based authentication to their web applications
to something stronger - the 2FA age. 2-Factor
Authentication (2FA) is currently achieving large scale deployments
and consumer adoption where PKI failed a few years ago.

From a technical standpoint, PKI offers significant benefits
including the possibility to sign transactions of legal value in
domains of trust, which is key to financial institutions offering
online services. Yet, 2FA technology, which offers mere user
authentication, has been preferred by most players for its
user-friendliness and ease of deployment.

The Challenge Ahead with 2FA

The main driver behind the success of 2FA is the protection of
online applications against crimes of ID Theft. An important
feature, which 2FA does not address at present, is the possibility
to offer electronic signature capability, which is gaining more
importance due to the need for message integrity as
Man-In-The-Middle and other advanced attacks are on the rise.

Traditionally, Secure Signature-Creation Devices (SSCDs) are
either chip-enabled cards or USB-connected tokens. Both of them
need to be connected to an end-user station and this is where the
nightmares start for most IT staff departments. Experience shows
that there are often drivers missing, broken connections or
restricted administration rights. In retail, it is simply
impossible to control the environment of the end user. It is
therefore not a viable option to bring such signatures devices to a
large audience.

A Method to Remedy the Situation and Leverage the 2FA
Technology

Our method is very inspired from the cloud computing concept
where a secure infrastructure that offers secure signature services
is made available as a service to the Web community.

Our approach is to centralize the storage and management of
private signing keys at trusted 3rd parties with highly secure
environments and strict procedures in order to maintain data
centres, that are both logically and physically protected. The user
retains control over his private key using 2-Factor Authentication
techniques. What we propose is in a sense very similar to the safe
deposit boxes offered by banks. In such cases, the ownership of the
deposit is not questioned even though the administration and access
to the safe box is under the responsibility of the bank. Similarly,
we propose to safe deposit the user's private key in a tamper
evident environment whose access is granted when a 2-Factor
Authentication of the end-user is performed.

How Does it Work in Practice?

In practice, a user is enrolled and his credentials, along with
a key pair is sent to a certification authority. So far, the
process is identical to a legacy PKI scheme. Instead of receiving
the certificate and the key pair, the user receives two factors of
authentications (e.g. a password sent from a PIN Mailer and an
activation password on SMS using this media to send One Time
Passwords in the future). The private key remains in the secure
signature server its entire life and will never ever leave that
server.

Once this initialization phase is completed, the end-user is
ready to use his key to e.g. sign a transaction presented by a
remote application.

A typical (and simplified) architecture is depicted in the
figure 1 below:

Figure 1 - Basic architecture

To preserve mobility and keep end-user constraints as low as
possible, our only assumption is that the user is connected to a
web enabled application. The challenge therefore is to ensure that
the data to be signed can be transmitted confidentially and
integrally to the central signing server. While keeping minimal
footprint, we have to introduce an end-to-end encrypted and
authenticated channel to make sure that:

a. When a connection is established, the server can be sure that
a legitimate user is in the other end, and

b. When the connection is established the user can enable the
environment where his keys are available, and

c. The user's keys can only be available in the environment
established by a 2FA process. The authentication mechanism does not
really matter (SMS- based OTP, OATH based OTP, EMV based OTP or
proprietary methods are supported). The ultimate aim is therefore
to implement this as rigidly as possible such that it will not even
be possible for inside server operators or even developers with
access to server source code, to circumvent the protection once the
system is deployed.

We wrote that item c is fulfilled by implementing a carefully
designed security kernel at the server side. Items a and b are
achieved using a security protocol which we have designed. From a
top-level perspective, the protocol works the following way:

• The client receives all user credentials (password, OTPs,
token output etc.) and combines these values with entropy (random
values) to form a symmetric key.

• The server (more precisely, the security kernel) attempts to
form the same symmetric key from the knowledge it has and from
publicly exchanged nonces.

• Once the keys have been established, the client sends
encrypted commands to the server and receives encrypted responses
back from the server. If either party fails to decrypt a message,
the communication is terminated. The key for a given connection is
represented by the state of the Pseudo Random Function. Whenever
the user authenticates himself using some credential (e.g. an OTP)
this state is updated using a so-called pre-session key derived
from the credential (in other words the effective key length is
augmented using these credentials).

A convenient way to provide such signature services for the web
application provider is to develop an application using a thin
client in order to fulfil the common zero-footprint requirement
mentioned above. In practice, this is made available as a Java
applet running in a web browser. This applet can of course be
customized to follow a given workflow with interactive features
such as What You See Is What You Sign (WYSIWYS) functionality.

Conclusion

To summarize, I will present the key advantages of deploying
such a method which, as presented in the introduction, leverages
the benefits of PKI and 2FA.

• Convenience: Because a mere 2FA token and a connected terminal
are the sole requirements for the end-user. The burden of PKI
deployments (middleware installation, lifecycle management, etc.)
remains transparent for the customer and is managed centrally. The
application provider can customize his workflow and application
taking advantage of the authentication and signing services
provided by the trust provider.

• Security: Thanks to the secure protocol, the fact that the key
storage is protected in a tamper evident environment and the strict
administration procedures enforced at trust providers site(s), it
is possible to reach a SSCD level and provide Qualified Electronic
Signature (QES) services to key owners.

• Cost-efficiency: No other solution available on the market
offers such a combination of value added authentication and signing
services directly usable in B2C environments. The total cost per
user remains way below legacy SSCD devices.

As of January 1st 2009, Cryptomathic has been granted a European
Patent (EP 1455503) for this method implemented in the Cryptomathic
Signer product.

Previously published in Cryptomathic NewsOnInk,
2009

3rd Party TSM Management of SIM Cards

Mon, 12 Sep 2011 16:45:22 GMT

Trusted Service Manager (TSM) is a relatively new role required
in a mobile Near Field Communication (NFC) ecosystem. The core
services a Trusted Service Manager offers, are the secure
management and provisioning of the applications issued by service
providers, such as banks, transport / ticketing authorities,
merchants, or other application issuers. Provisioning performed
over the air (OTA) includes, for example, the download,
installation, personalization and life-cycle management of the
applications to the secure element of the Near Field Communication
(NFC)-enabled mobile phone. The SIM as a portable, secure and
already existing smart card component will be the obvious secure
element form factor for mobile phones. However, the Trusted Service
Manager can support additional secure element form factors as
well.

Since the first SIM supported NFC-enabled mobile phones entered
the market during 2009-10, the management of the third party
applications on the SIM cards needed to be planned and agreed
between the different parties. The GlobalPlatform's Card
Specification version 2.2 gives a good framework for this, but as
the specification includes several options, the preferred ones need
to be chosen and details agreed between:

The Mobile Network Operator (MNO), the issuer of the SIM
card,

The Service Provider (SP) such as bank or transport operator
issuing the applications, and

The Trusted Service Manager (TSM), who provides services for
both the Mobile Network Operator and Service Provider.

Integration of the Mobile Network Operator (MNO) and Trusted
Service Manager (TSM) Systems

Since the SIM card is always issued by the MNO, certain
integration work needs to be executed between the MNO and TSM
systems and processes. There are various technical alternatives for
constructing the interfaces between MNO platforms and third party
TSM platforms in order to ensure a flawless and secure
communication.

This article presents two aspects in interface design:

1) The interface between the TSM platform and MNO SIM OTA
platform for over the air communications, and

2) Other interfaces required for a Near Field Communications
ecosystem.

Such other interfaces include a "Security Domain Management"
interface, i.e. an interface to enable the TSM to request so called
token signing 3rd party TSM management of SIM card services from
the MNO. The token signing service can be implemented as an online
or offline service per NFC application and therefore the selected
mode has an impact on the corresponding interface.

Security Domain Hierarchy

Security Domains (SD) are used for the management of Service
Provider applications on a SIM card issued by the MNO. Security
Domains can be established and managed in alternative ways and
within different hierarchy models. Different Security Domain
hierarchy models are presented in this article, and it should be
noted that all models are applicable but the final selection of the
model to be deployed must be made through joint discussion and
planning between the MNO, Service Provider (SP) and TSM.

Security Domain Option 1

The first option for a Security Domain hierarchy is to have a
dedicated Security Domain (SD) for the TSM usage - a TSD (Trusted
Service Manager Security Domain). The TSD is associated to an
Issuer Security Domain (ISD), which is managed by the issuer of the
secure element, the MNO. If the Trusted Service Manager Security
Domain is used, each Service Provider application is installed and
personalized in a dedicated SPSD (Service Provider Security
Domain), Properties and privileges of the TSD define the TSM's
capabilities on the SIM card.

Security Domain Option 2

A second option is that Service Provider Security Domains
(SPSDs) are associated directly to an Issuer Security Domain (ISD).
Final architecture of the Security Domains and their use needs to
be undertaken by the issuer of the secure element (the MNO), in
mutual understanding with the SPs issuing their applications to
this platform. The TSM should be able to support all the different
alternatives. Main options for SD management hierarchy are
described below.

It is important to understand that the underlying business
agreements create the foundation for the service provisioning for
all the alternatives. Naturally, the SIM cards must also support
the chosen features.

Security Domain Option 1 with Delegated Management

The following figure highlights the interfaces and
interactions between the TSM platform (in the picture Venyon
Trusted Service Platform) and the MNO platforms for a setup where
delegated management is configured for the TSM Security Domain (SD)
and where the TSM does not have its own Remote Application
Management (RAM) keys needed for creating a direct Bearer
Independent Protocol (BIP) channel to the SIM card.

In this setup the TSM always communicates through the MNO SIM
platform. Additionally, the MNO needs to sign the tokens enabling
the applet download into the TSM SD or alternatively into the
Service Provider SD (SPSD), if a TSM SD is not used.

Although the communication goes through the MNO SIM platform and
is delegated, the security is fully protected between the TSM
platform and TSM SD / SPSD for the download and personalization of
SP applets, as well for any life-cycle management services for the
applets.

Security Domain Option 1 or Option 2 with Authorised
Management

In the authorised management alternative the TSM is capable of
content management without specific tokens from the SIM issuer
(MNO). In an SD Option 1 scenario the TSM can, for example, create
new Security Domains (associated to the TSD) and populate their
keys under a secure channel opened with the TSD. For an SD Option 2
hierarchy there is no TSD and the SPSD(s) is therefore associated
directly with the ISD.

The picture below highlights the interfaces and
interactions between the TSM platform (in the picture Venyon
Trusted Service Platform) and the MNO platforms for a setup where
authorised management is configured for the TSM SD and where the
TSM does not have its own RAM keys needed for creating a direct BIP
channel to the SIM card. For an SD Option 2 hierarchy there is no
TSD and the SPSD(s) is therefore associated directly with the
ISD.

In this setup the TSM will always communicate through the MNO
SIM platform.

Again the security is fully protected between the TSM platform
and TSM SD / SPSD for the download and personalization of the
Service Provider applets as well for any life cycle management
services for the applets, using the MNO SIM platform.

Trusted Service Manager With its Own Remote Application
Management (RAM) Keys

If the TSM is given the TSM specific RAM keys, it can create a
direct BIP channel to the SIM card without routing it through the
MNO platform. If the MNO needs to sign the tokens enabling the
applet download into the TSM SD / SPSD, it will use the delegated
option. If token signing is not required, the authorised model will
be used.

In both these models the security is fully protected between the
TSM platform and the TSM SD / SPSD for the download and
personalization of SP applets as well for any life-cycle management
services for the SP applets.

Cooperation and Dialogue Needed Between All Stakeholders

Technical options are now quite well defined and Mobile
Operators and Service Providers can choose the most appropriate
ones for their implementation. It is however important to realize
that the underlying business agreements create the foundation for
the service provisioning for all of these alternatives. Therefore
close cooperation is needed to settle the outstanding business and
technical issues. By doing so, all stakeholders can build the
sustainable long-term mobile contactless business case enabled by
NFC.

Originally published in Cryptomathic NewsOnInk,
2009

Are the Dynamics of Card Fraud Changing?

Mon, 12 Sep 2011 16:44:42 GMT

In 2009, the RBS WorldPay ATM network reportedly lost $9 million
to a 30 minute fraud attack across 49 cities, in different
countries, using just 100 cloned cards. On the face of it, the $9
million dollar yield from the attack is a large enough figure to
make headline news, but perhaps not that shocking in this day and
age where the total UK card fraud exceeded £500 million in the past
year, according to APACS figures. What is possibly more serious in
this particular scenario is the method of attack.

As with all such serious data breaches within large financial
organisations, the full details of the attack and how it was
perpetrated will probably never be known to a wider audience. What
has been reported is that the money was taken in cash from 130
different ATMs shortly after midnight EST on the 8th November
2008.

Let's have a look at some of these figures: firstly, let's
assume that the 100 cards are cloned and each one is used in each
of the 49 cities; that gives us 4,900 cards to play with. Reports
also indicate that the cards were likely pre-paid cards, as RBS
WorldPay had also reported the loss of some 1.5 million pre-paid
cardholder details from its payroll business, sometime in November
2008 following 'improper access' to its systems.

In order to extract $9M we need to withdraw, on average, over
$1836 per cloned card. That's quite a sum of money from an ATM
transaction! However, if the pre-paid funds were account-based and
not card-based then there were only 100 accounts that were hit to a
tune of $90,000 per account. The reports have stated that the
attack happened at around midnight. It could therefore be safe to
assume that the cards processing platform refreshed the daily
withdrawal limit at midnight every night, so the fraudsters could
effectively take out two days' worth of funds in the space of only
a few minutes. That would in turn mean the fraudsters managed to
secure $918 per card or $45,000 per account, per processing
day.

It's not certain whether the pre-paid cards are based on an
account-centric or a card-centric funds system but by the figures
for the attack the card-based model would seem more realistic.
Either way though, the sheer amount of cash withdrawn indicates
that the fraudsters managed to somehow raise the daily withdrawal
limit on the cards as part of the attack. It is also likely that
the processing platform may not reconcile funds in real time as the
cards were used so many times within a short period without
denial.

Most of this is speculation on what happened based on the
reported figures that are in the public space but it's clear that
this was no ordinary card cloning attack. This was organised crime
at its best, or worst!

To initiate such an attack the fraudsters first managed to hack
into the RBS WorldPay systems and extract the details of 1.5
million users. They then only used 100 accounts so it may be that
they knew how to target specific accounts to provide the highest
yield, or it may be that their attack could be implemented against
any account and they just chose 100 at random. If the latter is
true then it's possible the fraudsters knew the breach would be
quickly detected and the vulnerability eradicated which is why RBS
WorldPay experienced a single large hit and then nothing.

The timing of the attack was not random either. An attack at
midnight EST on a number of US cities plus some other cities
globally at the same time, would indicate that the fraudsters knew
that there would be a specific vulnerability in the system at that
time. Of course the timing could have just been to do with quiet
periods at the ATM so the attackers were less likely to draw
suspicion from passers-by, but the fact that this attack spanned
time zones would suggest otherwise.

What seems very clear is that the masterminds behind the attack
were very tech savvy, and more than likely had some inside
knowledge of the RBS WorldPay processing platform in order to
identify a vulnerability and form a viable attack. This probably
came from a former employee of RBS WorldPay who was bought or had a
grudge with the organisation.

They also had the presence of mind to coordinate a large scale
attack against the identified vulnerability to maximise yield,
rather than performing the attack on small volumes over a long
period. A sustained attack would be more likely to be identified
and they were more likely to be caught and they knew that.

Of course this is not the first clever organised crime attack
and it won't be the last. What it might represent is another step
in a growing trend of card crime moving away from the more
traditional small-to-medium-sized card cloning attacks of the past.
Such attacks are becoming harder to achieve as card technology
advances and ever more intelligent neural network-style fraud
prevention software is implemented on the back-end processing
platform.

So the question is: Are the dynamics of card fraud changing? Are
we seeing a growing trend towards large-scale single occurrence
attacks? In reality it's hard to prove one way or the other. What
we do know is that the general trend is an annual increase in card
fraud. That also comes of course with an annual increase in card
usage, but even the general fraud percentage trend is an increasing
one. What we cannot tell from the information in the public space
right now is how much of the known fraud is from large-scale,
single occurrence attacks.

Some of the complexity here comes from how you define a
large-scale single attack. The current trend in UK card fraud is
for huge increases due to fraud carried out with UK cards overseas
and is a direct result of a phased global rollout of the card chip
technology - the fraudsters take the UK card and use them abroad
where the more modern security features are effectively bypassed.
This is certainly a large-scale attack against a single
vulnerability but it is not a single instance attack.

Quantifying such attacks will only help us understand the trend,
which in turn may help financial institutions decide where best to
deploy their countermeasures, and what those countermeasures should
be. However, the real concern from large-scale, single occurrence
attacks is the mechanism - insider knowledge - and the fact that a
single attack is almost impossible to predict and therefore very
difficult to safeguard against. The only real protection here is
through clearly defined security processes and procedures being
implemented in the fundamental design and build of the financial
institution's systems.

Previously published in Cryptomathic NewsOnInk,
2009

GlobalPlatform Key Managment System

Mon, 12 Sep 2011 16:43:56 GMT

This article provides an overview of GlobalPlatform (GP) Key
Management and includes a proposed architecture for an efficient GP
Key Management System (KMS) based on the Cryptomathic Key
Management System (CKMS). This article is not intended to cover all
possible uses of GlobalPlatform, but is meant to provide an
overview of how it may well be used in an environment where the
chip is personalized centrally, after which it is delivered to the
end-user and subsequently updated with new applications from
various parties, called Application Providers.

Example

Throughout this article, the following example may serve as a
guideline: Consider a mobile Network Operator who supplies
their customers with hand-sets containing a GP chip including
appropriate, standardized interfaces such as e.g. some of the many
GP Secure Channel Protocols. Part of the business model in this
example is to allow application providers and customers to agree on
a peer-to-peer basis for services based on authorizing the
Application Provider to issue and install an application for the
customer using a protected application space allocated by the
Network Operator. It may be useful to think of two or more
applications, e.g.

1) a contactless payment application (e.g. EMV-based)

2) a 2FA token application (e.g. OATH-based)

Additionally, it would be common for the Network Operator to
install their own applications for all users, say an application
which allows the customer to purchase and install ring-tones:

3) Ring-tone application (e.g. DRM-based)

We note that the above applications are likely to use a number
of application specific keys which are outside the scope of the
so-called GP Card KMS, but rather within the so-called Application
KMS. The remainder of this article will focus on keys managed using
the GP Card KMS, although the Cryptomathic Key Management System
supports both.

GP Domains and GP Card KMS Keys

A practical way of implementing the above example using
GlobalPlatform would be for the Network Operator to operate a GP
KMS that they would use to personalize the chip.

Step 1: Issuer Security Domain In receiving the
handset from the manufacturer along with the ISK (Initial Supplier
Key), the chip could be personalized with one single security
domain - the so-called Issuer Security Domain
(ISD) using the keys derived from the Initial Issuer Master Key
(KMC). Under this domain, the Ring-tone application would be
personalized and uploaded using the keys derived from the KMD
(Initial Application Provider Master Key). Next, a CMK (Issuer
Master Key) would be installed, effectively locking the ISD into a
state where the Ring-tone application could be used and new
Supplementary Security Domains (SSD) initialized later.
Following hand-out to the end-user, the end-user would be able to
agree with a Payment Scheme Issuer (i.e. a bank) on a contactless
application, as in our example above, who would then act as an
Application Provider. Caution: be careful not to confuse
with the GP term for Issuer used previously! See Figure 1 for a
logical representation of the security domains under GP: the blue
arrows depict which keys are used to control a given part of the GP
chip environment.

Step 2: Supplemental Security Domain(s) The
bank makes a request to the Network Operator to create a
Supplemental Security Domain (SSD), which the Network Operator does
using commands protected by the keys derived from the CMK. In
setting up the security domain, the Network Operator would load a
new KMD (Initial Application Provider Master Key) or AMK
(Application Provider Master Key), subject to the
implementation.

Next, the Network Operator derives the keys necessary for the
secure channel, e.g. ADKDEK, ADKENC and ADKMAC (used by the bank
for 1. encrypting application keys, 2. application load commands
and 3. MAC'ing of commands, respectively) and passes these three
derived keys to the bank (if not transferring the AMK itself) using
a secure channel agreed in advance between the two parties, as well
as transferring them securely to the chip and also optionally
inserting the DAP (Data Authentication Pattern) key of the bank,
i.e. a public key which can subsequently be used to verify that the
bank has signed the code intended to run on the chip. Now the bank
is ready to post-personalize the chip with the contactless payment
application based on the AMK key derivates.

Repeat Step 2 for any other application providers, e.g. that of
the 2FA application.

Figure 1: The GP chip divided into security
domains

CKMS as a GP KMS

The Cryptomathic Key Management System can be used as both a GP
Card KMS and a GP Application KMS.

GP KMS In our example above, the Network
Operator would operate the main GP Card KMS managing
the ISK received from the Integrated Circuit manufacturer as well
as any KMC, KMD, CMK and AMK keys. The Application
Provider would operate a combined GP Card KMS and GP
Application KMS - the prior for deriving or using the ADK
keys associated with the allocated SSD on the chip and the latter
for managing the contactless payment application, i.e. the EMV
Issuer Master Keys, the EMV Issuer Certificate, etc.

Encoding Using ADKs In simple scenarios, the
Application Provider might not wish to operate an entire Key
Management System, but would rather be interested in a module that
could be used to encode the APDU (Application Protocol Data Unit)
sets associated with the application in question and prepare the
load code using the SSD specific ADKs and optionally the DAP.

Final Observations and Recommendations

DAP Under GlobalPlatform, the DAP is envisaged
to be either a symmetric key or an asymmetric key pair of which the
public key is loaded into the SSD and the private key kept secret
for signing the application code by the Application Provider. The
use of the DAP is optional. If used, we recommend using the form
described in the GlobalPlatform Card Specifications 2.2, i.e. the
form under which the DAP is suggested, simplified into two
scenarios - that a hash is applied to the Load File Data
Block for ensuring integrity of the data and that a
signature is applied to the hash for authenticity of the
origin.

HSMs In either scenario we recommend using HSMs
(Hardware Security Modules) for managing and using keys and we note
that for a number of applications, the use of specially programmed
HSMs is a firm requirement.

Unique AMKs We recommend using unique AMKs per
card and per SSD to avoid the risk of applications being loaded
onto any unintended system.

Secure Operations Finally, we recommend that
any GP Card KMS operated by the GP Issuer (in our example, the
Network Operator) or the Application Provider (the bank, in our
example) to be operated in a secure and controlled environment with
system users' roles and responsibilities well defined and enforced
using hardware tokens such as operator chip cards.

Figure 2: GP Card Keys Used in the GP Chip Lifecycle
Stages (excl. EOL)

The Need for Speed

Mon, 12 Sep 2011 16:43:48 GMT

Ever since the EU mandated the introduction of biometric
ePassports containing fingerprints there has been a flurry of
technology development and innovation to make biometric ePassports
a reality. Much of this played out behind the scenes, but now
electronic passports are slowly working their way towards the
forefront of the public consciousness since they are sufficiently
widespread for researchers and journalists to play with. There have
already been a number of security scare stories where the gap
between the public's perception of passport security and the
reality of the protection is abruptly and rudely closed. It came as
a surprise to many that the first generation electronic chips
generally do not resist identical duplication, and there have been
concerns over eavesdropping and ePassport anonymity. These issues
have put ePassports on the media radar.

However, now there is an even stronger driver for public
interest in ePassports, beyond mere curiosity, because the regular
electronic inspection of ePassports at border control is getting
underway in earnest. This change has maybe been too long in the
making, and phased deployment has drawn the process out even
further (fingers have already been burnt over deployment of part
inspection, where the chip is read, but the certificate which
proves the data is intact is not verified).

From now the performance of ePassports will have a more direct
and tangible effect on travellers, because governments realise that
they cannot claim return on investment for ePassport technology if
the chips are not actually being regularly used. Without return on
investment it is hard to justify passing on the additional cost of
the ePassport to citizens in application fees. So will ePassport
speed travellers through border control bypassing the queues? Will
everyone be able to use e-Gates without enrolment in the future?
Will people be led away for questioning when their ePassport won't
read? Or will the queues get longer?

Unfortunately where we currently stand, the answers to these
questions are not positive. The necessary drive to full inspection
of ePassports needs to be backed up with the same innovation and
new technology that accompanied the issuance process. At the heart
of the matter is the rather lengthy duration of a full biometric
inspection. The machine readable zone (MRZ) on the passport must be
scanned and pushed through OCR, the chip must be read, data
verified, certificates checked. To extract fingerprint biometrics
each inspection system must submit a certificate chain to prove
entitlement; the actual ePassport data must be read out, the
traveller's fingers must be scanned, and finally everything must be
matched up. It is a formidable process, and border control agencies
are starting to realise that it is just not feasible to perform
such inspections unless the time required can be reduced - there is
a very real "need for speed".

Biometric ePassport inspection is such an involved process that
one technology alone is unlikely to be enough to drive down
inspection times to acceptable levels. Proposed solutions include
even greater numbers of e-Gates at border control, newer and faster
chips, to reduce cryptography time and communications overheads,
and new protocol improvements. Cryptomathic has developed a unique
technology in this area designed to work in conjunction with other
speed-up measures in order to rein in the inspection time.

High Speed Inspection

Cryptomathic's High Speed Inspection technology exploits the
middle ground between a fully distributed and a fully centralised
scheme: to implement local caching of data that has been read from
identity documents, on local, national or even international level.
Such a system could retrieve biometric data from an encrypted cache
forming part of the inspection infrastructure at a port of entry.
Reading from such a cache would allow a document to be read almost
instantaneously; however the challenge comes in implementing such a
cache in a secure manner such that the confidentiality, integrity
and anonymity of personal data is preserved. There is a solution,
however: it is possible to create an encrypted cache of biometric
data where each entry can only be accessed in the presence of the
original identity document from which it was sourced.

Consider the example of an ICAO-compliant EU electronic
passport, which contains sixteen different data groups of
biometric, biographical and additional information, such as iris
and signature data. Any and all of these data groups could be
cached with this mechanism. In particular, look at the two large
biometric data groups to be stored on EU Extended Access Control
(EAC) compliant ePassports:

Data Group 2 (DG2) - Facial Information

Data Group 3 (DG3) - Fingerprint Information

Before these large data groups are read from an ePassport, the
"Document Security Object" (SOD) is first read, a sort of "summary
file" which contains a digital signature and protects the integrity
of the information stored on the ePassport. As the summary file
contains high entropy unpredictable data, a key derivation function
can be applied to this data to generate a secure key for encrypting
data from the passport. Such a key could only be recreated in
possession of the summary file. Sources of entropy within the SOD
include, the hashes of biometric data groups, hashes of
cryptographic data groups (AA or EAC public keys), the digital
signature itself and timestamps.

There are many possible key derivation functions drawn from this
high entropy data, which can easily provide enough entropy to
derive a strong cryptographic key, but let us use a simple concrete
example: to use the hash value for each data group to create a
cryptographic key to encrypt the data group bulk data, and to
create a pseudonym for locating the cache data in order to prevent
the cache from containing personally identifiable information.

Figure 1: ePassport Encrypted Cache

Consider the derivation mechanism shown in Figure 1. To securely
store DG2, its hash is divided in half. The first half is used as a
key to a (noncryptographic) hash table in order to store the data
group. The data group is then encrypted using standard
best-practice cryptographic techniques: salting and encryption
under a cryptographic key derived from the second half of the hash.
Example rows in a cache table would contain the following lookup
key and data:

left(hash(DG2)) encrypt( right(hash(DG2)) , salt||DG2
)

In this way, only in possession of the real ePassport (whose
Document Security Object contains the hashes of the data groups)
can one calculate the key and decrypt the data group. It is
infeasible to predict the value of this hash of a biometric data
group, even knowing the identity of the citizen from which the data
groups have been made (this is because JPG and WSQ images are
highly redundant encodings from a semantic perspective, so contain
a lot of unpredictable data).

When is Stored Data Not Stored?

To deploy an encrypted cache scheme successfully it is vital to
be able to convince cryptography experts, lawyers, journalists and
citizens alike that the information is safely held. This is a
challenge hard to meet, and one that has to be tackled head on by
the implementers of the EAC protocols being deployed by the EU for
distributed fingerprint storage. But fortunately the security of a
distributed system is easy for the layperson to grasp - if I have
the document in my hand, I have the data, I can inspect it. If I do
not have the document, I can't. In the case of the encrypted cache,
the core compliance goal is to show that it is not creating a
central store of data, and that really the security lies with the
distributed system just as it has always done. Even with the cache
in place, if I don't have the document in my hand, I can do
absolutely nothing.

The "encrypt and destroy" technique used to enter data into the
cache can be as strong as anybody would want: it relies only on the
security of the cryptographic algorithm, and the act of destruction
of the key in the inspection system.

Trustworthy algorithms such as 3DES and AES have the seal of
approval of national security and intelligence experts as well as
standing up to years of open and academic scrutiny. Destruction of
the key is in fact an easier task than destruction of the biometric
data temporarily held on an inspection system during the matching
process (where the reference image is compared against the
candidate image from the traveller), as the smaller the amount of
data, the easier and the quicker it is to destroy. This is why the
very most sensitive data in the world - cryptographic keys used by
banking authorisation systems, customer PINs, the root keys of
certificate authorities, and even the arming codes for nuclear
weapons all lie under protection of Hardware Security Modules
(HSMs) which are subject to evaluation by NIST and Common Criteria
to demonstrate their security. The world's most secure FIPS 140-2
Level 4 evaluated module, the IBM4758 (and its 4764 successor) uses
the "encrypt and destroy" technique to protect its data. All stored
data in the devices non-volatile memory and RAM is held encrypted
with an internal master key stored in battery-backed RAM. If any
tampering event is sensed (evidence of an attacker trying to
physically penetrate the device and extract data), it need only
destroy this one key to render the entire remainder of the device
useless. The only technique that could be considered more
trustworthy is to use a shaped explosive charge to vaporise the
storage chip's content upon sensing of a tamper event. Even though
these explosions are very small, such technology is unwieldy, and
is the preserve of military equipment at particular risk of
battlefield capture, such as crypto ignition keys in battlefield
radios. Of course an explosive destruction technology can only be
used once (whereas biometric data has to be deleted after every
inspection).

The High Speed Inspection technology developed by Cryptomathic
is patent pending and incorporated into the ID Inspector product
range of inspection systems and software development kits. It is
also available as a technology for third party licensing.

Previously published in Cryptomathic NewsOnInk,
2008

The Trusted Platform Module Explained

Mon, 12 Sep 2011 16:43:14 GMT

Introducing the TPM

The Trusted Platform Module (TPM) is a special purpose
microcontroller designed by the Trusted Computing Group, which
interfaces with a standard hardware/software platform in order to
allow it to be secured to serve the interests of just one party -
the system designer.

The current generation of TPMs (version 1.2) are stand-alone
chips which are usually surface mounted onto the motherboard of a
PC, or integrated into a custom PCB for an embedded device. The TPM
can monitor and access the main bus of the computer, which allows
it to keep track of and report on the configuration state of the
entire computer, from the moment of power-on right through -
potentially - to the execution of applications on a modern
graphical operating system. Monitoring in itself has limited uses,
but combined with access control for secrets based on the
monitoring of state, all sorts of interesting applications become
possible. For example if a PC is booted into a certain trustworthy
state where only a fixed set of applications are installed, the
monitoring TPM could then grant access to data storage and
encryption keys for high security email. Additionally, the TPM can
attest to the configuration of the computer to external third
parties, be it the owner of a device wishing to remotely manage it,
or a device manufacturer leaving a device in the hands of an
untrusted third party. Finally, in order to support requirements
for availability, and to guard against equipment failure, the TPM
includes command infrastructure and protocols for migration of data
between trusted devices, and for use of third parties as privacy or
migration brokers. At time of creation, data can be designated as
either migrateable or non-migrateable, depending upon the
protection model required.

In short, the TPM puts tools in the hands of operating system
designers to protect themselves from attackers with logical access
to low-level parts of the computer (for instance attackers who can
swap out a hard drive).

A Cost-Effective Architecture

The TPM architecture and data format has been designed to
achieve the desired functionality, whilst always observing and
maintaining cost-effectiveness - to keep it suitable for
incorporation into millions of computers at little additional cost.
For example, consider the cost saving decision to use entirely
asymmetric encryption for all data storage, even though a symmetric
encryption algorithm such as a block cipher would be better suited.
The TPM thus need only contain an RSA modular exponentiation
accelerator, and not an implementation of AES or 3DES. Of course,
this does not mean that the TPM cannot store such keys - simply
that it does not perform cryptography using them. Instead,
symmetric keys are sealed to a configuration and released for use
to a trustworthy OS configuration. TPM internal data storage
formats are thus limited by the maximum size of data that can be
encrypted using an RSA operation of a particular key length. But
how does the TPM deal with false key injection - as the public half
of the storage key will be available to all? The ability to insert
false keys may seem irrelevant (after all it cannot gain access to
existing storage keys which govern protected content), but is
crucial as without it, it would be possible to create a key which
is designated as non-migrateable (can never be removed from a
specific TPM), and yet with a value known to the attacker. If a
content provider were to issue content to be protected under this
key, a breach would occur. The TPM solves this problem by
maintaining a special random secret - known as "TPM Proof" - which
is inserted into every data structure encrypted under the TPM's
root storage RSA key, and is checked for a match against the master
copy of TPM proof held in a special register. This ensures that
false keys cannot be inserted into the key hierarchy: whilst anyone
can of course encrypt plaintext under a public key, they do not
have access to the clear value of TPM proof. Essentially, the
asymmetric crypto system is converted into a symmetric one, with a
composite key consisting of the private half of the root storage
key and TPM proof.

The TPM does make extensive use of cryptographic hash
operations, however, and currently uses the SHA-1 hash algorithm.
This hash algorithm is used to "extend" the values in the Platform
Configuration Registers (PCRs), to detect and prevent data
modification, identify keys, and to create "capabilities" used to
improve the efficiency of command chaining. Capabilities are
created by hashing particular command parameters together with the
secret value TPM Proof in order to create a 160-bit capability
string which cannot be forged by an adversary. This is useful in
improving the performance of (for example) third-party approved
migration, where the third-party produces an authorisation
certificate processed by the TPM. The TPM architecture would be
complicated by storing additional state between API commands, but
on the other hand, requiring the migration certificate to be
verified before the migration of every individual key incurs a
performance penalty. The use of capabilities based on TPM Proof
allows the check to be done once only, and a capability issued,
which is much quicker to check at subsequent invocations of migrate
commands.

Physical tamper-resistance is another area where the TPM
architecture has been thought out carefully. In principle, there is
no limit to the security of a system built when cost is not a
factor. The question as always is - who is willing to pay for it?
For this reason, the TPM is alike most other commercial security
measures: it protects against certain attacks, and not others.
Specifically, as the TPM was envisaged as a low cost secure
microcontroller, one of the most significant compromises has been
limited protection against physical attacks. The first generation
of TPMs are separate chips, which are physically separable from the
devices they are monitoring. Current TPMs are generally surface
mounted onto the motherboard, and whilst it is a non-trivial
operation for an amateur to de-solder and replace chip components,
it has not been designed to resist active physical attacks. For
example, selective modification of bus signals to the TPM,
simulation of reset and use of dual-ported memory have all been
proposed as ways to trick a TPM into erroneously releasing access
to cryptographic keys whilst the system is in an unapproved state.
That said, the TPM specification does not require it to be a
separate chip, and there are plans underway to release specialised
hardware with more tightly integrated TPMs.

But such a trade off is not necessarily a bad choice: hardware
attacks are rarely within the threat model when TPM-based systems
are deployed. Scenarios such as Digital Rights Management (DRM)
exist where the operator of a computer is the attack, but more
often it is logical attacks - in particular Trojan Horse and
rootkit attacks - where TPM monitoring of Operating System
integrity really aims to make a difference. Together with improved
operating system design, hardware-assisted state monitoring is an
important component of systems to protect the integrity of user
input and display; a concept introduced almost 10 years ago as a
bi-product of the European ESPRIT project on Electronic Commerce,
SEMPER, namely WYSIWYS: What You See Is What You Sign.

The one area where the TPM architecture has gone out on a limb
in the trade-off between cost and functionality is in the area of
privacy - many sophisticated architectural features and layers of
indirection in the design exist purely to enable online services to
use TPMs without forcing the compromise of a user's privacy. This
operates through a system of pseudonymous identities which can be
managed locally and registered with trusted third parties (trusted
not to reveal a user's identity), and also via direct anonymous
attestation - an implementation of a zero knowledge proving
protocol which is designed to allow a TPM to attest to a particular
configuration without revealing this identity to anyone. This is an
extremely advanced protocol in comparison with other deployed
systems, and shows that whilst the TPM is generally aimed at the
low-cost market, compromises have not been made in the area of
privacy. The only caveat to be considered is that inclusion of
advanced architectural features does not necessarily mean that
applications and systems will take advantage of these features -
ultimately it will depend on whether the final online service
provider is economically motivated to protect the user's
privacy.

TPM Application Space

Many modern laptops (for example those from Lenovo (IBM) and HP)
have Trusted Platform Modules already integrated, however the chip
lies dormant by default and must be enabled (usually in the BIOS)
before it can begin monitoring. Once activated software such as
Microsoft BitLocker disk encryption software - released as part of
Windows Vista Business and Ultimate editions - can be configured to
use the TPM for secure storage of top-level cryptographic keys.
Whilst BitLocker and disk encryption in general can be seen as the
flagship deployed application, the more ambitious functionality of
the TPM such as remote attestation can only really be leveraged in
tandem with a specially designed operating system. Simply put - if
the trusted code has bugs, then the remote attestation proves
nothing - for it can be compromised after keys have been
surrendered to it. Vista may have made a substantial leap ahead for
Windows security, but in order to really make sense of remote
attestation, an OS more akin to SE Linux is required. Supposing
such an OS could be created and a usable work environment for the
desktop developed, there would be some interesting benefits. The
platform could restrict installation to only approved software so
virus and spyware protection would no longer be a challenge. This
is a commonly envisaged use case of the TPM - for helping system
administrators of IT systems in large corporations keep users
workstations locked-down from unauthorised tampering, be it a
virus, or a theoretically benign application installed by the user,
but which might damage reliability and complicate technical
support.

One of the major deployment areas for the TPM in future may be
in monitoring and securing mobile phone embedded computers, as they
support more and more advanced services (e.g. GPS mapping, mp3
playing, media streaming). Interestingly while the push to secure
the low-level software in the platform is undoubtedly aided by the
TPM, user programmability and interactivity is not suffering so
badly, as such features are migrating to higher and higher software
layers, for instance Javascript and interactive web services - all
of which will be supported on a modern mobile.

The arrival of the TPM secure microcontroller has largely been
due to an open co-operative effort between major IT hardware and
software players including Microsoft, Intel, Infineon, IBM and Sun
Microsystems, but it is not necessarily large companies such as
these who will benefit the most from the TPM (Sony for example
already has proprietary secure microcontrollers used in all its
products for enforcing security policies) - it is the affordance of
this hardware assisted security to smaller companies and even
individuals which is most exciting. So there is a bright future
ahead both on the desktop and for embedded and ubiquitous
computing, which the TPM can play a major role in - whether within
or alongside the eternally ubiquitous general purpose computer.

Previously published in Cryptomathic NewsOnInk,
2008

Issuing MULTOS Cards

Mon, 12 Sep 2011 16:42:59 GMT

MULTOS cards are being deployed in steadily increasing numbers
and Cryptomathic is delighted to be involved in MULTOS projects
across the globe.

MULTOS is a high-security card platform and issuing model in
which the "personalization" of cards with the cardholders' data is
done in one single logical step before reaching the actual
personalization machines. This is quite the opposite to the
standard method of personalizing native cards where the data is
sent to the cards, element by element and thereby increasing a
potential exposure of sensitive data.

Cryptomathic supports MULTOS issuing through CardInk - a data
preparation system for EMV and magnetic stripe cards - which has
recently been expanded with a range of applications supporting the
MULTOS platform. We offer, amongst other applications, MasterCard,
Visa and SPAN2. SPAN2 is used in the Kingdom of Saudi Arabia on
multi application cards that contain a second Visa or MasterCard
application for international use.

Contactless - The New Emerging Technology

The latest technology advancement within the field of payment
cards is the so-called contactless card. With a contactless card
one does not have to insert the card into a reader when paying - it
is sufficient to place the card within the proximity of the reader,
say 10cm, and the transaction will take place "through the air".
The purpose of contactless cards is to enable ease and speed of
use, particularly for low value transactions. Cryptomathic is in
the process of finalising a MULTOS implementation on MasterCard
contactless cards (MICA / MACU) with a planned release shortly
before Christmas.

Security in a Complex Environment

In an attempt to explain the increased interest in MULTOS one
could consider the dynamics of card prices, intensified sales and
marketing efforts (especially from MasterCard), and the industry
recognition of the relatively high level of security involved.
MULTOS has traditionally been associated with MasterCard but the
model has proven flexible enough to now support other players in
the market.

Needless to say the use of such a complex model means added
requirements regarding both functionality and security. A lot of
players are involved when a bank decides to engage in a MULTOS
project, and because the technology is still evolving, constant
attention to industry requirements, practices and technology is
necessary.

MULTOS applications are required to integrate with other payment
scheme specific software products / instances, and necessitate
bit-by-bit precision formatting of the so-called Application Load
Units (ALUs) that are used to personalize the cards. This last part
is particularly non-trivial as each card type and each application
has its own requirements and formats, thus we have made substantial
investments to implement the management of this into CardInk.

The security requirements are also more comprehensive than for
native card issuing. Examples include the generation and management
of more DES and RSA cryptographic keys, securing personal data
using both symmetric and asymmetric encryption, and digital
signatures. Specialising in commercial cryptography, it has been
interesting for us to enter this area and we are happy to admit
that we have had to make full use of our skills to accomplish the
implementations.

Image 1: Structure of an Application Load Unit

Image 2: The KTU-Prime Method

Image 3: Optimised MULTOS Production Model

Loading Applications

The data preparation system receives the actual application that
will run on the card from an external supplier; in principle simply
a software application that will be loaded and run on the MULTOS
card operating system. This application manages the interaction
with an ATM or pointof- sale terminal based on data received from
the bank host or card management system containing a list of
cardholder names, account numbers, spending limits etc. The data
preparation system maps the data to specific data addresses. For
particularly sensitive data a sequence of encryption keys are
generated and used to encrypt the individual data segments. These
encryption keys are collected and placed in a Key Transformation
Unit (KTU), and further encrypted under yet another key. Lastly the
data is signed by a digital signature. Together these combined data
components form the Application Load Unit.

When the ALU is loaded onto the card, the card verifies the
digital signature, and decrypts the sensitive data. To accomplish
this, the data preparation system and the card must previously have
exchanged information about the signature keys / certificates,
encryption keys, application layout, and go through key management
authorities - just to mention some of the interface points.

In the basic MULTOS scheme the KTU is directly RSA-encrypted
using a key specific for each card. Thereby each file produced
corresponds to a specific card. In practice however, this has
proven unfortunate as some cards do fail during production leading
back to a second round of data preparation with a new card ID, new
keys etc., all of which can be cumbersome.

To address this issue MULTOS has introduced an intermediate step
model where one generates the data for a generic card and uses only
symmetric encryption of the KTU. At production, the card ID is then
read from the card and the ALU is re-encrypted to target the
specific card Optimized Multos production model with the card's RSA
public key. This way a failed card can be immediately replaced.
This new method is called the KTU-Prime Method.

Extended Key Management

CardInk contains complete key management functionality for
MULTOS, in addition to card issuing. However, for customers with a
large amount of cryptographic keys to manage we also offer a
specific product, the Cryptomathic Key Management System (CKMS).
All the cryptographic keys can be managed in CMKS and be pushed to
CardInk to enable separation of operations and avoid key management
ceremonies in the production environment.

MULTOS step/one - A Variant Application

An alternative offering within the MULTOS framework is the
MULTOS step/one card. The step/one application is structured around
the same principles as conventional MULTOS cards, but it excludes
RSA cryptography for both the actual payment application and the
method of constructing the ALU. The payment application is an SDA
(Static Data Authentication) application - the card security is
based on a pre-calculated digital signature on the card data, as
opposed to a DDA (Dynamic Data Authentication) application where
each card has its own RSA key pair. For the ALU construction the
digital signature is made using a DES MAC and the contained
cryptographic keys are likewise DES encrypted. The advantages of a
MULTOS step/one card is its simpler application and implementation,
which further results in lower card prices.

Previously published in Cryptomathic NewsOnInk,
2007

Authenticated Encryption

Mon, 12 Sep 2011 15:25:02 GMT

A New Cryptographic Primitive?

By far the oldest and perhaps also the best-known goal of
cryptographic methods is the protection of secrecy, or
confidentiality, of data. This goal is achieved by employing
encryption techniques. Decryption can only be performed by someone
possessing the right decryption key.

Of far greater relevance in most commercial applications is the
protection of the correctness, or authenticity, of data. This goal
is achieved by means of digital signatures, or message
authentication codes (MACs). Both digital signatures and MACs
compute a tag, which can be seen as a kind of checksum computed
over the message and using a secret key. Without the secret key, it
is not possible to compute a valid tag - hence all modifications
applied to the data after the computation of the tag can be
detected easily.

Separation of the concepts confidentiality and authenticity is
relatively new. Historically, cryptographers believed that by using
a strong encryption algorithm, they could ensure the authenticity
of data as well. And indeed, when we are talking about
human-readable messages, this assumption is justified. However, in
the case of digital input data, both theory and practice have shown
that the two goals are quite different.

Hence, next to encryption algorithms, cryptographers developed
authentication algorithms. For example, the CBC-MAC algorithm
operates by 'encrypting' the message with a block cipher in the
Cipher Block Chaining (CBC) mode of operation, and then outputs the
last block of ciphertext (possibly truncated) as tag. There are
many variants on this scheme, most of them attempting to solve the
problems that arise when a legacy block cipher like the DES is used
as the underlying block cipher. When using the AES, even the
simplest CBC-MAC construction is secure.

When the length of the message to be protected is relatively
large compared to the block length of the block cipher, the
performance of the authentication step can be improved by using
alternative constructions. Most widely used is HMAC, which produces
a tag by hashing a message and a key together, operating at the
speed of the underlying hash algorithm (e.g. SHA-256).

For applications that need to protect both confidentiality and
authentication, the most straightforward approach is to process the
input twice: once to encrypt the data and once to compute the
authentication tag. This is called making two passes over the data.
Recently, this approach has lost its appeal, for several reasons.
The first observation that can be made is that there seems to be
room for performance optimizations. Implementations may use the CBC
mode of operation both for encryption and authentication, and it
may appear a bit odd to run essentially the same process twice,
each time with a different key. Secondly, and more importantly,
there is the issue of ordering. Should we first encrypt the message
and subsequently authenticate the ciphertext, or should we
authenticate the message and subsequently encrypt both message and
tag, or should we apply both in parallel on the message? Thirdly,
can we use any encryption algorithm together with any
authentication algorithm, or should we worry about mutual
side-effects?

In order to solve these matters, cryptographers have been
looking with increased interest at a different approach: the use of
authenticated encryption modes. Here, a block cipher is used in a
special mode of operation, which simultaneously provides
confidentiality and authentication. The most efficient
authenticated encryption modes provide authentication at a
negligible additional cost compared to encryption only. These modes
all appear to be patented or patent-pending. The second class of
authenticated encryption modes offers no performance advantages
compared to separate encryption and authentication passes, but
still solves the ordering issue and avoids worrying about
side-effects.

An example of the first class is the Integrity Aware Cipher
Block Chaining Mode (IACBC). This mode is very similar to the
ordinary CBC mode. A message consisting of m blocks P_i
is encrypted (and authenticated) as shown below:

Integrity Aware Cipher Block Chaining Mode (IACBC)

C₀ = X₀ = Enc_K (r)

X_i = Enc_K (P_i +
X_i-1)

C_i = X_i + S_i

C_m+1 = Enc_K (P₁ + P₂
+ ... + P_m + X_m) + S₀

Here r is a random nonce, as with CBC. The whitening
values S_i are new. They are derived from r by
means of a scheme using log₂(m + 1) encryptions under a
different key K'. The final ciphertext block is also new. It is an
encryption of a checksum of all the plaintext blocks. Compared to
ordinary CBC, authentication is provided at the cost of
log₂(m + 1) + 1 additional encryptions and management of
one additional key.

In the second class, the CCM mode of operation uses two separate
passes to provide confidentiality and authenticity. It consists of
an input formatting step, a CBC-MAC operation (with IV set to
zero), and finally an encryption in counter (CTR) mode. The
underlying block cipher is assumed to be AES. The same key is used
for both the CBC-MAC operation and the CTR encryption. The EAX mode
of operation is similar, but different. It uses OMAC instead of
CBC-MAC, and it performs the authentication step after the
encryption step, which is still done with CTR mode.

All the proposed modes come with a proof of security, provided
that the underlying block ciphers satisfies some requirements. CCM
has the advantage of having been adopted by NIST but, despite (or
perhaps because!) of this, it has been the subject of criticisms by
members of the cryptographic community.

None of the proposed modes offers a functionality that can't be
provided using a combination of the classical techniques at the
same or marginally slower performance. Their main advantages are
their simpler proofs of security, reduced key management and the
fewer opportunities they leave for mistakes.

References

NIST Special Publication 800-38C: Recommendation for block
cipher modes of operation: the CCM mode for authentication and
confidentiality.

Previously published in Cryptomathic NewsOnInk,
2005

Digital Rights Management Protection

Mon, 12 Sep 2011 15:14:02 GMT

In 2004, Intel, Nokia, Panasonic, and Samsung among others
announced plans for a licensing and compliance framework called
Content Management License Administrator (CMLA) (see href="http://www.cm-la.com/">www.cm-la.com). This body was
formed to address necessary business concerns and enable rapid
delivery of high-quality digital content to mobile handsets and
other devices that deploy Open Mobile Alliance (OMA).

CMLA's goal is to provide vendors and service providers with
clear processes and guidelines for robust and compliant OMA DRM
Version 2.0 implementations making their product development cycles
faster and easier. Ultimately, CMLA will assist in bringing
consumers greater access to new and emerging digital content such
as music, video clips, games etc.

CMLA asked Cryptomathic to help improve the security without
influencing performance. To this end, Cryptomathic made a proposal,
which has now been adapted by CMLA, and an international patent
application has been filed by CMLA with the Cryptomathic
cryptographers as inventers.

The approach that was taken was to ensure that keys were of
maximum entropy, i.e. "as random as possible". A scientific paper
has been submitted for publication and will be published very soon,
and we include here an abridged version of the introduction:

A key derivation function (KDF) is a function that takes as
input a (short) string of random bits and outputs some number of
(pseudo-randomly chosen) keys for some cryptosystem, typically keys
for a symmetric cipher such as AES. This can be useful, for
instance, in situations where we have a truly random seed of
limited size, but we need to generate many keys.

Of course, any secure pseudorandom generator G can be used as a
KDF in a simple way: just split the output from G in a number of
consecutive k-bit blocks, where k is the length of keys we want,
and output each segment as a key.

Now, the important question is, of course, whether the
encryption we get by using the KDF-output as encryption keys is as
secure as if we had chosen the keys independently and uniformly?
For the simple construction just mentioned, we can say that the
answer is yes if G is a good pseudorandom generator, since this
means that the adversary cannot distinguish G(R) from a genuinely
random string.

But this point of view is overly simplified, for several
reasons: first, a pseudorandom generator is not simply "good" or
"bad", it has a certain amount of strength, depending on exactly
how hard it is to distinguish its output from random. It may be
prudent to design our KDF construction so that all security is not
lost, even if the generator turns out to be weaker than we had
hoped. A second - perhaps more important - point is that, while
pseudorandom generators are usually seen as general methods for
making bits that are as good as random for any practical purpose,
we have a specific application in mind, namely to generate
cryptographic keys. In this application, certain specific
properties may be especially important, and we should consider
whether we can make sure they are satisfied.

One such property we consider is called local g-uniformity. A
locally g-uniform KDF has the property that any subset of g output
keys is genuinely uniform.

Why is this a nice property? In the special case where only a
single key is generated, it seems reasonable to demand that this
key is genuinely random, as long as the seed contains enough
randomness for this to be possible. Local 1-uniformity ensures
this. But local 1-uniformity is also desirable when several keys
are generated: As mentioned, the adversary will not be looking
directly at the keys, instead he will have to try to break the
encryptions we produce using the keys. Say we use the keys for some
block cipher like AES. Now observe that, as long as the adversary
tries to break encryptions produced from a single key Ki, then
since Ki is uniform, this will be as hard as simply breaking AES,
i.e., using this type of attack, the adversary cannot exploit the
fact that the keys are derived by a KDF.

In fact, the only way he can do so, is by attacking at the same
time encryptions under at least two different output keys Ki, Kj
and somehow use the fact that Ki, Kj are not independent. This can
reasonably be expected to be harder than attacking a single key and
exploit that this single key is not uniform, which would be a
possibility for the adversary if the KDF was not locally
uniform.

Motivated by this, we chose a KDF construction which augments a
pseudorandom generator G with universal hashing. This construction
guarantees local (almost) 1- uniformity for any desired key length,
assuming the seed is sufficiently long, given that G satisfies a
condition we call local randomness. This is much weaker than local
uniformity and loosely speaking says that if we split the output
from G in consecutive blocks, then each block contains at least
some (small) amount of randomness. This construction needs as
secret seed only what is needed as input for G.

Previously published in Cryptomathic NewsOnInk,
2005

Patents on Elliptic Curves

Fri, 09 Sep 2011 17:12:31 GMT

Background

Elliptic Curves for use in public key cryptography were first
proposed independently by two mathematicians, Neil Koblitz and
Victor Miller, in 1985. The underlying difficult mathematical
problem is the so-called discrete log problem, which in the
classical scenario is the following: Given a (large) prime
p, a g less than
p and a random integer x less
than p, calculate y =
g^x mod p (i.e. the
integer remainder of g^x divided by
p). The discrete log problem then states: Given
p, g and y, find
the (unique) x < p-1, for
which g^x = y mod
p. Obviously, this can be achieved by exhaustive
search for p small, but in general this is a very
hard mathematical problem which nobody has been able to solve in
any satisfactory or reasonable sense of the word "solve", except
for special cases.

In the discussion above, the so-called multiplicative group
structure on the integers modulo a prime p was
used. In Elliptic Curves, a different group structure is used. It
is the points on an Elliptic Curve over a so-called finite field,
which is - for cryptographic applications - always either the prime
field for a large prime p (i.e. the integers
modulo p) - which is said to be of characteristic
p - or a "large finite field of characteristic 2",
which can be constructed as follows: Choose any sufficiently large
n (e.g. 163), and find an "irreducible" polynomial
of degree n, over the primary field with 2
elements, the integers modulo 2 (consisting of 0 and 1, all
additions and multiplications being what they are expected to be
except 1 + 1, which is 0). These fields are called binary fields
for obvious reasons. An irreducible polynomial with binary
coefficients is of the form xⁿ +
a_n-1x^n-1 +...+
a₁x + 1, where each coefficient
a_i is 0 or 1 (i.e.
x² + x + 1 or
x³ + x + 1).
Irreducible means that it cannot be written in any way as a product
of two polynomials of smaller degree. So
x² + x is not
irreducible, as it equals x(x+1).
A little more tricky is that x² + 1 is
not irreducible as it can be written as (x +
1)(x + 1) (just remember, 1 + 1 is 0 J ). Anyway,
mathematics can be employed to prove that there exists irreducible
polynomials of any degree over a prime field, and there are very
effective algorithms to find them.

An Elliptic Curve over a finite field is the solutions in the
finite field of certain equations of the form:
y² + a₁xy + a₃y =
x³ + a₂x² + a₄x +
a₆. The solutions (pairs of x
and y) to "smooth" equations together with a
special point at infinity, denoted O, form an
Elliptic Curve.

A number of "standard" Elliptic Curves exist (e.g., see NIST and
SECG) for characteristic 2 as well as p.

Comparing Cryptosystems

The advantage is first of all bandwidth: It is well established
- and acknowledged by researchers that without sacrificing security
Elliptic Curves allow keys to be considerably shorter than the two
alternatives, RSA and exponentiation modulo a prime
p. For instance, the general view is that a
163-bit curve provides the same level of security as does 1024-bit
RSA.

Equivalent key sizes

EC
(bits)
RSA (bits)

163
1024

256
3072

384
7680

512
15360

Source: SIZES

With a 163-bits curve a signature has size 326 bits, while a
signature with 1024 bits RSA has size 1024 bits. It is important,
however, to notice that these are the actual sizes of the "raw"
signatures. Typically the raw signature is packaged in a larger
structure (e.g., PKCS#7), which among other information may provide
the public key that can validate the signature (i.e. in an X.509
certificate).

If non-standard curves are used, domain parameters (field and
curve specifications) must also be supplied and in this case, the
appearing favour of Elliptic Curves compared to RSA for small key
sizes somehow decreases.

In addition to shorter signatures, the shorter key lengths of
Elliptic Curves compared to RSA also implies that signatures can be
generated faster. However, one of the few advantages of RSA over
ECC is the fact that using small exponents, RSA verification is
significantly faster than ECC.

Why Not Use Elliptic Curves?

Looking at the vendors that provide Elliptic Curve technology,
there is one company that beyond comparison sticks out as the
market leader: Certicom. Right from the beginning, the chief
cryptographer and founder of Certicom, Professor Scott Vanstone,
decided to concentrate a major part of the R&D of Certicom on
ECC. There are other vendors who have considerable experience and
know-how with ECC - after all it is well known and understood
mathematics - but Scott Vanstone and his team have produced several
protocols, such as the renowned ECMQV three-pass key agreement
protocol, which is patented by Certicom. In addition, the company
has a number of patents on specific implementations, typically with
the purpose to increase the performance.

Roughly speaking, these can be classified into three groups:

1. Protocols such as ECMQV

2. Performance issues such a design of arithmetic
circuits and transfer of additional data elements for efficient
signature verification.

3. Point compression

The ECMQV provides an authenticated key exchange where the
ephemeral key pairs are implicitly signed by the static or long
term key pairs. Surely this can be achieved by other protocols,
such as STS. It still remains to provide a security proof for
ECMQV.

Beside designs for arithmetic circuits, the patents for improved
performance are generally closely connected to specific types of
fields and representations and can all be avoided.

The mathematics behind Point Compression is very simple: If we
know the x-coordinate of a point satisfying the Elliptic Curve
equation, we can find the y-coordinate simply by solving a
quadratic equation, yielding two solutions. The advantage is that
by indicating - with a bit - which of the two solutions to choose,
one only has to specify the x-coordinate rather than both. The
un-patented alternative of course is to give both coordinates.

Point compression is nice because it reduces the size of public
keys from say 510 bits to 256 bits. Solving quadratic equations
over finite fields is a reasonably cheap operation, hence point
compression only slightly increases the computational effort.

Standards

Thanks not the least to Certicom's persistent hard work over a
number of years, ECC has made it into a number of standards over
the years, such as ANSI, FIPS, IEEE and ISO standards, and we refer
to Appendix B of the excellent book, Guide to Elliptic Curve
Cryptography by Darrel Hankerson, Alfred Menezes and Scott
Vanstone, Springer Professional Computing 2004, ISBN 0-387-95273-X
for details.

Conclusion

There are those who claim there are other issues, such as using
specific curves, but it is important to understand that it is
possible to implement efficient and secure ECC solutions without
violating any patents whatsoever: Alternatives to ECMQV can be used
and the advantage of point compression is often reduced by the
structures in which the raw signature is embedded.

Indeed, a number of vendors are offering Elliptic Curves, such
as RSA Security, Cryptomathic, as well as chip vendors such as
Infineon without violating these patents, so eliminating ECC as a
solution a priori just because of patents issues is simply not
justified.

References

Special Publication 800-57 Recommendation for Key Management,
Part 1: General Guidelines - DRAFT, NIST Computer Security Resource
Centre, January 2003

href="http://csrc.nist.gov/CryptoToolkit/kms/guideline-1-Jan03.pdf">
http://csrc.nist.gov/CryptoToolkit/kms/guideline-1-Jan03.pdf

Digital Signature Standard (DSS), FIPS PUB 186-2 (+Change Note),
NIST, January 2000

href="http://csrc.nist.gov/publications/fips/fips186-2/fips186-2-change1.pdf">
http://csrc.nist.gov/publications/fips/fips186-2/fips186-2-change1.pdf

Standards for Efficient Cryptography, SEC 2: Recommended
Elliptic Curve Domain Parameters, Certicom Corp, September 2000

href="http://www.secg.org/download/aid-386/sec2_final.pdf">http://www.secg.org/download/aid-386/sec2_final.pdf

Previously published in Cryptomathic NewsOnInk,
2005

Cryptomathic Blog

Fully Homomorphic Encryption

Q: What's in a Logo? A: Mathematics

Delivering Advanced Electronic Signatures - via a central signing server

What is Advanced Electronic Signature?

How to achieve sole control?

Conclusion

References

EMV: The Fraud Bulldozer

Where 2FA and PKI Meet

The Challenge Ahead with 2FA

A Method to Remedy the Situation and Leverage the 2FA Technology

How Does it Work in Practice?

Conclusion

3rd Party TSM Management of SIM Cards

Integration of the Mobile Network Operator (MNO) and Trusted Service Manager (TSM) Systems

Security Domain Hierarchy

Security Domain Option 1

Security Domain Option 2

Security Domain Option 1 with Delegated Management

Security Domain Option 1 or Option 2 with Authorised Management

Trusted Service Manager With its Own Remote Application Management (RAM) Keys

Cooperation and Dialogue Needed Between All Stakeholders

Are the Dynamics of Card Fraud Changing?

GlobalPlatform Key Managment System

Example

GP Domains and GP Card KMS Keys

CKMS as a GP KMS

Final Observations and Recommendations

The Need for Speed

High Speed Inspection

When is Stored Data Not Stored?

The Trusted Platform Module Explained

Introducing the TPM

A Cost-Effective Architecture

TPM Application Space

Issuing MULTOS Cards

Contactless - The New Emerging Technology

Security in a Complex Environment

Loading Applications

Extended Key Management

MULTOS step/one - A Variant Application

Authenticated Encryption

A New Cryptographic Primitive?

References

Digital Rights Management Protection

Patents on Elliptic Curves

Background

Comparing Cryptosystems

Why Not Use Elliptic Curves?

Standards

Conclusion

References

A Method to Remedy the Situation and Leverage the 2FA
Technology

Integration of the Mobile Network Operator (MNO) and Trusted
Service Manager (TSM) Systems

Security Domain Option 1 or Option 2 with Authorised
Management

Trusted Service Manager With its Own Remote Application
Management (RAM) Keys