Re: [Cfrg] Trusting government certifications of cryptography

"Torsten Schütze" <> Tue, 07 October 2014 08:15 UTC

Return-Path: <>
Received: from localhost ( []) by (Postfix) with ESMTP id C2A9E1A9142 for <>; Tue, 7 Oct 2014 01:15:11 -0700 (PDT)
X-Virus-Scanned: amavisd-new at
X-Spam-Flag: NO
X-Spam-Score: 0.314
X-Spam-Status: No, score=0.314 tagged_above=-999 required=5 tests=[BAYES_50=0.8, FREEMAIL_FROM=0.001, MIME_8BIT_HEADER=0.3, RCVD_IN_DNSWL_NONE=-0.0001, RP_MATCHES_RCVD=-0.786, SPF_PASS=-0.001] autolearn=ham
Received: from ([]) by localhost ( []) (amavisd-new, port 10024) with ESMTP id bjW48gkIV13B for <>; Tue, 7 Oct 2014 01:15:08 -0700 (PDT)
Received: from ( []) (using TLSv1.2 with cipher DHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by (Postfix) with ESMTPS id 2CAC81A1B4E for <>; Tue, 7 Oct 2014 01:15:08 -0700 (PDT)
Received: from [] by 3capp-gmx-bs29.server.lan (via HTTP); Tue, 7 Oct 2014 10:15:03 +0200
MIME-Version: 1.0
Message-ID: <trinity-5e384bba-2edd-4ee2-a511-c8dc1caa173a-1412669702907@3capp-gmx-bs29>
From: "\"Torsten Schütze\"" <>
To: "D. J. Bernstein" <>
Content-Type: text/plain; charset="UTF-8"
Date: Tue, 07 Oct 2014 10:15:03 +0200
Importance: normal
Sensitivity: Normal
In-Reply-To: <>
References: <>
Content-Transfer-Encoding: quoted-printable
X-UI-Message-Type: mail
X-Priority: 3
X-Provags-ID: V03:K0:i2065a7oWgLKf8qYfMpzwVt+0Lf8w3q4e8r0K39AWM3 9cz3Lb59SLLN4geeCtHHjRncprfeAGEcwp3t3M7/l51UQwEajA apYDotKCGOcUQume3IeQh5qq3lkEABv0Ce4tT2HVwSDo+oRYyK yIAvCVuNTDUwDAm0w0QiwKvH2tyh0onCeEgjRED7/vKXn1k1Z/ dY2WP3RPaMcd7sKdvqzdcJXci/+mUvOKJ6MFCRRLGF6yFReFcx yyyIFVZPa8k7NlOKfqIIMF4hUrvDD4B/4GQIO80UdlE+TyXKNx 28HF/U=
X-UI-Out-Filterresults: notjunk:1;
Subject: Re: [Cfrg] Trusting government certifications of cryptography
X-Mailman-Version: 2.1.15
Precedence: list
List-Id: Crypto Forum Research Group <>
List-Unsubscribe: <>, <>
List-Archive: <>
List-Post: <>
List-Help: <>
List-Subscribe: <>, <>
X-List-Received-Date: Tue, 07 Oct 2014 08:15:12 -0000

On 10/3/14, 4:10 AM, D. J. Bernstein wrote:
>Torsten Schuetze writes:
>> Smart cards, i.e., its coprocessors and its ECC software
>> implementations, are always certified by Common Criteria, usually with
>> rather high assurance level. Don't you trust this certification in
>> principle? 
> explains how we factored 184 RSA-1024 keys
> from Taiwan's national "Citizen Digital Certificate" database. As you
> can see from, these keys were
> generated by government-issued smart cards that advertised all of the
> usual Common Criteria and FIPS certifications from BSI, NIST, and CSE.


you may remember that we discussed this RNG topic at the eve of last
years CRYPTO at Santa Barbara.

Following the discussion in this and the other threads on CFRG, I
should have better re-phrased my original question into: Do you
distrust Common Criteria (or government certification, as you call it)
in principle? Background of the question was to find out where does
the individual trust boundary of Alyssa run.

Of course, I cannot (and I will not) speak on behalf of BSI or another
``government agency´´ or on behalf of an independent evaluation lab as
T-Systems GEI or on behalf of any other official lab/agency. But
believe me, these presentations/these revelations have been discussed
thoroughly inside the German RNG community.

What do we have?
- We have a rather old CC EAL4+ certificate from January 2004 and a
  Assurance Continuity Maintenance Report from September 2004.
  (BTW, the first link to the Maintenance Report on your web site is
  wrong. The mirror link works.)

This certificate claims that the smart card hardware RNG TOGETHER
WITH ACCOMPANYING SOFTWARE provides a class P2 high physical true RNG
according to AIS 31, Version 1, 25.09.2001. The relevant technical
guide is Killmann/Schindler: A proposal for: Functionality classes and
evaluation methodology for true (physical) random number generators,
Version 3.1, 25.09.2001.

- Then we have your nice research paper and talks from the mid/end of

Of course, there was a major problem with this product. But this
doesn't mean necessarily that there is a major problem with the
certification / evaluation process.

P2 high requires that there are a) a startup test, b) a total failure
test, and c) a continuous on-line test. This is not surprising, but the
big difference, e.g., to NIST FIPS 140-2 is, that there must be a
so-called stochastic model, i.e., a ``Comprehensible and plausible
description of a mathematical model of the physical noise source and
the statistical properties of the digitised noise signal sequence
derived from it.´´ The on-line test has to be adapted specifically to
the stochastic model. Commonly this amounts in understanding your
entropy source (and not just passing statistical tests) and providing,
at best, lower bounds on the entropy. Or as Victor Fischer puts it: 
``It is quite easy to design a TRNG that will let the statistical
tests pass ... but it is much more difficult to know where the
randomness comes from and how much true randomness is there.´´

P2 high DOES NOT require that there is a cryptographic
post-processing of the internal random sequence (non-cryptographic
post-processing as von Neumann or Peres procedure does not count here).

So, obviously the mentioned product failed to implement an effective
total failure test and/or an effective continuous on-line test. 

The situation with RNGs is completely different with NIST FIPS.
Usually NIST is focused much more on deterministic RNGs, see the
infamous SP800-90A. Up to the publication of FIPS drafts SP800-90B and
SP800-90C you could not find much on entropy sources and their

(And with the last two FIPS drafts I see some problems, too. For
example, an entropy defect of order 2^{-64} can NEVER be estimated
experimentally. In AIS 31, we have now the requirement of an entropy
defect of less than 3E-03, practically E-4..E-5, i.e., average Shannon
entropy per bit exceeds 0.997. And for this estimate 2^30 random bits
are recommended to test. The full entropy sources from SP800-90B/C
would require such HUGE random data for estimating the defect
2^{-64}=5E-20 that this is practically impossible.)

At your website you wrote regarding FIPS mode or non-FIPS mode:
``However, this did not result in HICOS failing certification; it
merely resulted in extra words on the certificate saying that the
certificate was valid only when the card was "operated in FIPS

I presume that the card has been CC certified in FIPS mode. For CC we
only have 

``The confirmed assurance package is only valid on the condition that
      - all stipulations regarding generation, configuration and
        operation, as given in the following report, are observed,
      - the product is operated in the environment described, where
        specified in the following report.´´

This means, that the card has not been used properly, i.e., the
external preconditions have not been fulfilled. So, no problem with CC
certificate or CC process, but with individual usage.

By the way, the above mentioned certificate does only apply to the
smart card hardware. Usually, you either have a manufacturer library
for RSA with certificate or another CC certificate for operating
system and RSA application. I could not find anything like this at
your website. So the manufacturer/producer of the RSA application and
their evalution lab/certification THESE WERE THE PEOPLE TO BLAIM, NOT

However, even I have some criticism on Common Criteria. It is much too
easy to define a Target of Evaluation that is too narrow, sometimes
almost meaningless. For example, when I see an IPsec product evaluated
where the public-key and the symmetric key coprocessors are not in the
TOE. Or, when the organizational security policies and assumptions are
too wide, even unrealistic. But this just means: The statement ``CC
certification exists´´ is not very meaningful alone, one has to read
the complete security problem definition.

Another problem I sometimes have with CC is their reliance on keeping
design documents confidential and getting AVA points. I do not
advocate to publish everything, but one should not get any points for
confidential user manuals, etc.

> analyzes five contributing
> factors to this security disaster---low-quality hardware RNG, inadequate
> sanity checks, no run-time sanity checks, no post-processing, and
> inadequate initial response---and the complete failure of certification
> to prevent the disaster from occurring.

I admit the low-quality RNG and the missing/ineffective tests.
However, I do not see ``the complete failure of certification´´, only
then when you can prove that a smart card used in the CC specified
mode has been compromised.

Further, the analyzed product was rather old. This is no excuse and
shall not impair your results. But current AIS 20/31 standards,
effective since 2011, see Killmann/Schindler: A proposal for:
Functionality classes for random number generators, version 2.0,
September 18, 2011, recommend a class PTG.3 generator, e.g., a hybrid
physical true random number generator, basically a P2 high (now PTG.2)
with cryptographic post-processing (DRG.3). This type of RNG is/will
be REQUIRED for all German so-called qualified digital signatures, see
BSI Algorithmenkatalog 2014 (Übersicht über geeignete Algorithmen,
Bekanntmachung zur elektronischen Signatur, Bundesnetzagentur).

A PTG.3 RNG would have made the attack impossible. Nevertheless,
your result from last year provided one good reasoning for me
explaining the need of PTG.3 RNGs to our non-technical management
(besides certification requirement facts) :-)

As you may have noticed I have only written about Common Criteria
certification. This is the process I have the most experience with.
FIPS certification in general, for example, FIPS 140-2 and RNG
certification specifically, for example, SP800-90A, are completely
different. FIPS 140-2 is, in my opinion, rather old nowadays. FIPS
140-3 drafts, even they more than 5 years old now, had some good
ideas. Specifically with respect to side-channel evaluation.

This leads us back to the original problem: Elliptic Curve
Cryptography and Certification. Dan, I am sure you know the BSI
Guidelines AIS 46 Minimum Requirements for Evaluating Side-Channel
Attack Resistance of Elliptic Curve Implementations as Tanja was one
of the co-authors. All that I'm saying is that one should consider, at
least for applications in hostile environments, the complete set of
attacks and countermeasures. And not only timing attacks.

Common criteria may not be sufficient in some areas. But at least, it
is better than nothing (or everything else we have). Our aim as
security researchers/practitioners should be to improve that process
and not to discredit it.

Of course, in a perfect university world it would be fine to disclose
> We strongly recommend that the chip manufacturer publicly disclose
> full details of the RNG hardware in use and provide copies of the RNG
> hardware to researchers, allowing a thorough characterization of the
> physical failures of the RNG hardware on the 1024-bit cards and an
> analysis of the differences in the RNG hardware on the 2048-bit cards.  

and it would even interest me, personally. But what would happen if
you find something in millions of enrolled cards and cannot fix it
immediately? So, there are some differences between university and

> You can't reasonably ask CFRG to "trust this certification in
> principle".

What I do ask CFRG, is to consider established security evaluation as

And what I would like to ask CFRG further, is to consider the
different, more general ``performance´´ requirements as formulated in