Re: [Cfrg] Trusting government certifications of cryptography

Watson Ladd <> Tue, 07 October 2014 14:27 UTC

Return-Path: <>
Received: from localhost ( []) by (Postfix) with ESMTP id BBF3D1A6F86 for <>; Tue, 7 Oct 2014 07:27:28 -0700 (PDT)
X-Virus-Scanned: amavisd-new at
X-Spam-Flag: NO
X-Spam-Score: -1.7
X-Spam-Status: No, score=-1.7 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, FREEMAIL_FROM=0.001, MIME_8BIT_HEADER=0.3, SPF_PASS=-0.001] autolearn=no
Received: from ([]) by localhost ( []) (amavisd-new, port 10024) with ESMTP id qereSjqSpeo3 for <>; Tue, 7 Oct 2014 07:27:21 -0700 (PDT)
Received: from ( [IPv6:2607:f8b0:4002:c01::234]) (using TLSv1 with cipher ECDHE-RSA-RC4-SHA (128/128 bits)) (No client certificate requested) by (Postfix) with ESMTPS id 0BB161ACDB6 for <>; Tue, 7 Oct 2014 07:27:10 -0700 (PDT)
Received: by with SMTP id 29so3047880yhl.11 for <>; Tue, 07 Oct 2014 07:27:10 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;; s=20120113; h=mime-version:in-reply-to:references:date:message-id:subject:from:to :cc:content-type:content-transfer-encoding; bh=Fif9+Z81dUH7pfH4My8JHR2eC+qMCsJ87aor5yPjkGg=; b=DL/LDor2DFIPL71jDKYO0xmls8JHvg/nskWFs7r2nbA2ZCOGOCy3qTPxiuLRYjQbvw pzQShrGrhqzpZpUt77apRatm+MV6btbjRAWkedli9sLqv8vZ7Xk4QHQS794fcQ3wk/8f a6oy7i+1oKpJVwg9pfehLP9jXwu0hNZ/cknj5uZq5wS670tTSQuZ+iZEXPhyh54B7xt5 aAFX/k3dqSM+6VtLCZk3qnNH2tJKlpRx4zrnc960NSQPwtWR2YhIKTD/Hj1wguGrOjSu 6aDjmUV4PpzroRY97AYGwRP7d9ZZYXpAZFlzFdyP2cRfNt+r4T2dpIl6CQX+rOeUNvZB cvTw==
MIME-Version: 1.0
X-Received: by with SMTP id t21mr5897124yhl.65.1412692030038; Tue, 07 Oct 2014 07:27:10 -0700 (PDT)
Received: by with HTTP; Tue, 7 Oct 2014 07:27:09 -0700 (PDT)
In-Reply-To: <trinity-5e384bba-2edd-4ee2-a511-c8dc1caa173a-1412669702907@3capp-gmx-bs29>
References: <> <trinity-5e384bba-2edd-4ee2-a511-c8dc1caa173a-1412669702907@3capp-gmx-bs29>
Date: Tue, 07 Oct 2014 07:27:09 -0700
Message-ID: <>
From: Watson Ladd <>
To: Torsten Schütze <>
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
Cc: "" <>, "D. J. Bernstein" <>
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 14:27:28 -0000

On Tue, Oct 7, 2014 at 1:15 AM, "Torsten Schütze"
<> wrote:
> 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.
> Dan,
> 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.

This is not an isolated incident. Apple claims various things about
their certification (FIPS 140 lowest level), yet the core ECC
implementation does not validate points and has a timing+control flow
side channel. I'm sure we could find other problems with certified
products if we tried.

> 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
>   2013.
> 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
> evaluation.
> (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
> mode".´´
> 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

Why? The software can't make random numbers without the hardware. The
configuration issue is part of the problem: it's clear that people
don't understand the limits of the certification, or how to ensure
they are configuring things correctly. Taiwan had every incentive to
get this right and couldn't.

> 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.

Most applications are not smart-cards. I don't see why we need to take
a 50% performance hit on every TLS connection, for devices that are
generally deployed in specialized systems anyway. The argument that
some devices will need to do this doesn't convince me either: why
would they need to connect to arbitrary websites? Even if those are
true, what's wrong with the Brainpool curves for this purpose?

The quality of certification has nothing to do with this question:
it's entirely a question about the relevance of power-side channel
attacks to most ECC deployments.

> 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
> anything
>> 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
> industry.
>> 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
> Regards,
>     Torsten
> _______________________________________________
> Cfrg mailing list

"Those who would give up Essential Liberty to purchase a little
Temporary Safety deserve neither  Liberty nor Safety."
-- Benjamin Franklin