A crazy thought?

[Dave Howe]

Allen wrote:
> Hi Gang,
> 
> In a class I was in today a statement was made that there is no way that 
> anyone could present someone else's digital signature as their own because no
> one has has their private key to sign it with. This was in the context of a
> CA certificate which had it inside. I tried to suggest that there might be
> scenarios that could accomplish this but was told "impossible." Not being
> totally clear on all the methods that bind the digital signature to an
> identity I let it be; however, the "impossible" mantra got me to thinking
> about it and wondering what vectors might make this possible.

Awareness of the failure models of various PKI solutions is an important part of
using and designing uses for them. There are many, many failure models for the
current x509/Certification Authority model used by ssl.

(everyone already familiar with the failure modes should probably hit "next
message" now, unless they want to double check I am not giving out bad advice;
this email is going to get rather long :)

Consider the following steps. I will predefine three actors here -
[SITE] which for email is the *recipient*, for web traffic is the server owner.
[USER] which is the mail sender and/or site user - originator of protected data.
[CA] which is the certificate authority

1. [CA] generates and stores securely a private key

  This is a once-in-a-decade event, but even so, there are failure modes. One
  possible mode is to use political pressure (or just bad coding) to force one
  of the two primes used in RSA to be either fixed or from a very small subset
  of possible primes (aka "canned primes"). As you can imagine, finding the
  private key becomes near trivial if you know one of the two primes in
  advance... We can move onto the security of the key later.

2. [CA] generates and stores a public certificate using the private key

  This at least is without any real issues (except security of the private key
  of course). In practice, this would be the same operation as (1) but need not
  be.

3. [CA] transmits the public key verifiably to the end recipients

  This is actually more complex than it sounds - I would guess 99% of the keys
  everyone has on their machine (if not 100%) were supplied to them with the
  browser, or in the case of IE, preinstalled on the machine. The vast majority
  of users have no idea how to even display those keys, never mind check them.

  To verify, ask yourself this question. For each web browser or email package
  installed to your machine,

  a) Where are root keys stored?
  b) How do I view them?
  c) Where is the public key or hash I should check?
  d) where do I obtain a known-good copy of that so I can verify it?

  The answers to some of those might surprise you (for instance, IE stores its
  root certs unprotected in the registry, and your AD administrator can override
  them at will; IE keys are used by almost everything supplied by microsoft,
  including execution digital signatures and email - Outlook or OE). All are
  trivially over-ridable by an attacker with write access to your machine.

4. [SITE] Generates and stores securely a private key

  Pretty much the same provisos apply here as did for the CA. Do you know and
  can you trust your key generation software? IIS for instance relies on a tool
  supplied my microsoft for the purpose; Apache usually suggests OpenSSL, email
  clients usually use their associated web browser for an interactive generation
  of both key and CSR while connected to the CA's website. However as another
  exercise - for each, where (and how) is the private key stored and protected?

5. [SITE] Generates and forwards to the CA a certificate signing request (CSR)

  Modulo the usual private key concerns, this is usually trouble-free (and
  again, is usually a combined step with key generation)

6. [CA] Receives and (for a payment) signs the CSR with its private key.

  This is where things get interesting. The certificate generated at this stage
  may or may not use exact copies of the data in the CSR; It may or may not be
  signed directly by the CA master key (for many CA's, their master key is kept
  offline in a bank vault and used to sign an intermediate key which is used for
  actual CSRs. In fact, it may sign *multiple* intermediate keys, for a number
  of good reasons (which we won't go into at this stage) but which also
  introduce another possible attack vector for a TLA with the power to force a
  CA of his choice (or someone with access to a private key there) to do
  selected tasks.

  Several potential attacks require that this transmission to the CA be
  intercepted and fulfilled by someone other than the CA themselves.
  Conventional wisdom says that there is little or no risk caused by site
  certificate substitution, and to a great extent this is correct - other than
  the possible forcing of the symmetric encryption method to one breakable by
  the TLA, there is little or no benefit to such a substitution.

7. [CA] Transmits signed certificate to the site

  Attacks possible at stage (6) also occur here - the transaction isn't complete
  until you have your certificate safely on your machine.

8. [SITE] Installs certificate into appropriate software, along with any
          intermediate certificates needed

  I am not aware of any attacks at this stage; willing to be enlightened
  though...

9. [SITE] transmits its shiny new certificate to the user

  This is an important stage, and one where the vast majority of MITM attacks
  take place. For web services, this is the https handshake; for email, the
  vector is typically sending a signed message to the user (but of course you
  can just send the key if you want, assuming the user knows how to import a key
  directly)

  If you are gnashing your teeth right now and saying but THAT'S THE PART I
  NEEDED TO KNOW - WHY IS HE GLOSSING OVER IT LIKE THAT! bear with me - I will
  come back to signatures once I have finished discussing the more general case
  (encryption)

  Normally, in order for future MITM intercepts to be readable (without
  compromising the SITE private key) the attacker must replace the proffered
  certificate with one of his own, so he can read the traffic.

  Alternately, an attacker with control over the user's machine can simply
  substitute the imported certificate in the user's profile with one of his own
  creation.

10. [USER] Establishes a symmetric key for use during the transmittal

  For web traffic, that would be an interactive process with the site (or more
  accurately, whomever you are speaking to who holds the private key matching
  the certificate you have). For email, that would be a local generation process
  in accordance with the supported methods outlined in the certificate.

11. User encodes and transmits the data

  Perhaps obviously, this would be a two-way conversation for a website, a
single transaction for an email.





But of course we are more concerned with digital signatures. To digitally sign
an email, the following elements take place:

1. [SITE] calcuates a cryptographically secure hash from the document

  An important question at this stage is - what constitutes the document? For
  many email systems, this is the body text of the email, excluding any
  attachments or inline graphics.

2. [SITE] encrypts this with his private key

  We will gloss over the padding and similar aspects of this, as they are not
  relevant to the problem.

3. [SITE] appends the encrypted checksum to the message.

  In S/MIME, the sender's certificate is often bundled as well; this makes
  signatures a convenient way to convey your certificate to an end user.

4. [SITE] transmits the message to the recipient

  For a MITM attack, this is usually where the attack takes place. Note if the
  message is, in addition to the signature, encrypted to the recipient, the MITM
  attacker must first have either compromised the recipient's private key or
  replaced the sender's copy of the recipient's certificate with its own.

5. [USER] recalculates the hash value of the document

  Obviously, this must match the value in the signature. Note that one
  theoretical attack is to substitute in the message a document which contains
  differing text, but which has the same hash as the original document. While no
  known attack can do this, there is a weaker form of the same principle (two
  documents, both generated by the same attacker, which have the same hash)
  which can be a viable attack in certain scenarios)

6. [USER] Validates the site's key(s) against the CA key(s) it holds

  Obviously, this is where substitition of the CA's key (or creation of a "new"
  CA specifically to be added to user's machines) bears its fruit.

7. [USER] uses public key from certificate to verify hash values match.




NONE of this is specific to email - "Document" could as easily be a PDF, and the
"message" (bundle of Document, signature, certificate, and any other related
items) sent as a zipfile with detached signature inside as a PDF (which has tags
to incorporate a digital signature) or other stucture, by post, hand or file
transfer. The important element is that the user is in receipt of a bundle, some
or all of which are hashed, and that that hash matches one that is encrypted
using a private key the user believes (due to the mechanisms available to him)
belongs to the user.

Ok, now we have that framework in place, we can more clearly outline the attacks
against such a system.

a) Case: Document is not signed
  1) Subcase: Fake seal attack

    For this attack, it is required only that the attacker affix to the document
    text or images that imply or falsely state that the document is digitally
    signed; as an alternate, the document could include a scanned image of the
    sender's physical (pen and ink) signature, possibly even by the sender's
    intention.

    Belief that a scanned image of a pen signature constitutes a "electronic
    signature" is fairly common, and in fact outside of our own tight
    mathematical meaning, could be correct.  Most legal jurisdictions make no
    distinction, and in those jurisdictions, typing "I SIGN THIS" on the end of
    a text file is as legally binding as the formal X509 procedure, provided you
    can prove it was done by the "signer" - the act of signing demonstrates
    intent to be bound by a document, the actual procedure is irrelevant; that
    is why an illiterate 'X' on a document before two witnesses is as fully
    binding as a sworn oath.

    Equally, it is possible both the recipient and the signer implemented such
    an electronic document in good faith, but it is not binding in the
    jurisdiction whose law the document will be interpretted in. It is also
    possible that one or the other of the parties has (after the fact, and
    wishing to escape a contract) done some jurisdiction shopping to arrange for
    this to be true.

b) Case: Document is part signed
  1) Subcase: bad encapsulation

    As has already been discussed, it is possible that only part of the
    perceived whole (for instance, a html email which references an attached or
    remote image which is not itself part of the hash, although the reference
    is) is subject to change after the fact, which alters the displayed document
    in ways hard to explain to a non-technical jury, and which in any case would
    render the document invalid due to this flaw (regardless of what the
    original said)

  2) Subcase: Dynamic content

    This is a more subtle attack, but one subject to technical analysis;
    technically, this is merely a special case of the first subcase, in that it
    introduces a dependency on some element outside the scope of the signature;
    the distinction (if there is one) is that there is some interpreted element
    within the Document which is aware of its environment, and makes changes to
    the rendering of that document should it find itself in an environment other
    than the one in effect when first signed - an example would be a document
    which checks the current date upon the machine it is running and, after a
    certain time has elapsed (three months say) makes changes in the displayed
    text so as to alter the meaning of the document in its author's favour.

    This is a powerful attack, in that it requires no access to the recipient's
    copy of the document after the signature is affixed, nor does it introduce a
    dependency on an external element (such as a remote website) which may not
    be present at all at some point, thus revealing to the recipient (possibly
    at a point inconvenient to the author) that some elements of the document
    lie outside of the scope of the signature.

    It is however also a risky attack, as competent analysis would show the
    rendering mechanism for what it is, a deliberate attempt to cause the
    displayed form of the document to change in the author's favour after the
    signature was affixed, to induce the recipient to accept as signed a
    document they would otherwise not so accept (i.e. fraud; there could be an
    argument made that they should have checked the document before signatures
    were affixed, but I suspect a reasonable jury would conclude that checking
    for digital "invisible ink" would require a level of technical competence
    far beyond the norm. To reduce the risk for the attacker, a platform (such
    as pdf with certain additions directly sponsored by adobe) could be chosen
    where the rendering is deliberately obscured from the recipient by a closed
    source module, the defeating of which is a criminal act in the USA.

c) Case: Document is signed with fake key
  1) Subcase: Fake CA

    An important prerequisite for this attack is that the recipient have on
    their equipment a ca "root" certificate not genuinely issued by a commonly
    accepted CA.  The exact mechanism here could vary, but possible vectors
    could be:
    * Compromise of browser vendor (ie, key supplied with browser)
    * Compromise of host by virus or other code vector
    * Compromise of host by user (social attack, inducing user to accept the
      root key by their own actions)
    * Compromise of host by direct action (ie, AD policy or simply modifying the
      key registry while the user is away from the machine)

    The effect of the attack, perhaps obviously, is that an attacker-generated
    certificate would be accepted as valid by the recipient; one possible
    realization of the attack would be to remove the key, leaving the recipient
    with a document which no longer verifies as signed (and hence, which is
    invalid or at least indistinguishable from one created by the recipient
    themselves)

  2) Subcase: Compromised CA

    In this case, the key verification chain is valid but was not issued
    knowingly by the CA or its agents; this could be done by having a
    confederate issue the certificate, issue an intermediary (ie, a certificate
    which can be then used to sign other certificates) or disclose the private
    key for the master or intermediate used by that confederate in the course of
    his work, so that valid (but not legitimate) certificates can be issued.

    Additionally, it is possible that social engineering caused an otherwise
    uncompromised employee to issue a key to someone not entitled to it -
    typically, a CA will verify identity by email exchange - if you respond
    appropriately to a testprobe email (and your payment clears) the certificate
    is issued. Note all CAs have no liability in this regard - they could issue
    keys routinely to anyone who asks, and there would be no legal impact
    (although I guess a lot of people would then remove the root CA key from
    their machines, making certs issued by that CA worthless - if they found
    out, and if they knew how)

  3) Subcase: Co-operating CA

    In the case of a TLA, they may well be able to command direct compliance
    from the CA they use to validate this attack - this is structurally
    different from the previous subcase only in that any attempt to validate the
    key by out-of-band methods with the CA would meet acknowledgement that the
    key was valid (as opposed to examples of the above where queries as to
    issuance of a certificate could lead to its cancellation and possibly legal
    or internal action against the compromised employee) - ie, as far as the CA
    will tell you, the issuance was "good" and the key is genuine.

d) Case: Document is signed with real key
  1) Subcase: Hash compromise

    As has previously been discussed, it is possible by the mechanisms of
    hashing that there exist two documents, both in the control of the same
    individual, which when hashed yield the same value. Hence that individual
    could induce the signer to sign the first document (which contains terms
    favourable to the signer) then transfer that signature to the *second*
    document (which contains terms unfavourable to the signer) which is then
    "signed"

    Successful use of the second document would usually require that the first
    be discarded by the signer (which may or may not happen), that the first be
    more valuable to the signer than the cost of the second (as revealing the
    collision would almost certainly invalidate both documents) and in any case
    require that the signer or his representative be able to extract the hash
    value of both documents (possibly all documents the signer has ever signed,
    just to locate the first document) and successfully explain to a court why
    the hash collision was almost certainly a deliberate act and not a strange
    twist of fate (good luck with that; while the odds of a collision are worse
    than that of winning the lottery, *someone* wins the lottery every week; its
    only a matter of time before someone, somewhere in the world signs purely by
    accident two documents that have the same hash, and it *could* have been
    you)

    A smart investigator will probably not even consider hash collision as a
    possibility until all other avenues are exhausted; even then, he may not be
    able to locate the first document if its terms have already been fulfilled
    and it is "expired" in the eyes of its recipient.

2) Subcase: Process compromise

    For this to be an attack, the signer must be induced to sign something
    either without reading, or in the belief he is signing something different;
    a variation would be the case where he is induced to sign two items in close
    succession, in the belief he is only signing one.  Automated signing systems
    could be vulnerable to such attacks depending on design; contactless
    identity systems such as are frequently proposed for national identity or
    passport schemes are another such group - by having a medium range
    transceiver, it could be possible in some designs for a random passerby in
    the street to trigger your contactless card while still in your wallet and
    cause it to sign something you have not seen.

    Similarly in the uk, credit card transactions are protected by "chip and
    pin"  - the mechanism is not disclosed for this, but it is thought to be a
    digital signature system using a dedicated cryptochip, unlocked by the pin.

    One known attack on this system is a relay attack - a confederate in a food
    retailer presents for settlement a modest food bill, and offers a card
    reader so the customer may insert his card and key his PIN to pay for the
    meal.  Unknown to the customer, the attacker is standing in *another*
    retailer, this time for something of high resale value - a jewellers, say -
    and is currently admiring something many times the cost of the meal - a ring
    for several hundred dollars.

    The attacker inserts into the retailler's similar card reading device a card
    which looks legitimate, but in fact is a short-range transceiver to a larger
    more powerful device in the attacker's pocket. this relays to another device
    at the food outlet, which is embedded in the card reader being presented to
    the customer. As the customer enters his PIN, the digits are relayed to the
    attacker as a lcd display on the second device; he reads this, and enters
    them onto the device belonging to the retailer. The retailer's device then
    authorizes the transaction, by PIN, against the customer's card some yards
    away - it all checks out, so the transaction goes though and the attacker is
    now the happy owner of an expensive and high-resale-value object - and the
    customer is now the unhappy recipient of a large bill for an object he did
    not purchase (and which when he discovers it on his statement at the end of
    the month, will probably not be able to relate to a meal he ate which does
    not appear on his statement at all). The bank of course says their system is
    infallible, so it *must* have been a valid transaction and refuses to refund
    the money.

    Note this is *not* a theoretical attack - people have been caught doing
    this, hence the great detail of the method I was able to show.

3) Subcase: key compromise

    By contrast, this is a much simpler attack. By compromising the owner's
    ztorage of the key, the attacker is able to obtain access - either directly
    (by using the key while the legitimate owner is not in direct physical
    possession of the device) or indirectly (by extracting the key and using it
    on hardware of the attacker's choosing)

    A common example of the former is where other household residents or thieves
    obtain physical possession of a token (eg - a credit card) and its
    associated unlock code (sadly, many people still keep a slip with a PIN in
    the same wallet as their cards; in addition, for remote use the usual PIN is
    a three digit code *printed on the back of the card* but this is not
    directly relevant as no on-card pki is currently party to a remote
    transaction; users typically do not have the hardware to access a physical
    token like a chip-and-pin card at home)




Anyhow, I hope some or all of this is of assistance the next time your lecturer
claims PKI is infallible :)

---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at metzdowd.com