Re: [Cfrg] Trusting government certifications of cryptography

Dirk Feldhusen <> Tue, 07 October 2014 16:08 UTC

Return-Path: <>
Received: from localhost ( []) by (Postfix) with ESMTP id 9F7501A01A8 for <>; Tue, 7 Oct 2014 09:08:58 -0700 (PDT)
X-Virus-Scanned: amavisd-new at
X-Spam-Flag: NO
X-Spam-Score: -1.95
X-Spam-Status: No, score=-1.95 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, HELO_EQ_DE=0.35, MIME_8BIT_HEADER=0.3, RCVD_IN_DNSWL_LOW=-0.7] autolearn=ham
Received: from ([]) by localhost ( []) (amavisd-new, port 10024) with ESMTP id x88Jv43j7tdB for <>; Tue, 7 Oct 2014 09:08:55 -0700 (PDT)
Received: from ( []) (using TLSv1.1 with cipher AECDH-AES256-SHA (256/256 bits)) (No client certificate requested) by (Postfix) with ESMTPS id CBFE41A01A5 for <>; Tue, 7 Oct 2014 09:08:54 -0700 (PDT)
Received: from imail (imail.src-gmbh.lan []) by (Postfix) with SMTP id 74F11959A; Tue, 7 Oct 2014 18:08:51 +0200 (CEST)
Message-ID: <>
Date: Tue, 07 Oct 2014 18:08:48 +0200
From: Dirk Feldhusen <>
User-Agent: Mozilla/5.0 (Windows NT 6.1; WOW64; rv:24.0) Gecko/20100101 Thunderbird/24.6.0
MIME-Version: 1.0
To: Watson Ladd <>, Torsten Schütze <>
References: <> <trinity-5e384bba-2edd-4ee2-a511-c8dc1caa173a-1412669702907@3capp-gmx-bs29> <>
In-Reply-To: <>
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 16:08:58 -0000

Am 07.10.2014 16:27, schrieb Watson Ladd:
> 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.
OK, by a certifcation it cannot be guaranteed that the product is
unbreakable. The statement provides an estimate for the minimal effort
which is required to break it. I am no FIPS expert, but to my opinion
this example shows that a low level evaluation is not an adequate
measure to detect vulnerabilities on implementation level. Contrariwise
a CC EAL4 evaluation (or higher) requires the evaluator to get access to
the source code by ADV_IMP.

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

The information how to use the product in a secure way is given in the
guidance which has to be delivered together with the product.
The smart card hardware is not able to make every possible software on
it secure, so you need also a certificate for the RSA implementation,
which implies that the software uses the hardware properly.

>> 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.
To exclude the possibilty of power or EM side channel you need the
assumption that the attacker has no physical access to the device.
As I understand Torsten the main problem here are special primes which
are harder to secure against such side channel leakage.
>> 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
>> Common Criteria as ONE BLOCK OF BUILDING TRUST.
>> 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