Advanced Cryptographic Tickets Deep Dive
Learn how HydraVeil's Anonymous cryptography works.
Can Just Use It
You don’t need to actually read this to use it. You can just hit a button if you like and it does the cryptography automatically. (or you can even opt out and pay for each profile separately). But for those who are curious here’s the deep dive.
Advanced
This is the more advanced version, for the easy basics with memes please see the intro article.
Premise
HydraVeil allows the user to isolate parts of their life with different profiles. But if this was all under a single billing ID that would centralize information about the user to the billing coordinator. However, expecting the end-user to manage multiple subscriptions across devices can be an inconvenient burden. This is why HydraVeil offers cryptographic billing, so the end-user can make a single payment for a longer time period, yet still have each profile and device completely isolated and anonymous from the rest.
Technical Implementation
Specifically HydraVeil’s billing system uses BLS12-381 keys, with the pairing equation, implemented in Python using the py_ecc library. We use Miller’s Pairing equation for signature verification. And Scalar Multiplication to blind the commitments.
Brief Overview of Flow
Send Blinded
Client generates 6 commitments, blinds them, and then sends the blinded ones to the server.
Sign Blind
After paying, the Server signs them all separately (but returns the data aggregated as a single JSON)
Unblind
The client unblinds the server’s signature. And puts this unblind signature in a JSON together with the original unblinded commitment as a “ticket”. At any time, the client can use the ticket, to get VPN access for a single profile.
Verification:
To verify the ticket, the billing server uses Miller's algorithm (see below). The exact same formula also exists in the HydraVeil client to verify the server’s blind signature is legitimate.
Scope
Let’s discuss what the project aims to achieve, and what we are currently unable to hide.
Does Hide:
Our primary goal is to isolate the profiles/tickets from one another, as well as seperating the payment from the use.
HydraVeil is able to defeat subliminal embedded messages, key switching, side-channel attacks involving time, use sufficient randomization, and present reasonable anonymity to the billing server under nearly any conditions.
does NOT hide:
But once a ticket is used, going forward, repeat uses of the same ticket are known as the same person. However, reusing the same Wireguard key for a given profile, would do this anyway, so hiding repeat use is currently out of scope for our project.
When Tickets Are Used
Additionally, if multiple tickets are used at the same time, it could potentially connect them in the eyes of the billing server. This is NOT something we can realistically prevent using cryptography. The HydraVeil client does offer billing through Tor to give new IP addresses to each ticket use. But to provide true anonymity, the user would have to randomly use tickets over time, and not all at once.
Verification
To verify the final signature on the unblinded commitment, the billing server uses Miller’s elliptic pairing algorithm with BLS12-381. Let’s understand the history behind this.
What’s a Pairing?
Pairings are a special family of elliptic curves with a specific slope to allow two groups to be compared. In this case, the message and the public key are in different groups. This has amazing properties for enabling privacy and signing many messages at once.
Pairings Invented by Miller
This formula was originally created in 1986 by Victor Miller [1], the father of pairing elliptic cryptography. Miller’s big revelation was to make pairings validation checks computational feasible, by delaying finishing it until later stages. Prior to Miller’s revelations, pairings could not be used in the real world practically. We’ll see Miller’s formula below, but first we should first learn about the form that we’re using Miller’s in, which is with shorter signatures called “BLS”.
Shorter Signatures (“BLS”) - (2001)
15 years after Miller’s initial papers were published, a trio of cryptographers Boneh–Lynn–Shacham “BLS”, dramatically improved Miller’s original algorithm. They managed to make the data shorter, by allowing hashing of messages, and also the signatures and commitments to be points on an elliptic curve. [2]. This set the academic framework for many projects to use pairings over the next 20 years, leading to the modern use in cryptocurrencies like Zcash, Ethereum, Polkadot, and Filecoin.
Zcash Invents BLS12-381 (2017)
While the foundations for pairing we created many years prior, Zcash’s founder introduced BLS12-381 [6], which was specifically tailored for faster performance. While Zcash eventually switched off BLS12-381 in a future upgrade, the optimized curve got use in other cryptocurrencies and industries such as medical privacy.
Ethereum Adopts It (2022)
By 2022, BLS12-381 had gotten mainstream attention. Ethereum’s upgrade to Eth 2.0, saw the start of it using the curve for validator nodes. Ethereum does not use BLS12-381 for privacy, but for the scaling benefits pairings offer. Because pairing elliptic curves can sign multiple notes at once, which is very important for a validator node.
HydraVeil
HydraVeil uses Miller’s formula, through the Ethereum foundation’s py_ecc library, with their Python implementation of the pairing function. All the underlying math is done by this Ethereum library, and Simplified Privacy is only handling the inputs in the proper format. This is good, because “rolling your own crypto” is hard. And we don’t gain anything by reinventing the wheel here.
Not Blockchain:
Note: HydraVeil does NOT literally use Ethereum’s blockchain or cryptocurrency. We use their library to do math.
Why Ethereum’s Library?
While Zcash originally developed the BLS12-381 curve, the actual Zcash protocol switched off it. So we didn’t want to use a library that had a high chance of not being maintained in the future. On the other hand, Ethereum is a large and well-funded project, with a high-value current use-case for validator nodes, and thus making it very likely to be maintained in the future.
We are not ruling Arkworks out for a future potential Rust rewrite, but Arkworks relies upon free community support. And Arkworks’ Discord server has a low amount of contributors answering questions, which often aren’t in their documentation.
Why Python?
Ethereum’s Python and Rust versions use the same underlying math formulas. We use Ethereum’s Python version, and not their Rust version, because we (Simplified Privacy) are the adversary. So Python’s interpreted nature makes it impossible to hide the source code. Anyone can rip open our AppImage and inspect that the code is what we claim it is because it’s pure Python.
While Rust can in theory compile to a hash, in practice, the underlying dependencies change, so it is outside the control of the developer to promise verifiable rebuilds. Rust is often used by other developers to keep you safe from external actors. While HydraVeil’s encryption is to prevent us (the developers) from collecting data on which profiles are you. Under that threat model, Python’s forced open source nature, provides greater transparency to our project.
While it’s true that Python can’t keep “constant time”, this is not a problem for HydraVeil, because it prepares all the tickets at once, and then uses them over time. Given the “offline” nature of the cryptograhic operations, there is no repeat decryption to measure time against.
Python Random:
The fact that Python’s default random library can not generate secure random numbers is not relevant, as we use the os module using the operating system’s underlying random features.
Future Mobile
In the future, we will evaluate how well this performs with a mobile app, to see if we may have to switch to a Rust version. Users can currently cash tickets in via the web app for mobile or routers, but must generate them in HydraVeil’s desktop app to begin with.
Used Correctly?
How do we know that Simplified Privacy is using Miller’s formula correctly? The first answer to that question, is that it doesn’t even matter. This formula is what the attacker does to verify it. All that matters is what inputs the attacker (billing server) can see.
The second reason you know Miller’s was done correctly, is because the signatures verify under the conditions they are supposed to (actually signed), and break under the conditions they are supposed to (not signed or forged inputs). This would be mathematically impossible unless we were using the verification formula correctly.
And the third reason is that the HydraVeil client uses the same code and Miller’s formula as the server does to verify it. HydraVeil uses Miller’s to verify the server’s blind signature is legitimate for for the public key. The billing server verifies it’s unblinded signature when the ticket is finally used.
Verification Formulas
Inputs
Where: commitment, signature, public_key, and G1 are all x and y coordinate points on the elliptic curve.
And:
commitment = unblinded commitment
signature = billing server’s signature (originally signed on the blinded commitment, but has now been unblinded with the same secret)
G1 = constant point for the py_ecc library with BLS12-381
public_key = the billing server’s BLS12-381 key
Then,
The Pairing Equation:
e(signature, G1) == e(commitment, public_key)
How do we know that this formula can’t deanonymize users? Because substituting any of the inputs in the formula breaks it. And this formula is ONLY MEANS to verify signatures or results.
This BREAKS it:
BREAKS:
e(BLIND_signature, G1) == e(NOT_blind_commitment, public_key)
You CAN’T swap the blind signature in there, to go with the unblind commitment message, because then the verification fails. Or vica-versa. That signature doesn’t match with that commitment.
You can’t swap G1, it’s a constant.
You can’t swap the public key, or the whole thing is meaningless.
Given that Miller’s formula is the only validation tool, the adversary has no means to even test deanonyizing users. Swap anything and it breaks.
We just described the final validation, but how does blinding actually work?
Blinding / Unblinding
HydraVeil uses age old techniques that come from the godfather of anonymity.
David Chaum (1982)
In 1982, David Chaum pioneered cryptographically anonymous unlinkable payments. His revolutionary paper “Blind Signatures for Untraceable Payments” [3], laid the foundation for using scalar multiplication to give anonymity to a signed message and/or signature. His techniques have proven to stand the test of time against the most rigorous academic studies.
Chaum-style on Elliptics
While Chaum originally used RSA, extremely similar techniques with scalar multiplication have also been done with elliptic curves. One example of this is a 2010 peer-reviewed paper from Constantin Popescu that (literally and openly) cites Chaum and copies his original mathematical style to work with elliptic curves. [4]
HydraVeil’s use.
The HydraVeil Client blinds the commitment using the same scalar point elliptic curve multiplication. It’s through the “magic of pairing cryptography” that there is no link between the unblinded commitment and blinded commitment, or unblinded signature and blinded signature.
Raw Math:
For BLS12-381 specifically, scalar multiplication happens in the scalar field (integers modulo the curve order),
blind_C = blinding_factor ⋅ unblinded_c
Python with py_ecc:
unblind_commitment = multiply(G2, commitment_input)
Unblinding
The client is able to unblind the server’s signature, using the same blinding_factor factor that initially blinded the commitment.
Raw Math:
S_unblind = blinding_factor^(-1) · S_blind
How do we know this is secure? Because the only relationship between the blind and unblind data is if you know the “blinding factor”. And to solve for that number requires breaking elliptic curve cryptography. (it’s computational hard)
Python with py_ecc:
b_inv = pow(blinding_factor, -1, curve_order)
unblinded_signature = multiply(blinded_signature, b_inv)
Subliminal Embedded Messages
The authority can NOT maliciously hide secret messages in the signature, because this BLS12-381 scheme does not involve the authority picking any random numbers. The signature is purely deterministic. Each input produces the same output, and the output signature can be verified. Therefore, given these constraints, subliminal side-channel attacks are not possible.
Switching Keys
The HydraVeil client verifies every single blind signature against the public key, and the server uses the same public key indiscriminately for all users in the billing group. This presents serious challenges to a malicious billing server attempting to swap public keys for individual users, because at any time users can fetch a new key to verify against though Tor. Under these conditions, the server has to hand out the public keys indiscriminately.
Support from Peer Reviewed Papers
There are multiple peer-reviewed academic papers using either extremely similar or exactly the same formulas as HydraVeil. For example, Alexandra Boldyreva in 2003 published a paper on blind signature schemes, using simple Chaum-style scalar multiplication just like HydraVeil. And with a verification formula using the same inputs as HydraVeil. [10]
Comparison:
While Alexandra Boldyreva’s paper uses a different verification formula, that doesn’t matter if it’s the same inputs, because it’s irrelevant what the attacker says he’s going to do. All that matters is what information he has access to, and what the vulnerabilities are of that information.
Peer-reviewed Alexandra Boldyreva in 2003
Blinding: Chaum-style scalar multiplication
Attacker gets: g, pk, H(M), σ
HydraVeil
Blinding: Chaum-style scalar multiplication
Attacker gets: g, pk, H(M), σ
But what about the Critics?
I’ve cited proponents of these formulas and systems. But what about it’s critics? What does the peer reviewed literature say? There actually a huge amount of papers discussing trying to break “Chaum-style” scalar multipication.
“Double attack” Won’t Work
Fouque & Valette published a paper in DCSSI Crypto Lab [8] attacking Chaum-style blinding, with a new technique to doxx users doing repeated cryptographic operations. But their method, does NOT apply to HydraVeil, because it relies upon visibly measuring the time that repeated use of the private key takes. With HydraVeil, after recieving the blind signatures, your client does all the cryptographic operations (unblind all the signatures and prepare the tickets) all at once. This means there is no ability to these kinds of side-channel attacks.
16 Years Later, Same Problem
While that Fouque & Valette paper was in 2003, the same problem existed in 2019, when Thomas Roche, Laurent Imbert, and Victor Lomné published “Side-channel Attacks on Blinded Scalar Multiplications Revisited” [9]. Although 16 years passed, their techniques did not improve much. It still requires multiple cryptographic operations, which completely rules out HydraVeil’s scheme from doxxing users.
Final Cryptography Overview
Curve: BLS12-381
Library: py_ecc
Verification: Miller’s Pairing with BLS
Blinding: Chaum-style Scalar Multipication
Yellow Paper
If you enjoyed this article, you’d probably like the full yellow paper.
Sources:
[1]
Victor S. Miller
“Short Programs for functions on Curves”
Exploratory Computer Science, IBM, Thomas J. Watson Research Center, Yorktown Heights, NY 10598, May 6, 1986
https://crypto.stanford.edu/miller/
[2]
Boneh, D., Lynn, B., Shacham, H. (2001).
Short Signatures from the Weil Pairing. In: Boyd, C. (eds) Advances in Cryptology
ASIACRYPT 2001. Lecture Notes in Computer Science, vol 2248. Springer, Berlin, Heidelberg.
https://doi.org/10.1007/3-540-45682-1_30
https://link.springer.com/content/pdf/10.1007/3-540-45682-1_30.pdf
[3]
Chaum, D. (1983).
Blind Signatures for Untraceable Payments. In: Chaum, D., Rivest, R.L., Sherman, A.T. (eds) Advances in Cryptology. Springer, Boston, MA.
https://doi.org/10.1007/978-1-4757-0602-4_18
[4]
Constantin Popescu (2010).
“Blind Signature Schemes Based on the Elliptic Curve Discrete Logarithm Problem”
Studies in Informatics and Control, Vol. 19, No. 4, pp. 397–402
DOI: https://doi.org/10.24846/v19i4y201007
[5]
Alexandra Boldyreva (2003)
“Threshold Signatures, Multisignatures and Blind Signatures Based on the Gap-Diffie-Hellman-Group Signature Scheme”
Alexandra Boldyreva, PKC 2003.
DOI: https://doi.org/10.1007/3-540-36288-6_3
[6]
Sean Bowe (2017)
BLS12-381: New zk-SNARK Elliptic Curve Construction
Electric Coin. Zcash Blog. March 11, 2017
https://electriccoin.co/blog/new-snark-curve/
[7]
Menezes, A., Sarkar, P., Singh, S. (2017).
Challenges with Assessing the Impact of NFS Advances on the Security of Pairing-Based Cryptography. In: Phan, RW., Yung, M. (eds) Paradigms in Cryptology – Mycrypt 2016. Malicious and Exploratory Cryptology. Mycrypt 2016. Lecture Notes in Computer Science(), vol 10311. Springer, Cham. https://doi.org/10.1007/978-3-319-61273-7_5
[8]
Roche, T., Imbert, L., Lomné, V. (2020).
Side-Channel Attacks on Blinded Scalar Multiplications Revisited.
In: Belaïd, S., Güneysu, T. (eds) Smart Card Research and Advanced Applications. CARDIS 2019. Lecture Notes in Computer Science(), vol 11833. Springer, Cham. https://doi.org/10.1007/978-3-030-42068-0_6
[9]
Fouque, PA., Valette, F. (2003).
The Doubling Attack – Why Upwards Is Better than Downwards.
In: Walter, C.D., Koç, Ç.K., Paar, C. (eds) Cryptographic Hardware and Embedded Systems - CHES 2003. CHES 2003. Lecture Notes in Computer Science, vol 2779. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-45238-6_22
https://link.springer.com/chapter/10.1007/978-3-540-45238-6_22
& Also in:
DCSSI Crypto Lab, Paris, France
https://www.di.ens.fr/~fouque/pub/ches03b.pdf
[10]
Alexandra Boldyreva, 2003
“Threshold Signatures, Multisignatures and Blind Signatures Based on the Gap-Diffie-Hellman-Group Signature Scheme”, PKC.
DOI: https://doi.org/10.1007/3-540-36288-6_3
https://link.springer.com/content/pdf/10.1007/3-540-36288-6_3.pdf