Protecting Citizen-Government Interactions with End-to-End Encryption
Yuanruo Liang, Senior Software Engineer
Introduction
FormSG is a form manager widely used in the Singapore public service to launch online applications and securely collect sensitive data from citizens and businesses. Since its launch in Dec 2017, FormSG has digitalised over 60,000 government forms, transforming the workflows of over 70,000 public officers, and processed more than 100 million submissions in the process.
In early iterations of the product, FormSG did not store form response data to limit the potential damage in case of a database breach. Instead, form responses were automatically forwarded as emails to public officers’ inboxes. As FormSG rapidly grew in popularity, this mode of data collection quickly became impractical as the volume of responses from popular online forms overwhelmed the email inboxes of public officers.
It soon became clear that there was a need for the system to store responses for retrieval, but without allowing unauthorised personnel from accessing sensitive citizen data.
Our approach was to employ end-to-end encryption (E2EE) — a system of communication where only the form admins could read responses, and no other. In principle, this would prevent potential eavesdroppers from gaining access to the data — including us, the system admins. We decided to call this mode of form response Storage Mode, a secure-by-default mode of data storage.
How FormSG’s end-to-end encryption works
When a form is created, the form admin downloads a secret key that is generated in-browser. This secret key is the private half of a cryptographic key pair; the public key is appended to the created form and saved into the Form database. When a user visits a Storage Mode form, this public key is retrieved and then used to encrypt the response data.
The form admin has to ensure that the secret key generated by the client is kept safe.
Each form response would be encrypted by its corresponding public key (not shown).
To access any data, the form admin has to upload the secret key for client-side decryption.
This would then grant the user access to the encrypted responses.
Implementing end-to-end encryption
Cryptography considerations
Our initial proof-of-concept was a combination of RSA-2048 with AES-128 used together in a key encapsulation scheme; a submitter would generate a symmetric AES key to encrypt the response data, and then encrypt this key with the form admin’s RSA public key.
However, this turned out to be extremely unperformant during the decryption stage — decrypting 100,000 responses for a form of 10 questions required more than 8 hours of compute on a single JavaScript thread. This was unacceptable performance, as some form admins frequently needed to download a high volume of responses (e.g. for large events such as National Day Parade applications or more recently, registrations for the COVID-19 vaccine). Thus, it was necessary to be able to decrypt hundreds of thousands of responses at a time, if not millions.
It turns out that RSA is slow because its security depends on the difficulty of integer factorisation which takes sub-exponential time for the best-known algorithms to break, and therefore requires much longer decryption keys (>2048 bits) to remain secure but results in the CPU having to dedicate a lot of compute cycles to decrypt the underlying ciphertext.
The team researched other alternatives and decided to switch to elliptic-curve cryptography (ECC) instead, which offered far better performance. Unlike RSA, the security of ECCs is based on the difficulty of the discrete logarithm problem, for which the best-known algorithms still run in exponential time.
The team chose an ECC implementation provided by the tweetnacl-js library, based on published performance benchmarks and separate cryptographic audit by Cure53. Making the switch from RSA-2048 to ECC-256 resulted in a 20x decryption speed gain whilst simultaneously gaining in equivalent cryptographic strength from RSA-2048 to RSA-3072.
The US National Institute of Standards and Technology has conveniently provided a comparison table of equivalent key sizes to illustrate this:
Equivalent key sizes in bits
Performance considerations
Implementing a performant end-to-end encryption scheme was not straightforward. The team made multiple design choices aside from bug fixes that enabled the feature to run efficiently and reliably in production.
One of the key features to optimise was the CSV download feature, which required the bulk fetch and decryption of large numbers of responses.
Memory optimisation
To avoid the risk of servers running out of memory, the team decided to reduce the expected memory bloat from concurrent calls to the GET API by implementing the database and HTTP network calls with a streaming implementation:
- First, obtain a mongoose QueryCursor from the relevant database query
- Pipe the cursor stream to a transform function, which modifies each record by appending additional metadata where necessary (e.g. S3 pre-signed URLs for attachments) and re-formatting into newline-delimited JSON
- Pipe the output stream to an Express response object
This enabled the server to act as a conduit between the database and the browser whilst avoiding the build-up of the entire dataset in memory (interested parties may refer to our code here).
Better performance through threading
JavaScript developers know that it is generally good practice to avoid blocking the main thread, as it leads to issues such as freezing UI rendering. The team used the Web Worker API to offload the heavy decryption workload to a single Web Worker running on a separate thread to avoid such issues. This resulted in a 3.2x speed improvement whilst solving UI issues.
If adding a single thread worked, what about leveraging multiple threads? Building atop our gains, the team leveraged parallel cores by spawning a thread pool of Web Workers and distributing the work round-robin. The optimal number of workers is determined by the window.navigator.hardwareConcurrency, a browser variable which informs the application of the total number of logical processors available to run threads on the user’s computer. This optimisation provided another 3.4x in speed gains and led to the architecture below:
Performance profiling with Chrome DevTools
Although the performance had improved dramatically, we wondered if it was possible to obtain further gains by employing performance profiling techniques. This led to the following profile:
The top green bar depicts work performed by the main thread, whereas the light blue bars depict work performed by the web workers. It looks as if the web workers were being assigned work at random times, and it was not clear whether much parallelism was even being achieved.
We suspected a bug in our scheduling code. On closer examination, we realised that our round-robin message passing implementation which distributed the decryption work was buggy; instead of distributing work evenly when each piece of ciphertext was first received, it only did so after each decryption task was completed.
After writing a fix and re-profiling the code, the profiler immediately demarcated clear periods of work which alternated between the execution of the main thread and the worker threads in parallel:
However, this led to the next question — why does the main thread idle so much between worker decryption cycles? We used the profiler and zoomed into the main thread profile:
It turns out that for every 15ms spent decrypting, a whopping 266ms (!) was spent on parsing in the main thread. The reason lay in the byline library, which the browser was using to parse UTF-8 character streams from the HTTP buffer.
We patched our own copy of the byline library to speed up the parsing process to drop UTF-8 support and only parse for ASCII characters.
Amazingly, this not only reduced the time expended on stream parsing from 266ms to 35ms, but also reduced the maximum memory use from 5GB to 200MB.
All in all, the team was able to obtain speedups of up to 600x compared to the original RSA implementation, out of which 10x was due to optimising application code:
Note: FormSG has since switched to using fetch-readablestream instead of byline to leverage on native browser performance as much as possible.
Avoid speculation and profile performance instead
Many ideas and discussions were proposed during feature development, most of which were speculative and not supported by evidence. Some of them are reproduced below:
In the end, most of the ideas floated didn’t work; we realised that the key lesson was to avoid speculation, and depend on performance profiling instead.
Impact
The team delivered Storage Mode and end-to-end encryption in late 2019. When the Covid crisis struck, these features greatly enabled public officers to quickly bring new workflows and processes online. As of April 2021, FormSG has processed over 100 million form responses for more than 100 public agencies, such as vaccine registration or the gov.sg WhatsApp subscription.
Conclusion
FormSG built Storage Mode end-to-end encryption to allow public officers to store data, whilst preserving the security and privacy of citizens. After reviewing the available cryptography methods, we decided to employ an elliptic curve cryptographic scheme. By carefully optimising performance at each step, the FormSG team was able to deliver a fast, efficient and secure method of digitalising the collection of public form responses to more than 70,000 public officers. This enabled the public service to respond with agility to a fast-developing Covid pandemic and led to the platform’s growth to more than 100 million form responses.
Open Government Products is a team of engineers, designers, product managers, and data scientists who build software systems that improve the public good. If you’re interested in joining us, click here to apply!
Acknowledgments
Leonard Loo, Senior Product Manager
Sonjia Yan, Product Manager
Yuanruo Liang, Senior Software Engineer
Jean Tan, Software Engineer
Arshad Ali, Software Engineer
Lau Kar Rui, Software Engineer
Antariksh Mahajan, Software Engineer
Teo Shu Li, Software Engineer
Fiza Husin, Product Designer
Sarah Salim, Product Designer
Pearly Ong, Product Designer
Jackson Yap, Product Specialist
Special thanks to
Gregor Hohpe, Distinguished Engineer, Smart Nation Fellow
Frank Chen, Senior Software Engineer, Google
