Pankaj Gupta
June 6 2021
Summary
This post describes a simple but foundational new cryptographic primitive – called LimitedUseKey or LUK – introduced in Android 12 (aka Android S, to be released later this year). This crypto primitive has far reaching implications on secure detection of decentralized double-spend in mobile devices. Hopefully this primitive and its variants enable new applications that are decentralized, peer-to-peer, faster and work offline (without Internet connectivity). Examples include digital ticketing, coupons, payments systems and Central Bank Digital Currencies (CBDCs).
This post is a longer, hopefully clearer description of the primitive I first described in my tweetstorm on the topic in April 2021. Much of the underlying work on the primitive was done when I was part of Google Pay. What is described here is available publicly but not documented or explained anywhere, including the publicly available APIs and their implications and use cases for mobile apps and developers to leverage, now that the primitive is available in Android 12.
When this primitive is combined with a few other mechanisms to provide anonymity and transitivity as I described in this blog post, the persistent question among CS researchers and economists alike of whether true digital tokens are possible at all is definitively addressed. Hopefully that removes a fundamental blocker to achieving the vision of Digital Cash which can now have properties identical to those of Physical Cash.
Given the simple implementation of this new primitive and its power in bringing new foundational use cases and capabilities, I earnestly request all operating systems (IOS/MacOS/Windows/others) as well as popular crypto libraries to adopt a similar primitive in their future cryptographic APIs.
Background
In order to provide convenient APIs to developers, Crypto libraries and toolkits (such as Android Keystore or Apple Cryptokit) rely on secure support from both hardware and many layers of OS and software stack in the middle. While hardware typically only provides very basic but critical functionality like un-extractable key material, different layers of the software stack expose different functionalities and ensure security and proper use of the underlying layers. Here is a quick look at how this software stack looks like in a modern device.
Trusted Execution Environment (TEE)
A TEE is a restricted, isolated environment within the mobile device. It includes its own OS but with a much smaller footprint to minimize attack surface area. The TEE OS runs parallel to but isolated from the Android OS on the same hardware. Android provides what is typically called a Rich Execution Environment (REE) as it provides rich and flexible capabilities — but can not be trusted to the same extent as the TEE. On the flip side, TEE is extremely constrained in its OS capabilities, development environment and available raw cpu/storage resources.
While 3rd party developers can use the Android REE to build rich apps of the kind we use daily, TEE apps are minimal and constrained but much more secure. These are called “Trusted Apps” and are typically not open to 3rd party developers. Examples include apps for fingerprint management, DRM management for content and Android KeyMaster to provide access to hardware backed keys and key operations. Trusted Apps provide more convenient abstractions over the raw capabilities of the hardware and also act as a bridge to the non-secure world.
To provide a secure environment, TEE utilizes and is complementary to the secure hardware present in the device – this includes specialized memory, Secure Elements (SE), specialized storage as well as specialized virtualization support within CPUs and SOCs (Systems-on-Chip) used in the device.
For more details, also see
- TEE Architecture (PDF) of a TEE standard called GlobalPlatform (PDF whitepaper)
- Qualcomm’s TEE (PDF) description
- Google publishes an open source TEE implementation called Trusty
- See ARM TrustZone details here.
Cryptographic Operations in Android
Android provides various cryptographic operations to developers for use in their apps through a module called Keystore. (IOS has an equivalent Cryptokit). The Keystore interfaces with the Android Keymaster (aka KeyMint) Trusted Application that runs in the TEE and itself provides abstractions over the hardware backed key material and other cryptographic primitives in the TEE OS and hardware.
Some of the keystore APIs available to mobile apps are to create keys, import keys, and to perform crypto operations such as signing, encryption and decryption using these generated keys. These relieve the app developer from having to implement the basic (but complex to implement) crypto operations themselves.
New Cryptographic primitive in Android 12 (aka Android S, API 31)
Google announced the preview of its latest version of Android in February 2021 with full release expected in September 2021. There are various improvements to Keystore and Keymint in Android S. But there is one new, simple but powerful cryptographic primitive added for the first time. It adds the ability to generate and use special keys called LimitedUseKeys (LUKs).
What is a LimitedUseKey (LUK)?
An LUK allows the client app to set a maximum usage count on the generated key. For example, an app can generate a key and require that it be used at most 4 times. The Keystore/Keymaster system will keep track of how many times a key has been used, and will delete the key once it has been used 4 times so that the key can not be used further.
Keys that can be used at most once are important special cases of LUKs — let’s call them SingleUseKeys (SUKs).
In order to securely implement LUKs/SUKs and guarantee no more than the intended max usage count, it is better if the counter is kept as downstream and as close to the hardware as possible in the device. However, this requires storing a counter per key and is a burden on the constrained TEE and hardware resources. Hence, it may not be available immediately in all TEEs. For SUKs though, one needs only a single bit per key and it is more likely that SUKs are natively hardware supported than general LUKs. Indeed the Android S HIDL reference implementation for KeyMaster also includes the SUK implementation. Hardware TEE vendors who typically confirm to this reference are likely to incorporate hardware support at least for SUKs. As stated in the Android documentation above, Android Keystore works correctly as per the API contract regardless of hardware capabilities. It maintains the counters itself if the underlying hardware doesn’t have support for them, but this is obviously not as secure as having the native support in the TEE/SE. It remains to be seen how soon we see TEE vendors adopt native support of this new primitive.
Digital Cash – The Motivating application of LUK/SUK
At Google Pay, we added LUK/SUK support in Android because these primitives elegantly solve the complex problem of offline payments while only requiring minimal changes to the constrained TEEs. To understand this, we have to dive a bit deeper into digital payments and digital Cash.
All digital payments today actively need Internet connectivity
All electronic payment mechanisms today are built on the fundamental assumption of Internet connectivity. Basically, every payment transaction — whether swiping or tapping a credit card or debit card or using payment rails like UPI — needs to ring up one or more remote servers for every transaction. In fact, a typical transaction likely goes through tens of such servers before being completed. We have all experienced the frustration of waiting for a card swipe to “go through” on occasion.
Why do they need to go through servers? Servers are trusted entities (eg bank servers or Visa servers) that are making a number of checks for safety and security and are doing book-keeping by maintaining a ledger of transactions recording who paid whom. This is true for all digital payment networks, including in blockchains where the ledger is decentralized and there is no single trusted authority, but one’s transaction needs to be verified and recorded by the network.
Requiring Internet connectivity for payments is a fundamental block to achieving universal access and financial inclusion
While Internet connectivity is steadily becoming more ubiquitous all over the world, it remains a problem in not just many regions of the world but also in many places where users go day to day — think of the congested networks we have all encountered during a conference, or a stadium, or intermittent connectivity we encounter in the basement, in the mall, or on the road during our road trips, etc.
Contrast this with physical Cash – the existent technology that digital money seeks to supplant. Cash is highly robust. It works always and everywhere. This is because it is truly decentralized and peer-to-peer — no server needs to be called up before the recipient accepts cash. Imagine if you paid some cash to the lemonade stand who first has to call up some servers to verify a few things before they can take your cash.
Electronic payments can not realize the vision of Digital Cash and only be partial substitutes to Cash without this level of robustness.
The Fundamental Problem of Double spend in all Digital Tokens
Perhaps the biggest idea in Satoshi’s original Bitcoin whitepaper was Proof-of-work consensus to solve the double spend problem when going from a centralized ledger to a decentralized ledger with no trusted authority.
It is the same double spend problem that we need to tackle when we do not have access to the Internet. Without connectivity, there is no ledger available for the recipient to check the safety of a sender’s transaction.
To understand the problem, consider the following scenario in the real world where you and friends go to a movie theater to watch your favorite movie or to a school or county fair. When you show them your ticket at the entrance, you get some colored paper or plastic coupons to buy food or beverages.
While you may have not thought too much about this system, it is popular because it has several advantages:
- Ease of use – kids, elderly, anyone can use them, and the vendors can quickly accept them
- Eliminates the need for food / beverage sellers to handle payments, making everything faster
- The responsibility of the safety and custody of these tokens is passed to you
It is important to realize that there is a crucial built in assumption for this system of tokens to work – that they can not be easily copied. Because if they could be easily copied or forged, all the vendors would run out of food very quickly! Until we have cheap, portable 3D copiers available that can make exact replicas — simple physical attributes like stamps, engravings, marks, colors etc. make it almost impossible for these tokens to be copied. So the system works in the physical world so well that we hardly think about it.
But consider the digital world. It is very different from the physical world in one foundational aspect:
The fundamental difference in digital world is that digital data can be easily copied, and at will. If you see any data even once, you can copy it trivially and use it infinitely.
There is absolutely nothing that can be done to stop it. This has profound implications on how we devise any exchange networks such as Payments or the school fair token system. If the school fair were to replace the physical tickets/tokens by digital equivalents by giving you digital tokens (say colored images of coins), you could trivially copy those images, so the organisers would need to. do something different.
The only thing that will work is for them to give unique coupons – say with numbers – and keep track of them. When you present a digital token to the food vendor, they will need to check whether that number has been used by someone else before. To do that, they will need to maintain a record (aka a ledger) of all previous coupon numbers they have seen. This is how digital payment systems work, and this is a fundamental reason why ledgers need to be maintained and looked up. If it is really the organizers who are issuing the tokens, it is likely that they maintain this ledger in their database and for every transaction, each food vendor now has to first check from that database before giving you your burger and fries. Everything just became orders of magnitude slower and painful.
And there are severe privacy implications too — now that the organizers track who they issued what unique numbers to and which exact places these were spent on, they can also send this report next day to someone else, like parents for kids at a school or a spying government. You would think that you can get around this by exchanging your coupon numbers with your friend’s (technically called “mixing”). But if the organizers are serious they could ensure that the database stores not just which coupon numbers have been used up, but that whom were they issued to, and require that you have to present your ID along with the coupon numbers given to you. Their database could only allow you to get your items if those match as expected by the ledger.
The same problems are present in all Digital Cash / CBDC proposals. They are a far cry from the properties of Cash they seek to provide alternatives to.
How LUKs/SUKs solve the double spend problem without requiring connectivity to any ledger
Let’s continue with the analogy of implementing a digital coupon system at a movie theater or a school fair. The digital system will work like this:
A. When the user’s phone is online (ie, before going to the movie theater):
The digital coupon app on the phone uses the new Android SUK crypto primitive to generate a SUK keypair per coupon. The app sends the SUK public keys to the organizer and the private key is in hardware, unknown to even the app. The organizer makes a few checks like the key’s and device’s attestation and then signs (attests) the SUK pubkey to authenticate the SUK. This would typically be done with its own private key (say the organizer key) and the corresponding organizer public key would be pre-configured in each phone’s coupon app. After this step, the user now has a bunch of signed SUKs. If for example, the organizer meant to give multiple food coupons and drinks coupons – it could sign the tuple <SUK, coupon-type> instead of just the SUK.
B. When the user is inside the theater or school fair:
The user goes to the food/drinks vendor, taps their phone to communicate with the vendor’s POS or phone app where the the following happens (some details are abstracted for simplicity):
- User’s app sends a “transaction message” consisting of <coupon-type, timestamp, other fields> signed with SUK along with the organizer-signed-tuple <SUK, coupon-type> to the vendor to show that it is indeed consuming an organizer attested SUK
- Vendor’s app checks whether the tuple is signed by the organizer. It can do so using the organizer’s pubkey with it
- Vendor’s app checks that the SUK pubkey signed by the organizer correctly decrypts the message signed by the user. If it does, vendor dispenses the requested item.
The reason why this works is that because the SUK was guaranteed by the user’s device to have been only used for signing only once, (1) can not be done again using the same SUK. That SUK has been well and truly spent, just like the physical coupon. This is true even if the sender has root access to their phone and is guaranteed by the TEE implementing SUK.
The case of multiple coupons per item
Let’s say the organizer wishes to give 20 coupons. Instead of signing 20 SUKs, the organizer could also convert this to an account-based system in which it signs a single LUK with a maxUsageCount of 20. If some item needs 5 coupons, instead of repeating steps (1)-(3) 5 times, the user app sends a single transaction message which includes the number of coupons to be sent in that transaction and asks the keystore to sign that message 5 times using the LUK (or signs repeatedly with 5 SUKs)
From coupons to offline decentralized digital payments
Decentralized digital payments work offline pretty much in the same way as the digital coupons mentioned above. Here are the steps involved at a high level:
A. When the user is online:
The digital process mirrors the one in the physical world — as one goes to the ATM of their account issuer (e.g., their bank) in physical world, authenticates oneself and withdraws some cash bills from the ATM to one’s physical wallet, the user wallet/payments app visits their issuer bank site and downloads an amount say “B” as either digital tokens or as a digital balance along with organizer-attested LUK with maxUsageCount of B or B SUKs.
B. When the user is offline and wants to transact:
Let’s say a sending user S wants to send an amount M to the recipient R. S can sign a transaction that consumes M number of LUK/SUK signing operations
Generalizing – LUKs/SUKs help enforce a immutable, untamperable, ordered, verifiable log for decentralized applications
The above mechanism describes what could be called token-based mechanisms. We could also cast these as account-based mechanisms, in which a single starting balance ‘B’ is maintained securely in the wallet. The issuer would attest ‘B’ as well as a N number of SUKs (or a single LUK with maxUsageCount of N). Here the SUKs won’t represent tokens to be consumed, but transactions to be recorded in the ledger. Hence what the issuer would attest are not just SUK, but the tuple <SUK_i, i> indicating that the device must use SUK_i for the ith entry in its transaction log. This simple modification allows anything to be recorded in an immutable, untamperable sequence. For example, let’s say a balance of 1000 was consumed in three transactions of amounts 200, 750, 50 in that sequence to four different receivers.
The transaction log would look like this:
- <Send 200 to R1, new Balance = 800, issuer-attested <SUK_1, 1>> signed by SUK_1
- <Send 750 to R2, new Balance = 50, issuer-attested <SUK_2,2>> signed by SUK_2
- <Send 50 to R3, new Balance = 0, issuer-attested <SUK_3,3>> signed by SUK_3
When transacting with R2, the transaction entries (1) and (2) would be sent to R2, who would be able to verify everything itself without contacting any server. The sender can not tamper anything in this log because let’s see what happens if it tries to do:
(a) Change the amount of the first transaction to 10 instead of 200 – well, it must produce a transaction record that includes the amount 10 instead of 200 but. it has already consumed SUK_1. It can not use some other SUK because the issuer attested <SUK_1, 1> meaning that SUK_1 is the only key to be used for the first transaction
(b) Create a fake transaction of amount 10 and call that as the first transaction, and delete the real first transaction. Again that doesn’t work because there is only 1 SUK – SUK_1 – to be used as the first transaction. If it is used in the real transaction to R1, it can not be used again. Likewise, if it was used as a fake transaction first, it can not be used in the real transaction and the sender will be stuck.
There are many more threat models present here that we do not explain here. Some of those are mentioned here.
Achieving the vision of digital cash and a digital currency / CBDC
Achieving offline transactions is a crucial step for robustness of a digital payments/currency system. But to be identical to Digital Cash, two more properties also need to be provided in the system – anonymity and transitivity (receiver should also be able to forward offline the money it received from a sender). Here, we need some more mechanisms that were developed after this work and are described in another blog post. That blog post introduces a complete digital cash protocol, called CryptoCash, that provides identical properties to physical cash in the digital world.
Practical Deployments
Recall that Android has introduced the LU/SUK primitives only this year (2021). While Android 12 rollout might take only a few months, there will always be phones on previous Android versions. Because Android Open source reference implementation also includes the hardware implementation of SUK which most TEE vendors adopt immediately, it remains to be seen when all TEE vendors will support hardware backing of SUK/LUKs. Until then, these primitives could be simply supported by the app themselves but that will come with vastly reduced security guarantees. Regardless of hardware, TEE and OS support, it is expected that policy rules – like a maximum allowed time that the device an. be offline or max number of offline transactions allowed – would be needed while the technology is being rolled out.
Given that the primitive is fairly simple to implement but extremely powerful in its applications, I request and urge the other OS vendors – IOS/ MacOS/Windows – to consider implementing this primitive in their cryptographic libraries and toolkits (Apple Cryptokit, Swift Crypto etc.) along with encouraging TEE and hardware vendors to provide secure native support for Single Use and Limited Use keys.
Questions or Comments?
Please send any questions or comments to me on Twitter using private DM or replies to my tweet announcing this blog post.
A Zero Knowledge Blog 