Cryptography – Page 2

Pomcor Granted Patent on How to Implement a PKI on a Blockchain

Pomcor has just been granted US Patent 10,764,067, “Operation of a Certificate Authority on a Distributed Ledger”. A distributed ledger is a database replicated across of set of nodes and populated by transactions issued by the nodes. A distributed consensus algorithm is used to achieve consensus among the nodes on the order of the ledger transactions. A blockchain is a distributed ledger in which ledger transactions are grouped into blocks, and consensus on the ordering of the ledger transactions is based on consensus on the validity and ordering of the blocks.

Some distributed ledgers, e.g. the Ethereum blockchain, provide on-ledger storage by allowing a ledger transaction to contain an instruction to store data in an abstract ledger store identified by a ledger address. As ledger transactions including such instructions are propagated to the nodes of the ledger through the peer-to-peer protocol each node executes the instruction locally, on a local replica of the abstract ledger store that is part of the node’s local replica of the ledger state.

A public key infrastructure is a system for issuing, revoking and validating public key certificates, implemented by a hierarchy of certificate authorities (CAs). The storage replication functionality provided by a distributed ledger with on-ledger storage can greatly simplify the implementation of a PKI.

I do not advocate setting up a blockchain or other distributed ledger just for the purpose of implementing a PKI. But if a distributed ledger has already been set up or is being set up for some other purpose, it can be opportunistically used to implement a PKI, or to simplify the operation of an existing PKI.

I also do not advocate storing or transmitting certificates on the blockchain. That would be a bad idea for privacy reasons, and there is no need to do so. A CA operating on a distributed ledger can issue any kind of certificates, including certificates whose subject is a machine, such as a web server or an IoT device, and certificates whose subject is a person. Each kind of certificate can be stored together with the corresponding private key in any kind of secure storage customarily used for that kind of certificate. In a presentation at ICMC 2017 I explained how JavaScript Web APIs can be used to store personal cryptographic credentials in the browser.

Here is a summary of how a PKI can be implemented on a distributed ledger; details can be found in the patent. A subject requests a certificate as usual by submitting a certificate signing request (CSR). The CA creates a certificate and transmits it to the subject, without ledger involvement in the transmission; there is no need for the subject to have access to the ledger. But the CA also issues an issuance transaction on the ledger with an instruction to store a cryptographic hash of the certificate in a certificate issuance store controlled by the CA; and when the certificate needs to be revoked, it issues a revocation transaction on the ledger with an instruction to store the serial number of the certificate in a certificate revocation store also controlled by the CA. As those transactions propagate throughout the ledger, the instructions are executed by all the nodes in their local replicas of the stores.

This greatly simplifies the process of verifying that a certificate is valid.

Instead of verifying the signature on the certificate, the verifier can just check that the hash of the certificate is present in the certificate issuance store controlled by the CA that has issued the certificate. In fact, the signature can be omitted from the certificate if all verifiers have access to the ledger, substantially reducing the size of the certificate and thus the bandwidth and latency cost of presenting the certificate.

And the verifier can check that the certificate has not been revoked simply by checking that its serial number is not present in the certificate revocation store controlled the CA. This obviates the need for the CA to provide a highly available Online Certificate Status Protocol (OCSP) server and/or a regularly updated Certificate Revocation List (CRL); and for the verifier to query the OCSP server or maintain a local copy of the CRL by periodically retrieving signed updates.

A Formal Proof of Omission-Tolerant Integrity Protection

This is the fourth and last part of a series on omission-tolerant integrity protection and related topics. See also part 1, part 2, and part 3. A technical report on the topic is available on this site and in the IACR ePrint Archive.

In part 3 we saw how the system parameterization concept introduced by Boneh and Shoup in their Graduate Course in Applied Cryptography makes it possible to provide a formal definition of collision resistance for keyless hash functions. In this last post I will explain how that definition, and the security and system parameters used in the definition, are used in the proof of Theorem 3 of the technical report, which states that the root label of a typed hash tree can serve as an omission-tolerant checksum of an encoding of a set of key-value pairs.

Mapping a Formal Definition of Collision Resistance to Existing Implementations of Hash Functions

This is part 3 of a series on omission-tolerant integrity protection and related topics. See also part 1 and part 2. A technical report on the topic is available on this site and in the IACR ePrint Archive.

When a cryptographic hash is used as a checksum of a bit string, security depends on the collision resistance of the hash function. When the root label of a typed hash tree is used as an omission-tolerant checksum of a set of key-value pairs, security also depends on the collision resistance of a hash function, in this case of the hash function that is used to construct the typed hash tree. (It may also depend on the preimage resistance of the hash function depending on how the set is encoded, as we shall see in another post of this series.) The formal proof of security in the technical report is therefore based on a formal definition of collision resistance. But, surprising as this may seem, there is no standard, widely used, formal definition of collision resistance for the keyless, or unkeyed hash functions such as SHA256 that are used in practice.

Collision resistance is hard to define

The concept of a hash function collision is simple and clear enough: it is a pair of distinct elements of the domain of the hash function that have the same image. The concept of collision resistance, on the other hand, is difficult to define. The reason for this, as explained for example by Katz and Lindell in their Introduction to Modern Cryptography (Chapman & Hall/CRC, 2nd edition, 2014, bottom of page 155), is that collisions exist, and for any collision there exists a trivial algorithm that hardcodes the collision and outputs it in constant time.

Using an Omission-Tolerant Checksum for Selective Disclosure of Attributes Asserted by a Public Key Certificate

This is part 2 of a series on omission-tolerant integrity protection and related topics. A technical report on the topic is available on this site and in the IACR ePrint Archive.

The first post of this series introduced a new technical report that describes the concept of an omission-tolerant checksum in a broader context than the rich credentials paper and includes a formal proof of security in an asymptotic security setting. In this post I give an example showing how an omission-tolerant checksum implemented using a typed hash tree can provide selective disclosure of attributes asserted by a public key certificate.

Typed hash trees vs. Merkle trees

A typed hash tree is a hash tree where every node has a type in addition to a label, and the label of an internal node is a cryptographic hash of an encoding of the types and labels of its children. A distinguished type is assigned to all the internal nodes, and may also be assigned to some of the leaf nodes.

Hash trees were first proposed by Merkle. In a Merkle tree, each internal node is labeled by a hash of the concatenation of the labels of its children, and each leaf node is labeled by a hash of a data block. In both a typed hash tree and a Merkle tree, a subtree can be pruned without modifying the root label of the tree. (By “pruning a subtree” we mean removing the descendants of an internal node.) But in the case of a Merkle tree this is a “bug” to be mitigated if the tree is to provide integrity protection, while in the case of a typed hash tree it is a “feature” that allows the root label of the tree to be used as an omission-tolerant checksum.

An Omission-Tolerant Cryptographic Checksum

This is part 1 of a series on omission-tolerant integrity protection and related topics. A technical report on the topic is available on this site and in the IACR ePrint Archive.

Broadly speaking, an omission-tolerant cryptographic checksum is a checksum on data that does not change when items are removed from the data but makes it infeasible for an adversary to modify the data in other ways without invalidating the checksum.

We discovered the concept of omission-tolerant integrity protection while working on rich credentials. A rich credential includes subject attributes and verification data stored in a typed hash tree. We noted in an interim report that the root label of the tree could be viewed as an “omission-tolerant cryptographic checksum”. Prof. Phil Windley, who read the report, told us that he had not seen the concept before, and asked if we had invented it. We then added a section on typed hash trees and omission-tolerant integrity protection to the final report.

We’ve now written a new technical report that discusses omission-tolerant checksums and omission-tolerant integrity protection in a broader context than rich credentials. The main contributions of the new paper are a formal definition of omission-tolerant integrity protection, a method of computing an omission-tolerant checksum on a bit-string encoding of a set of key-value pairs, and a formal proof of security in an asymptotic security setting that uses the system parameterization concept introduced by Boneh and Shoup in their online book.

I have not said much in this blog about omission-tolerant integrity protection, and there is a lot to say: how an omission-tolerant checksum can be used to implement selective disclosure of subject attributes in public key certificates; how public key certificates with selective disclosure could easily provide security and privacy for client authentication in TLS; what’s special about Boneh and Shoup’s system parameterization concept and how we use it in our definitions and proofs; how can a typed hash tree provide omission-tolerant integrity protection whereas a Merkle tree cannot; and a number of narrower but no less interesting topics. This is the first of a series of posts on these topics.

Random Bit Generation with Full Entropy and Configurable Prediction Resistance in a Node.js Application

This is the fourth and last post of a series describing a proof-of-concept web app that implements cryptographic authentication using Node.js with a MongoDB back-end. Part 1 described the login process. Part 2 described the registration process. Part 3 described login session maintenance. The proof-of-concept app, called app-mongodb.js, or simply app-mongodb, can be found in a zip file downloadable from the cryptographic authentication page.

In app-mongodb, random bits are used on the server side for generating registration and login challenges to be signed by the browser, and for generating login session IDs. On the client side, they are used for generating key pairs and computing randomized signatures on server challenges.

In quest of full entropy

There are established methods for obtaining random bits to be used in web apps. On the client side, random bits can be obtained from crypto.getRandomValues, which is part of the W3C Web Crypto API. On the server side, /dev/urandom can be used in Linux, MacOS and most flavors of Unix. However, neither of these methods guarantees full entropy.

Login Session Maintenance in Node.js using Express and Handlebars

This is part 3 of a series of posts describing a proof-of-concept web app that implements cryptographic authentication using Node.js with a MongoDB back-end. Part 1 described the login process. Part 2 described the registration process. This Part 3 is concerned with login session maintenance in a broader scope than cryptographic authentication. Part 4, concerned with random bit generation, is now available. The proof-of-concept app, called app-mongodb.js, can be found in a zip file downloadable from the cryptographic authentication page.

Update. The name of the constant securityStrength has been changed to rbgSecurityStrength as noted in the last post of the series and reflected in one of the snippets below.

At first glance it may seem that there is no need for login session maintenance in a web app that implements cryptographic authentication with a key pair. Every HTTP request can be authenticated on its own without linking it to a session, by sending the public key to the back-end and proving possession of the private key, as in the login process described in Part 1. That login process relied on the user supplying the username in order to locate the user record, but this is not essential, since the user record could be located in the database by searching for the public key, which is unique with overwhelming probability.

But login sessions provide important login/logout functionality, allowing the user to choose whether to authenticate or not. A member of a site accessible to both members and non-members, for example, may choose to visit the site without authenticating in order to see what information is made available by the site to non-members. Also, the proof of possession of the private key has a latency cost for the user due to the need to retrieve the challenge from the server, and a computational cost for the server and the browser. These costs are insignificant if incurred once per session, but may not be insignificant if incurred for every HTTP request.

The app discussed in this series, app-mongodb.js, implements login sessions in the traditional way using session cookies. Having said that I could stop here. But the Express framework used in the app provides interesting ways of implementing traditional login sessions, which are worth discussing.

Credential Registration for Cryptographic Authentication with Node.js and MongoDB

This is part 2 of a series of posts describing a proof-of-concept web app that implements cryptographic authentication using Node.js, Express, Handlebars, MongoDB and Mongoose. All parts are now available. Part 1 describes the login process. This Part 2 describes the registration process. Part 3 describes login session maintenance. Part 4 is concerned with random bit generation.

Update. The name of the constant securityStrength has been changed to rbgSecurityStrength as noted in the last post of the series and reflected in the snippets below.

Part 1 of this series described the login process of a proof-of-concept Node.js application that implements cryptographic authentication using a MongoDB database back-end. The app, called app-mongodb.js, can be found in a zip file downloadable from the cryptographic authentication page, where it is bundled together with a simpler app that has the same functionality and the same front-end but emulates the database using JavaScript objects, provided for comparison.

This post describes the registration process of app-mongodb.js. The app has a registration page reachable from a link found under a top-of-page login form in the public pages of the app. The registration page has a form where the user enters a username, a first name and a last name, but no password. The first and last names are representative of any info that the user may be asked to provide in a full-fledged application.

The registration process of app-mongodb.js has a structure similar to that of the login process described in Part 1. The browser sends an HTTP POST request to the /register-username endpoint of the server, conveying the username, first name and last name. The server creates a user record, called a “user document” in MongoDB terminology, and responds with a JavaScript POST redirection. The JavaScript POST redirection consists of downloading a script that generates a key pair, signs a server challenge with the private key, and sends the public key and the signature to the /register-public-key endpoint in a second HTTP POST request. The server cryptographically validates the public key, verifies the signature, and adds the public key to the user document.

The following code snippet shows how the server processes the first HTTP POST request, received at the /register-username endpoint.

Cryptographic authentication with Node.js and MongoDB

This is part 1 of a series of posts describing a proof-of-concept web app that implements cryptographic authentication using Node.js, Express, Handlebars, MongoDB and Mongoose. All parts are now available. Part 2 describes the registration process. Part 3 describes login session maintenance. Part 4 is concerned with random bit generation.

Update. The name of the constant securityStrength has been changed to rbgSecurityStrength as noted in the last post of the series and reflected the snippets below.

The PJCL library allows full-stack web developers to use the same cryptographic API on a browser front-end and a Node.js back-end, as explained here. At the last IIW we demoed a web app, implemented using Node.js and Express, that featured cryptographic authentication with a DSA key pair, using PJCL both in the browser to sign a challenge and in the Node.js server to verify the signature. Initial implementations of the app were complicated by having to work around a Firefox bug, which we reported and was confirmed. But eventually we found a simple way of bypassing that bug.

The IIW demo app was very simple. It only had a public “home page” and a private “welcome page”, and it emulated the back-end database using JavaScript objects. We are now releasing a more substantial proof of concept of cryptographic authentication that again uses Node.js and Express, but this time uses a MongoDB database, accessed via a Mongoose driver. Besides using an actual rather than emulated database, the new proof-of-concept app includes features such as on-the-fly login and garbage collection of incomplete user registrations. It also shows how to implement random bit generation with full initial entropy and configurable prediction resistance, which I plan to discuss in another blog post of this series.

The new app is available in a new cryptographic authentication page of the Pomcor site. It is bundled together in a zip file with a simpler app that has the same functionality and the same front-end, but emulates the database using JavaScript objects. The two apps, called app-mongodb.js and app-nodb.js, share the same static files and views. Comparing the two apps may help with understanding the code of the more complex app-mongodb.js. The apps may be run in any Node.js server with access to a MongoDB database and a /dev/random device file, as explained in a README file included in the zip archive.

A Bypass of the Firefox POST Redirection Bug

I’m happy to report that we have found a way of bypassing the Firefox POST redirection bug discussed in the previous post, obviating the need for code changes to cope with the redirection replay by Firefox when the user clicks the back button. While waiting for the bug to be fixed, this will simplify the implementation of web apps that rely on POST redirection, including apps that use cryptographic authencation or federated login. We have revised again the sample web app demoed at the last IIW, this time to simplify it by taking advantage of the bug bypass.