Threat Alert CenterLearn More About Our Detection and Response Services
Today we are excited to release Shufflecake, a tool aimed at helping people whose freedom of expression is threatened by repressive authorities or dangerous criminal organizations, in particular: whistleblowers, investigative journalists, and activists for human rights in oppressive regimes. Shufflecake is FLOSS (Free/Libre, Open Source Software). Source code in C is available and released under the GNU General Public License v3.0 or superior.
Shufflecake is originally based on the EPFL M.Sc. Thesis “Hidden Filesystems Design and Improvement” by our former student Elia Anzuoni (under supervision of Dr. Tommaso Gagliardoni and Prof. Edouard Bugnion) during his internship on the Kudelski Security Research Team.
Shufflecake is a tool for Linux that allows creation of multiple hidden volumes on a storage device in such a way that it is very difficult, even under forensic inspection, to prove the existence of such volumes. Each volume is encrypted with a different secret key, scrambled across the empty space of an underlying existing storage medium, and indistinguishable from random noise when not decrypted. Even if the presence of the Shufflecake software itself cannot be hidden – and hence the presence of secret volumes is suspected – the number of volumes is also hidden. This allows a user to create a hierarchy of plausible deniability, where “most hidden” secret volumes are buried under “less hidden” decoy volumes, whose passwords can be surrendered under pressure. In other words, a user can plausibly “lie” to a coercive adversary about the existence of hidden data, by providing a password that unlocks “decoy” data. Every volume can be managed independently as a virtual block device, i.e. partitioned, formatted with any filesystem of choice, and mounted and dismounted like a normal disc. The whole system is very fast, with only a minor slowdown in I/O throughput compared to a bare LUKS-encrypted disk, and with negligible waste of memory and disc space.
You can consider Shufflecake a “spiritual successor” of tools such as Truecrypt and Veracrypt, but vastly improved. First of all, it works natively on Linux, it supports any filesystem of choice, and can manage up to 15 nested volumes per device, so to make deniability of the existence of these partitions really plausible.
Shufflecake is made of two components: dm-sflc, which is a kernel module implementing the Shufflecake scheme as a device-mapper target for the Linux kernel, and shufflecake-userland, which is a command-line tool allowing the user to create and manage hidden volumes. The kernel module must be loaded before using the userland tool. For now the support is limited to Debian/Ubuntu and similar derivatives, testing has been done with the Linux kernel 5.13.
In a nutshell, Shufflecake allocates space for each volume as encrypted slices at random positions of the underlying device. Slices are allocated dynamically, as soon as the kernel module decides that more space than the currently used quota is required, and are interleaved to make forensic analysis more difficult. Data about the position of used and unused slices is stored in a volume-specific “position map”, which is indexed within an encrypted header at the beginning of the device. Both position map and header are indistinguishable from random data without the correct decryption key, and every slot in the header (currently up to 15 volumes) has a field containing the decryption key for the previous (i.e., “less hidden”) header and volume, thereby recursively linking all volumes and allowing the user to open all of them with a single password. This also makes overcommitment possible, i.e., if you have a 1 GiB device and you create 3 Shufflecake volumes on it, by default you will see each of these 3 volumes being 1 GiB in size (although you will start receiving I/O errors if you try to write more than 1 GiB total across all 3), which is also crucial for plausible deniability, because an adversary can never tell for sure how many other volumes are there. Notice, in fact, that if some volumes are left unopened they are not considered for the total space allocation.
A user must first init a device, for example, a physical disc, or a partition therein, or a virtual block device such as a file-backed loop device. This will first overwrite the disc with random data and then create an encrypted header section at the beginning of the device. The header contains metadata and allocation tables for 15 Shufflecake volumes. The user is asked to provide N different passwords (where N is between 1 and 15). Then, the first N sections of the header will be encrypted with each of the N passwords, while the others will be left random. The order of the given passwords is important, because it establishes a hierarchy from “less hidden” to “more hidden” volumes. Notice that it is impossible to know how many volumes there are without decrypting.
Then the user can open the volumes inside a given Shufflecake-initialised device. This is done by providing only one of the N given passwords, which unlocks one of the 15 slots in the header, and hence a device area allocated for the corresponding volume. Furthermore, the unlocked slot contains a key that allows to decrypt the previous (i.e. “less hidden”) slot in the hierarchy, thereby allowing to open all the less sensitive volumes recursively. All these volumes appear as virtual block devices under /dev/mapper and can be mounted, formatted, and used to store data.
Finally, a user can close a device and all the supported volumes therein with a single command.
Shufflecake is efficient: I/O slowdown is roughly 2x compared to a “normal” LUKS encrypted volume, which is still barely noticeable for daily desktop use, and wastes less than 1% of the available disc space. Compare this to state-of-the-art plausible deniability solutions based on WORAM techniques, with slowdowns that range from 200x to 5x with 75% of disc space wasted. A decent amount of memory (roughly 60 MiB per open volume) is required to manage the position maps in-RAM for better efficiency. There is certainly room for improvement, we didn’t focus too much on optimization for the first release, performance will surely get better in future versions.
We believe that Shufflecake fills a gap in the availability of robust plausible deniability solutions for Linux. The current release is still a non-production-ready prototype, so we advise against using it for really sensitive operations. However, we believe that future work will sensibly improve both security and performance, hopefully offering a really useful tool to people who live in constant danger of being interrogated with coercive methods to reveal sensitive information.
Authors: Antonio de la Piedra (Kudelski Security Research Team), Marloes Venema (Radboud University Nijmegen), Greg Alpar (Radboud University Nijmegen and Open University of the Netherlands).
Attribute-based encryption (ABE) is an elegant type of public-key cryptography where secret keys are associated to attributes. It can be used for fine-grained access control on sensitive data, and the Cloud is a perfect use case.
In the past, we have shown how Attributed-based encryption schemes can be attacked. This time, we asked ourselves the following question: Given the myriad of published ABE schemes, can we accurately measure their efficiency in order to know which one is the best? And if yes, what is the best way of achieving this, and what do we mean by the best?
In order to answer this question, we have created ABE Squared, a framework for comparing the efficiency of ABE schemes and to optimize them according to the design goal, taking into account different optimization layers.
We are presenting ABE Squared this week at CHES 2022.
An ABE scheme generally consists of 4 algorithms: Setup, Key generation, Encryption and Decryption. In a typical ABE deployment, a party, e.g. Alice, wants to protect her sensitive data according to a particular access policy based on attributes e.g. doctor OR nurse. In order to do that, Alice will request to a Key Generation Authority (KGA) the master public key (MPK) of the system, and she will encrypt her data accordingly.
Only parties having secret keys related to the attributes doctor, nurse can satisfy the access policy established by Alice and decrypt. In our example, Bob receives to secret keys related to the attributes doctor and Johns Hopkins Hospital, which satisfy (in this case, doctor) the access policy established by Alice.
Nowadays, mature ABE schemes mainly rely on pairing-based cryptography and are challenging to implement. Many of these implementations of ABE schemes rely on rapid prototyping frameworks such as CHARM and oftentimes only some parts of the scheme are optimized. This can be problematic, since implementing an ABE scheme requires addressing many variables such as the implementation of access policy, the group arithmetic and the type conversion. All these areas depend on the type ABE application we are designing. To aid the design process of an ABE application, improve the benchmarking capabilities of designers of ABE schemes and to provide heuristics capable of obtaining optimized versions of ABE schemes given design goal, we have created ABE Squared.
ABE Squared takes into account all the layers of optimization. As inputs, it receives the theoretical description of the scheme and produces the description of the scheme that directly yields the most efficient implementation.
In this process, we choose the design goal, which is of utmost importance. For instance, some applications may require an optimized key generation variant, such as the implementation of a KGA. In order to achieve this, every layer needs to be optimized, and we create optimization approaches based on these design goals:
In order to show how important is to have a design goal when implementing an ABE scheme, we have taken the Wat11-I scheme and implemented using the BLS-12-381 pairing-friendly curve.
We have used all of our heuristics to obtain the OD, OE and OK variants of the same scheme:
Another question we can ask is: What scheme is the best for which operation (e.g. key generation, encryption, decryption) and using which pairing-friendly curve? To illustrate how ABE Squared works, we have chosen 3 ABE schemes that share the same practical properties and structure: AC17-LU, Wat11-IV and RW13.
We see that, in general, the BLS-12-381 pairing-friendly curve provides the best performance. Moreover, the AC17-LU is the best scheme for performing encryption and decryption, whereas the RW13 scheme is the best scheme for key generation.
We started this article by asking ourselves what could be the best way of measuring the efficiency of ABE schemes. We have seen that only by first optimizing the schemes to the same design goal we can compare them in a fair manner. If you want to know more about our optimization heuristics and ABE Squared in general, you can read our paper in the IACR ePrint service.
In my last post, I described the ZK-oriented Ciminion AE (Dobraunig et al., 2021) scheme and implemented it using the circom2 DSL for writing zkSNARK circuits.
In this second part I present an overview of the different hashing constructions that have been proposed in the last few years, starting from MiMC (Albrecht et al., 2016) and finishing with Griffin (Grassi et al., 2022). This allows us to visit another DSL for writing SNARKs (Leo) and to explore embedded DSLs. These libraries provide APIs for constraint definition, compilation and proof generation from languages such as Go and Rust. Two examples are gnark and arkworks. Finally, I include a small list of ingredients that can be used to build a checklist when auditing circuits.
In the first part of this series of articles, we dealt with encryption schemes designed for zkSNARKs applications. For instance, they can be used to prove that a certain piece of sensitive data has been encrypted using a particular key (think about cloud storage) or that a ciphertext has been correctly encrypted using a particular encryption scheme.
In general, using hashes in circuits means that a prover can convince a verifier that she knows the preimage of a value x given the hash of x (i.e. H(X)). In particular, this fact can serve to prove the knowledge of a secret, the membership of a sensitive value in a set, to obtain nullifiers and commitments, and more commonly, to implement set membership proofs in Merkle tree accumulators. In all these cases the performance of the hash scheme utilized is of utmost importance and schemes such as SHA-256 don’t provide the same performance in a circuit in comparison to a scheme based on a reduced number of multiplication and addition gates.
Typically, hashing schemes that target ZK circuits rely on the same type of linear and non-linear layers (we should note that in this article we mainly focus and describe schemes which partially or mainly optimize and measure the performance and size of their schemes using Rank-1 quadratic constraints as metric. We left schemes such as Reinforced Concrete (Grassi et al., 2021), focused on PLONK and others based on Elliptic Curve operations for another time). R1CS constraints describe a circuit via polynomials, where circuit multiplication and addition gates act over the prime Field Fp of a pairing-friendly elliptic curve. Since the proof generation complexity is generally related to the number of constraints (mainly multiplication gates, we can say additions are free), the aim of scheme designers is to reduce the number of multiplications.
In these schemes, in the linear layer, we cannot manipulate individual bits as we generally do in common block ciphers and hash functions, and matrix multiplication is used instead, via maximum distance separable (MDS) matrices for diffusion. On the other hand, non-linear layers are generally based on power maps. The smallest integer that guarantees invertibility and non-linearity is chosen. For instance
is utilized in the case of MiMC. The exponent is chosen if both
and
exist and are both permutations where
Most schemes are based on a round function that applies one linear layer and one non-linear layer, introducing a round constant and/or a subkey:
where c is round constant, M is an invertible MDS matrix and S is the non-linear layer, which can be seen as an s-box. The round function is arranged in a Feistel or SPN structure and iterated. For hash constructions based on the permutations described in the next section, a sponge construction is usually instantiated.
Many arithmetization-oriented schemes have been proposed in the last 7 years, targeting
multi-party computation, fully homomorphic encryption, and zero-knowledge proof applications. We provide a concise overview of constructions focused on prime fields and whose performance has been, mainly or partially measured on R1CS arithmetization. We cite block cipher designs and strategies when they have been used as inspiration to create other hash functions.
One of the first ZK-focused ciphers to be proposed was LowMC (Albrecht et al., 2016). It has received, since then, quite a lot of attention from the cryptanalysis community (see for instance here and here). Inspired by LowMC, MiMC proposes a permutation (that can use the Feistel structure), a block cipher, and a hash function. It relies on the non-linear power map xd with x = 3. The MiMC block cipher was the starting point to improvements in encryption with the GMiMC (Grassi et al., 2019 ) construction and the HadesMiMC strategy (Grassi et al., 2019). MiMC is implemented in libraries such as circomlib and gnark.
The Poseidon hash scheme, proposed after MiMC provided two main advantages: variable-length hashes and instances dedicated for Merkle trees. It is implemented in libraries such as arkworks and circomlib. The authors followed the HadesMiMC approach and the SPN structure, together with the power map xd, with d >= 3 (d = 5 for pairing friendly curves BLS-12-381 and BN-254). They created the Poseidon-pi permutation, based on the Hades design. It contains partial rounds (where the non-linear functions modify one part of the state) and rounds where the non-linear layer modifies the full state. The linear layer is an MDS matrix with dimensions based on the number of field elements processed by the round function.
The Rescue construction (Aly et al.,2019) it is based on a SPN network as Poseidon. However, it utilizes two non-linear layers in the same round with power maps xa and x1/a separated by the linear layer, which consists of a multiplication with an MDS matrix and subkey addition. Neptune is a variant of Poseidon whose non-linear layer reduces the number of multiplications. First, the authors rely on a non-linear layer that uses independent functions and second, they propose to use two different round functions: one for internal rounds and the other one for external rounds. The external round is based on the concatenation of independent s-boxes via Lai-Masey. Finally, the Griffin construction (Grassi et al., 2022) employs s-boxes inspired by Neptune and uses the so-called Horst mode of operation. It provides the best performance when used in plain for a state of field elements t >= 20 among the other candidates. And when using for membership roofs in Merkle tree accumulators it has the smallest R1CS number of constraints.
Summary of described zk-hash functions
In the next two sections, we implement the MiMC and Griffin permutations which allows us to describe how other DSLs for writing circuits work. Note that we only implement the permutations for demonstration purposes and that the respective sponge construction should be instantiated for real use. Also, note that to the best of our knowledge, at the time of writing this post, both Neptune and Griffin have been only published on the IACR ePrint website.
The Leo language is utilized to create applications in the privacy-friendly blockchain Aleo. The proof related to a circuit or application written in Leo is sent as an on-chain transaction so third parties can verify the truth about a certain statement we want to prove. This structure is based on ZEXE. Leo relies on the BLS-12-337 pairing friendly curve and on the Marlin (Chiesa et al., 2019) proof system.
In the block cipher construction, MiMC utilizes a permutation polynomial over Fq as round, consisting in the addition of the key, a round constant, and the application of a power map function:
And iterating over the round function F:
…
Using the same permutation in a Feistel network, we can process two field elements if we multiply the numbers of rounds by 2. In this case, the round function is:
Finally, the MIMCP permutation is created by setting k = 0 and the hash function by instantiating a sponge construction with the permutation.
Leo uses the scalar field of the BLS-12-377 curve with r = 8444461749428370424248824938781546531375899335154063827935233455917409239041.
In our case, we choose a parameter d = 11. According to Section 5.1 of the MiMC paper we need that the cubing in the round function creates a permutation so gcd(3, p-1) = 1, which is not possible in the case of the scalar field of the BLS-12-377 curve. For d = 5 and d = 7 we have the same problem. We estimate the number of required rounds with the number of rounds with 2 * (log p / log d) for the power map f(x) = xd and the permutation that uses the Feistel structure.
The Leo development environment can be installed from its repository. It only requires a Rust language installation. Via the leo command-line tool, we can build, test, generate and verify proofs for a given circuit or application.
For d = 11, we require 2 * (log p / log 11) = 145 rounds. We hardcode the round constants and implement the Feistel version that can be used in the block cipher with parameter k and in the hash function with k = 0 and by instantiating a sponge construction. We start with the design of the of the non-linear layer, that comprises the addition of a round constant and the power map with d = 11:
function non_linear(state: field, constant: field) -> field {
let c: field = state + constant;
let c2: field = c*c;
let c4: field = c2*c2;
let c8: field = c4*c4;
let c11: field = c8*c2*c;
return c11;
} In Leo, we can create functions using the field data type, that is, an element from the curve scalar field. We add the round constant and perform the power map. The syntax is more similar to Rust than to JS. The application of one round function consists on updating the state, composed of two field elements with the addition of the result of the application of the non-linear layer:
function round(state: [field; 2], constant:field) -> [field; 2] {
state[1] += non_linear(state[0], constant);
return state;
}Finally, we can precompute the round constants separately and we can create the permutation:
function permutation(state: [field; 2]) -> [field; 2] {
const N_ROUNDS:u32 = 147;
let RC: [field; 147] = [
3865702934124093755943890899496595264675194361091768380145853932420267718340,
1007157542023399026163733618843871954165432315393358131261818260851607860762,
4405765946538921025695035439523237362153599324827654321243952925829102897068,
3664456287923997818199382200327273463939055455139573605615804006507349414661,
[...]
let tmp: field = 0field;
for i in 0..N_ROUNDS - 1{
state = round(state, RC[i]);
tmp = state[0];
state[0] = state[1];
state[1] = tmp;
}
state = round(state, RC[N_ROUNDS - 1]);
return state;
} Leo allows us to create tests on the same file to test our functions, for instance, for the non-linear layer we can do:
@test
function sbox_test() {
let constant: field = 5943928848779486925441395077146413864173255127001087220085381147547751487102 ;
let state: field = 5324319209727394843353330183529117967230803372202482264714325483223508628524 ;
let check: field = 4817246075678656562069386914259487599241369120264717506466034175518663577036 ;
let result = sbox(state, constant);
console.assert(check == result);
}and the round function:
@test
function round_test() {
let state_in: [field; 2] = [
┆ 205590015168576069906775328287417415487799853627397567932093125904979123828,
┆ 6314658282813217945138278251984680094319698463151078319831502705046804707990
];
let constant: field = 7687545491407243578138660792989370259027838962927279562322213575702987063508;
let result_0: field = 205590015168576069906775328287417415487799853627397567932093125904979123828;
let result_1: field = 4768980667092361968239023698012060630723900845915064763583717922931253545522;
let result = round(state_in, constant);
console.assert(result_0 == result[0]);
console.assert(result_1 == result[1]);
}We can build the circuit and obtain the number of constraints with leo build:
$ leo build
Build Starting...
Build Compiling main program...
Build Number of constraints - 735
Build Complete
Done Finished in 23 millisecondsas well as create proving and verification keys and a proof that can be verify correctly via leo run:
Build Starting...
Build Compiling main program...
Build Number of constraints - 735
Build Complete
Done Finished in 38 milliseconds
Setup Starting...
Setup Saving proving key
Setup Complete
Setup Saving verification key
Setup Complete
Done Finished in 79 milliseconds
Proving Starting...
Proving Saving proof...
Done Finished in 54 milliseconds
Verifying Starting...
Verifying Proof is valid
Done Finished in 2 millisecondsSo far we have used the circom2 and Leo DSLs. However, there exist other options to describe zkSNARKs circuits using embedded DSLs such as bellman, gnark and arkworks-rs. In this section, we’ll implement the Griffin permutation in gnark using the BLS-12-381 curve. These libraries create an interface between pure R1CS constraints and the operations performed in the circuit e.g. modular multiplications and additions via an API.
We can use the gnark playground or install gnark in our project via go get. In circom2 all the signals are private by default. In gnark, signals are defined via the Circuit struct. For instance, declaring 3 (input) private signals (X0-X2) and 3 (output) public signals (Y0-Y2) is done via:
type Circuit struct {
X0 frontend.Variable `gnark:"x"`
X1 frontend.Variable `gnark:"x"`
X2 frontend.Variable `gnark:"x"`
Y0 frontend.Variable `gnark:",public"`
Y1 frontend.Variable `gnark:",public"`
Y2 frontend.Variable `gnark:",public"`
} Once we have defined a circuit using the arithmetic operations of the gnark front end api e.g. via api.Mul(x, x), we can obtain the R1CS representation of our circuit, for a particular curve supported by the library via:
var myCircuit Circuit
// generate R1CS
r1cs, err := frontend.Compile(ecc.BLS12_381, r1cs.NewBuilder, &myCircuit) after choosing a proving system (e.g. Groth16), we can perform the setup, generate the witness and the proof for verification:
pk, vk, err := groth16.Setup(r1cs)
witness, err := frontend.NewWitness(&myCircuit, ecc.BLS12_381)
publicWitness, err := witness.Public()
proof, err := groth16.Prove(r1cs, pk, witness)
err = groth16.Verify(proof, vk, publicWitness)but before creating the circuit for the Griffin permutation, we need to explain its structure.
Grifffin improves the performance of SPN-based schemes by using the so-called Horst mode of operation and the Rescue approach. The Feistel scheme
is replaced by
Griffin utilizes three non-linear functions:
,
, and
where g is a quadratic function.
In our example, we chose the parameters t = 3, R = 12, d = 5, based on the BLS-12-381 field. We apply the permutation to 3 field elements. Note that we are implementing only the Griffin permutation and that we need to instantiate a sponge in order to obtain the associated hashing function. The transformation applied to the three input field elements is the following:
,
, and
The parameters alpha and beta are chosen to be distinct values where a^2 - 4*beta is a quadratic non-residue modulo p. Li is a linear transformation:
For t = 3 we obtain the following non-linear layer implementation:
func non_linear(api frontend.API, x0 frontend.Variable, x1 frontend.Variable, x2 frontend.Variable) (frontend.Variable, frontend.Variable, frontend.Variable) {
alpha, _ := new(big.Int).SetString("20950244155795017333954742965657628047481163604901233004908207073969011285354", 10)
beta, _ := new(big.Int).SetString("3710185818436319233594998810848289882480745979515096857371562288200759554874", 10)
y0 := add_chain_exp_d_inv(api, x0)
y1 := exp_d(api, x1)
// l for t = 3
l := api.Add(y0, y1)
lq := api.Mul(l, l)
l = api.Mul(l, alpha)
l = api.Add(l, lq)
l = api.Add(l, beta)
y2 := api.Mul(x2, l)
return y0, y1, y2
} At the time of writing this post, gnark does not provide a gadget for native modular exponentiation (see for instance https://github.com/ConsenSys/gnark/issues/309). We need to implement the exponentation of 1/d, that is the modular inverse of 5 mod (p -1), used on the second field element of the input in the permutation, which corresponds to z = x^0x2e5f0fbadd72321ce14a56699d73f002217f0e679998f19933333332cccccccd. Since the gnark API provides the modular multiplication operation, one alternative could be to implement a variant of the square-and-multiply approach, which would yield a number of constraints based on the number of multiplication operations (more precisely, 254 doublings and 130 multiplications = 384 multiplication gates). On other other hand, since we are dealing with a fixed exponent operation, we can implement the power map using a short addition chain. In this case, we have used addchain to generate an addition chain for 1/d based on 305 multiplications and created a template for gnark.
The linear layer of Griffin for t = 3 is based on the circulant matrix cir(2, 1, 1), which results in adding the sum of the 3 input field elements to each of the elements of the state, that is, via the matrix:
which can be performed in gnark via:
func mds_t_3_no_rc(api frontend.API, x0 frontend.Variable, x1 frontend.Variable, x2 frontend.Variable) (frontend.Variable, frontend.Variable, frontend.Variable) {
/* for t = 3, M = circ(2,1,1)
┆ for state input (a, b, c) output is =
┆ | 2a + b + c |
┆ | a + 2b + c |
┆ | a + b + 2c |
*/
sum := api.Add(x0, x1, x2)
return api.Add(sum, x0), api.Add(sum, x1), api.Add(sum, x2)Finally, we can hardcode all the round constants and perform the 12 rounds:
rc10_0, _ := new(big.Int).SetString("0886bf20a448bd83746fe5e21995cf73911701f7ee2761575d47c44b3827dde5", 16)
rc10_1, _ := new(big.Int).SetString("70e9886f1de2e576b86c893ddf531b467cd42ea6eb6e4273034053284ff7cb02", 16)
rc10_2, _ := new(big.Int).SetString("4f1b3f6a9f91cfc548389964eefe28a3a9572224c5541962011b540f60b509d8", 16)
s0, s1, s2 := mds_t_3_no_rc(api, circuit.X0, circuit.X1, circuit.X2)
// round 1
y0, y1, y2 := non_linear(api, s0, s1, s2)
y0, y1, y2 = mds_t_3_rc(api, y0, y1, y2, rc0_0, rc0_1, rc0_2)
// round 2
y0, y1, y2 = non_linear(api, y0, y1, y2)
y0, y1, y2 = mds_t_3_rc(api, y0, y1, y2, rc1_0, rc1_1, rc1_2)
// round 3
y0, y1, y2 = non_linear(api, y0, y1, y2)
y0, y1, y2 = mds_t_3_rc(api, y0, y1, y2, rc2_0, rc2_1, rc2_2)
// round 4
y0, y1, y2 = non_linear(api, y0, y1, y2)
y0, y1, y2 = mds_t_3_rc(api, y0, y1, y2, rc3_0, rc3_1, rc3_2)
[...]Based on the first part of this post and this one, I have prepared a list of checks that could be used for validating implementations of zk-oriented schemes. Some of them are based on the DSL it self , others are based on the very nature of the zkSNARKs circuits themselves and finally, other mistakes can appear based on the lack of input validation of the upper layers in so-called zk-distributed applications.
Every arithmetic operation within a circuit is performed mod q, where Fq is the field of the pairing-friendly curve utilized. That means, that if it is possible to satisfy a circuit with inputs x0, x1, it is also possible to satisfy the same circuit with inputs (x0 + n*q, x1 + n*q). Even if this fact seems trivial, an application that uses a zkSNARK circuit with authorization purposes that don’t take this fact into account can believe that is accepting different valid inputs where at the same type they correspond to the same input. This fact is directly related to the next point, “collisions” in hash functions.
The same overflow example presented in the point above can be utilized for creating “collisions” in hash functions if the input is not validated in a zk-app. We can show this fact using the gnark playground. It contains an example using MiMC for proving the knowledge of a secret 0xdeadf00d with digest 5198853307513511565221857855889129613353124614036601136339058862251852610180.
// Welcome to the gnark playground!
package main
import (
"github.com/consensys/gnark/frontend"
"github.com/consensys/gnark/std/hash/mimc"
)
// gnark is a zk-SNARK library written in Go. Circuits are regular structs.
// The inputs must be of type frontend.Variable and make up the witness.
// The witness has a
// * secret part --> known to the prover only
// * public part --> known to the prover and the verifier
type Circuit struct {
Secret frontend.Variable // pre-image of the hash secret known to the prover only
Hash frontend.Variable `gnark:",public"` // hash of the secret known to all
}
// Define declares the circuit logic. The compiler then produces a list of constraints
// which must be satisfied (valid witness) in order to create a valid zk-SNARK
// This circuit proves knowledge of a pre-image such that hash(secret) == hash
func (circuit *Circuit) Define(api frontend.API) error {
// hash function
mimc, _ := mimc.NewMiMC(api)
// hash the secret
mimc.Write(circuit.Secret)
// ensure hashes match
api.AssertIsEqual(circuit.Hash, mimc.Sum())
return nil
}
-- witness.json --
{
"Secret": "0xdeadf00d",
"Hash": "5198853307513511565221857855889129613353124614036601136339058862251852610180"
}
However, if the input size is not validated in the application that uses the circuit, we can create other valid inputs, for instance 5198853307513511565221857855889129613353124614036601136339058862251852610180 + q*4 = 180304796282227713343193103817947330321740039817364875885924692354858320575116 that also satisfies the circuit. One way of avoiding this type of problems can be by enforcing input validation in the upper layer that uses the circuit. Moreover, DSLs such as circom2 allows inputs made of bits which can be used for accepting an input specific length.
Some languages include operators that can be problematic when used incorrectly. In a DSL we could expect that every assign operation including an arithmetic operator creates a constraint. This is the case when using the <== operator in circom2. However, it can be possible to assign a value including an arithmetic operation with the operator <--. In that case, a constraint is not created, which can be exploited for creating proofs with invalid inputs that pass as valid.
Finding errors in unconstrained R1CS circuits can be automated using tools such as Franklyn Wang‘s Ecne project, a tool which I contributed to during the 0xPARC 2nd learning group.
Many encryption and hash schemes designed for zero-knowledge applications require round constants generated with specific properties as well as parameters (such as alpha and beta in Griffin). These parameters are usually hardcoded to reduce the number of constraints in a circuit. Another example is choosing a valid value d in the power maps according to the pairing-friendly elliptic curve utilized.
The code written for this post is available at https://github.com/kudelskisecurity/zkhash_post.
Roman Walch, Franklyn Wang (Ecne Project), 0xPARC community.
Last update: 14th July 2022
After a long process started in 2016, today NIST announced the first standardized cryptographic algorithms designed to protect IT systems against future quantum attacks. Here is the list of the first winners of the competition:
For digital signatures:
For KEMs:
Additionally, the following candidate KEM algorithms will advance to the 4th and final round, even though they have not been standardized yet:
This is exciting news, as it marks a fundamental milestone in a very long process that the cryptography and security community has been following for many years. Quantum computers are rapidly advancing to a state of maturity that will allow soon to solve real-world problems in chemistry, physics, logistics, etc. Although cryptanalytic applications of quantum computers are probably still far away, given the long lifespan of security applications and the slow process of updating IT systems, businesses and governments have started to worry about quantum attacks for a while already. What was holding many stakeholders off from proactively starting a quantum-resistant strategy for their products and services was the lack of accredited international cryptographic standards. Now this obstacle has been removed, so we expect (and we welcome) a wave of renewed interest in quantum-resistant applications.
Infrastructure-as-Code (IaC) is great. It allows teams to deploy infrastructure quickly in a consistent and repeatable manner and when coupled with a proper CI/CD process (linting, SAST (Static Application Security Testing), 4-eyes reviews, multi-env, …) it creates a powerful security framework for platform and development teams.
However as great as IaC is, it does not prevent users from making mistakes; it is easy to wrongly expose a service and thus increase your attack surface or to deploy it in a way that conflicts with your compliance requirements.
Luckily Cloud providers offer guardrail functionalities to catch those mistakes and to enforce your compliance requirements.
Azure provides it under the Azure Policy feature; for Google it is called Organization Policies and for AWS (Amazon Web Services) it is Service Control Policies. The implementation methods and features differ between the different cloud providers, but the idea is the same; provide central control over the maximum available permissions for the accounts in your organization.
In this blog post I’ll cover how you can manage these guardrails as-code and how you can code unit-tests to validate them. We will focus on the Azure platform, but it could be easily reproduced on the others.
(all the code present is this blog-post is available on the following Github repository)
You need to start somewhere, and the blank page syndrome can be hard to overcome… My recommendation is to start with low hanging fruits. First, things that you never want to see happening in your production environment no matter what.
Ideally you should also pick things that will have little to no impact on your platform and development teams – it’s always frustrating to rollback or make people angry at the beginning of a new project. Also, keep in mind that you will need the support of these teams to progress on your Cloud-native security journey, so it is best if you have their buy-in day 1.
We’ll start with two simple use-cases:
Now we need to define where in the accounts hierarchy we want to apply these policies. Azure recommends organizing Subscriptions under Management Groups. In this blog post that’s where we’ll assign them, but they could be just as readily assigned at the Subscriptions level or at the Resource Groups level as well. Assigning policies at the top of the tree means that all the objects downwards will inherit them.
Policies can be defined inside the Azure Portal Policy page under “Authoring / Definition” but we’ll do it as-code using Terraform today.
We’ll focus on the policy for forbidden regions here but the code for both is available here.
Notes:
Now that the policies are created, we need to assign them to our Management Group (“Authoring / Assignments in the Azure portal). Without an assignation a policy has no effect.
That’s what we’ll do with the following code (source available here):
Notes
Now that we have created and assigned our policies we can do a quick test from the Azure portal, by trying to create a new NSG rule that voids the policy or by deploying a resource in a forbidden region.
We can see that our policies prevented the deployment of the resources, and that it did so during the evaluation process of the resource creation. This is quite powerful because it will warn users even before deploying the offending resources, instead of crashing with an error message at deployment-time.
The same will happen if we try to deploy the resource as-code, we will find the non-compliance error message inside the query response body.
A good policy framework must also support exemptions for certain rare use cases. Azure Policy provides that out-of-the box. We won’t cover exemptions in this blog post but they follow the same logic as policies assignments, you define a scope, a reason and optionally an expiration date for the exemption and that’s it.
For more details check the official documentation from Azure.
I could have stopped here, but I wanted to go a bit further than that. These policies are working as expected, but I still had the following questions open in my mind. How to make sure that:
Some of the questions above could be answered by the principle of least privilege, locking in the policies at the highest org-level and granting access only to certain super-admins. With infrastructure as-code, however, it is usually a service account that is used to push the changes on the platform and even with four-eye reviews, a mistake could happen.
To answer all these questions, I decided to implement unit tests. Initially I thought about doing them using Terraform code, but it was a bit cumbersome to catch and parse error messages and would mean that I had to wrap some bash or Golang around the Terraform code to achieve what I wanted to do.
Instead, I decided to implement the resource creation process using Golang code (leveraging the Azure SDK for Golang) and simply define unit tests using the standard testing package.
Here’s an extract of the testing scenarios for the forbidden regions (full code here).
And here’s an extract of the logic to iterate over all the tests (full code here):
Here’s an extract of the testing scenarios for the forbidden NSGs (full code here).
And here is how it looks like when being executed (here the NSG tests):
We can see that all the tests successfully passed as expected.
In this blog post we saw how to improve our Cloud-native security by implementing guardrails as-code leveraging Azure Policies.
We also saw how to make sure that these policies remain consistent over-time by coding some unit-tests in Golang.
It is understood that all the Terraform code and the unit tests must be part of steps in a Continuous-Integration/Continuous-Deployment (CI/CD) pipeline.
All the examples above are available on the following Github repository.
Finally if you have questions about cloud-native security or security in general feel free to reach out to us !
-Romain
Pretty Good Privacy (PGP) and the open source implementation GNU Privacy Guard (GPG) are encryption solutions following the OpenPGP standard. Even if GPG has been criticized in the past, it is widely used and deployed and has been publicly reviewed for many years. For example, GnuPG VS-Desktop has been recently approved by the German government to secure data at the VS-NfD (restricted) level. Thus it is used in practice to protect sensitive data, for example, to sign and encrypt emails, sign commits, or authenticate packages for several Linux distributions. To decrypt a message, the following command can be used:
$ gpg -d clear.gpg
gpg: encrypted with 3072-bit RSA key, ID 6F2C79C919966FC1, created 2021-07-21
"Test key <[email protected]>"
Hello GPGHello GPG
The first time the decryption is called, the system asks the user for their passphrase to decrypt the private key needed to decrypt the file.
Then for future decryption attempts, the passphrase is not asked but read from cache. The same mechanism is used for symmetric-key encryption. The cache time to live has a default value of 10 minutes. After the time to live elapsed, the cached item is cleared from memory.
To avoid having key material directly in the clear in memory, GPG encapsulates such key material before storing it in memory. The idea of that is that if a TPM is available, then the encapsulation key can be stored in a safe memory area. However, TPMs are usually not used, and the encapsulation key stays in regular memory.
A cached item is stored in the ITEM structure. We find this structure in gnupg/agent/cache.c (GPG version 2.3.4):
The ITEM structure is a linked list containing the cached item address and additional data. Among them, there are the time of creation and time of last access. These values are unix epoch times, the number of seconds elapsed since January 1, 1970. Then there is the time to live (ttl) field which is the number of seconds gpg-agent has to keep the item in cache. By default it is set to 10 minutes (0x0258 seconds). If gpg-agent found that the last accessed time is older than the time to live, the item is cleared from cache. After that we have the address of a secret_data_s structure. The secret_data_s structure contains the length of the cached item in bytes followed by the encrypted item with AES in key wrap mode. GnuPG uses AES key wrap mode of operation to encapsulate key material in memory as defined in RFC 3394. The AES key wrap algorithm is used to encrypt (wrap) keys or secrets with another key. It is used in several solutions like Apple FileVault 2 or Cryptomator. The mode uses two 64-bit blocks concatenated together as input of AES encryption:
This operation is iterated 6 times, and the final R values obtained are outputted as the ciphertext. Decryption works in exactly the same way but in reverse order. The initialization vector (IV) can be any value but the RFC default value is 0xa6a6a6a6a6a6a6a6. It allows for verification of the integrity of the decrypted key after the decryption. If the last decrypted block yields a value that starts with the IV, decryption is considered correct as long as no other error is returned. GPG uses the implementation of AES key wrap provided by the Libgcrypt library. In GPG, the cached item encryption is used to prevent attackers from simply grepping for passphrases in memory as commented in gnupg/agent/cache.c (GPG version 2.3.4):
However, as we will see later, someone who has access to the memory can also retrieve the encryption key and decrypt cached items anyway. To avoid having sensitive values left in memory after processing, Libgcrypt deletes those values when they are not used anymore. For example, a variable is wiped with the function wipememory and the stack is cleaned with the function _gcry_burn_stack. In Libgcrypt, the function _gcry_cipher_aeswrap_decrypt libgcrypt/cipher/cipher-aeswrap.c on line 81) did not clean a temporary variable containing the last decrypted block. Suppose we use GPG to decrypt some cleartext using a passphrase. At the end of the cached item decryption, the temporary variable contains the IV value 0xa6a6a6a6a6a6a6a6 followed by the first 8 bytes of the passphrase. For example, if a dump of gpg-agent’s memory using gcore or a dump of the whole system memory using LiME can be obtained, then, we should retrieve the constant 0xa6a6a6a6a6a6a6a6 in memory, next to the first 8 bytes of the passphrase. We reported this problem to GPG maintainers. This was quickly corrected in Libgcrypt 1.8.9 and future versions should not be affected by this issue.
Nevertheless, we investigated more to understand if it is possible to decrypt completely the passphrase in cache. We saw that each cached entry has two timestamps created and accessed of type time_t. This information can be leveraged to search for such patterns in memory and retrieve the location of cache_item_s instances. If we can estimate the time of the creation of the cached item, we can search for masked timestamps concatenated in memory followed by the time to live value. For example, the following regular expression matches all timestamps created after July 27, 2021 12:45:52 PM and before February 6, 2022 5:06:08 PM with a time to live of 10 minutes:
.{3}\x61\x00\x00\x00\x00.{3}\x61\x00\x00\x00\x00\x58\x02
To further reduce the number of false positives during the search, for each match, the created time can be checked to be less than or equal to the accessed time. Then, as soon as the ITEM structure has been found, we can access the secret_data_s structure.
To recover the encryption key, we used a known method to recover AES keys in memory. In AES, before data is encrypted, the AES key schedule is used to derive 11 subkeys that are used later in the algorithm.
These subkeys are usually stored consecutively in RAM and there are relations between each consecutive subkeys. Thus, we scan the memory byte per byte trying to see if at this position the AES key schedule relation are verified. If it is the case for two consecutive rounds, there is a very high probability that there are subkeys stored at this location. We scan the process memory until we find a 128-bit expanded AES key. Then we use this key to decrypt the cached item. If the integrity of AES key wrap is verified we know we have properly decrypted the cached item and recovered the passphrase.
At this point, we had everything we needed to implement our solution. Volatility is a widely used forensics framework. It is used to analyze volatile memory dump artifacts to extract data. For example, it has been used in the past to recover Bitlocker volume encryption keys while they are in RAM or to solve challenges of previous SSTIC editions. The framework is highly customizable and allows writing plugins in Python to fit specific needs. Therefore, we developed two plugins for Volatility3. The first plugin retrieves partial (or complete, up to 8 characters) passphrases from memory by searching in gpg-agent‘s memory the constant IV of aes-wrap. This plugin would not work on versions of GPG later than version 2.3.4.
$ vol -f ubuntu-21.10-vm-gpg.raw -s ./volatility-gpg/symbols/ -p ../gpg-mem-forensics/volatility-gpg/ linux.gpg_partial
Volatility 3 Framework 2.0.0
Progress: 100.00 Stacking attempts finished
Offset Partial GPG passphrase (max 8 chars)
0x7fb73d53a2a0 my_passpThe first 8 bytes of the passphrase were found in the clear in memory. The second plugin retrieves cached items and cache encryption keys from memory and therefore helps recover plaintexts. Here is an example of usage on an Ubuntu 21.10 VM dump:
$ vol -f ubuntu-21.10-vm-gpg.raw -s ./volatility-gpg/symbols/ -p ../gpg-mem-forensics/volatility-gpg/ linux.gpg_full
Volatility 3 Framework 2.0.0
Progress: 100.00 Stacking attempts finished
Offset Private key Secret size Plaintext
0x7fb738002658 0b78497b0d26239211b8841c59e943f7 32 my_passphraseThe plugin successfully found the entire passphrase my_passphrase in memory. The first plugin execution took 6.4 seconds and the second 59.7 seconds on an Intel Core i7-7600U CPU for a 1GB RAM dump.
Memory forensics may be used during a criminal investigation to analyze memory dumps obtained during a search and seizure. After the data has been copied, the investigator may need to obtain the passphrases stored encrypted in cached items to further decrypt conversations. These techniques may also be applied to investigate virtual machines stored remotely in servers that are seized.
Ransomware is a common problem nowadays. These malicious software encrypt files on an infected machine and ask the owner for a ransom so that they can recover their files. It happens that some ransomware rely on well studied tools to encrypt a user’s data. Ransomware such as KeyBTC, VaultCrypt or Qwerty use GPG to encrypt files. In the event that a victim of such a ransomware just noticed what happened when they get infected, the victim or the incident response team could make a memory dump of the whole system and later retrieve the password or decryption key from memory. Thus, thwarting the ransomware threat and retrieving the original files without having to pay a ransom at all. Note that the ransomware would have to rely on symmetric encryption for this to work (gpg --symmetric) and, so far, we have not found any ransomware relying on GPG symmetric encryption.
To conclude, we have analyzed a bug in Libgcrypt where after cleaning memory, it was still possible to read 8 bytes of the passphrase in the clear from a memory dump. We have further analyzed how to decrypt cached items stored in GPG memory. Our work highlights that GPG is a solid encryption solution, but it should be used in conjunction with a TPM or a secure enclave solution to harden the security against physical attacks.
This bulletin was written by Travis Holland and Eric Dodge of the Kudelski Security Threat Detection & Research Team
On May 18th, 2022, the U.S Cybersecurity and Infrastructure Security Agency (CISA) released Emergency Directive 22-03 requiring U.S Federal Government agencies to patch VMware vulnerabilities under active exploitation or vulnerabilities CISA expects to be exploited in the next 48 hours. Due to active exploitation of vulnerabilities made public in April, and additional vulnerabilities published in May, the Cyber Fusion Center strongly advises all organizations with vulnerable instances to take immediate action.
VMware has released two security advisories related to vulnerabilities that may be exploited by Nation State and advanced threat actors. VMSA-2022-0014 was issued on May 18th and contains detailed for two newly disclosed vulnerabilities: An authentication bypass issue, assigned, CVE-2022-22972 which impacts VMware Workspace ONE Access, Identity Manager and vRealize Automation, Additionally, a Privilege Escalation vulnerability was also disclosed, the vulnerability was assigned CVE-2022-22973, and impacts VMware Workspace ONE Access and Identity Manager. At this time neither are known to have been exploited in the wild, however, CISA, VMware, and the CFC expect threat actors to begin exploitation of these issues shortly.
In April of 2022, VMware produced a separate security advisory, VMSA-2022-0011, which contained details of eight (8) vulnerabilities, ranging from critical to moderate. The vulnerabilities disclosed in April include remote code execution, authentication bypass, local privilege escalation issues, and more. The vulnerabilities disclosed in April impact a wide range of VMware products, including VMware Workspace ONE Access, Identity Manager, and vRealize Automation. Some of the vulnerabilities disclosed in April are known to have been actively exploited in the wild by a wide range of threat actors. VMware has provided patches and workarounds for all identified vulnerabilities; however, the CFC strongly advises organizations to apply patches rather than leverage temporary workarounds as the workarounds can have a noticeable impact on business operations.
For additional details about these vulnerabilities, including versions of VMware software impacted, please review the rest of this bulletin.
Below is a table that highlights which VMware products are impacted by the vulnerabilities disclosed by VMware throughout the months of April and May. For additional details on these vulnerabilities, please review the contents of this bulletin and, if applicable, any linked sources and content.
On May 18th VMware released an advisory for two new vulnerabilities: CVE-2022-22972 and CVE-2022-22973. Those are broken down into an authentication bypass, and a local privilege escalation issue. They require network/local access to the respective VMware product User Interfaces in order to properly exploit the vulnerabilities. Due to the nature of these vulnerabilities, CISA has pushed an emergency directive requiring U.S Government Agencies to patch or mitigate these issues within 5 days. The vulnerabilities are not currently being exploited; it is expected to start occurring within the next 48 hours based on previous reverse engineering of similar vulnerabilities from April 2022.
CVE-2022-22972 is a critical severity authentication bypass vulnerability with a CVSSv3 score of 9.8. This vulnerability allows authentication bypass impacting any local domain users and requiring network access to the software’s User Interface.
Note that for some software systems, such as VMware Workspace ONE Access or VMware Identity manager, the User Interfaces may be intentionally exposed to the internet and thus should be prioritized for remediation.
CVE-2022-22973 is an important local privilege escalation vulnerability with a CVSSv3 score of 7.8. This vulnerability allows a malicious actor with local access to escalate privileges to ‘root
VMware recommends patching as soon as possible to remediate CVE-2022-22972 and CVE-2022-22973. The patch instructions can be found in KB88438, also provided below in the sources section. There currently is a workaround; however, it may have an impact on business operations, and patching is highly recommended. The workaround will make admins unable to log into Workspace ONE console via the local admin account. More information on performing the workaround can be found in KB8843; which is available below in the sources section.
Multiple vulnerabilities have been identified to impact several VMware products including Workspace ONE Access, Identity Manager, vRealize Automation, Cloud Foundation and vRealize Suite Lifecycle Manager. The Cyber Fusion Center is aware of several threat actors actively exploiting these vulnerabilities for initial access and strongly recommends organizations with vulnerable versions of the software assume breach and investigate deployments for potential compromise. VMware has provided patches to remediate all identified vulnerabilities and patches should be applied immediately.
Details regarding the vulnerabilities disclosed by
Critical severity remote code execution vulnerability exploiting server-side template injection with CVSSv3 score of 9.8. This vulnerability allows a malicious actor with network access the ability to trigger a server-side template injection potentially allowing code execution. This vulnerability is known to have been used by several threat actors to gain initial access to organizations with these VMware products deployed.
Critical severity authentication bypass vulnerability in the OAuth2 ACS Framework with a CVSSv3 score of 9.8. This vulnerability allows authentication bypass which allows the malicious actor the ability to execute any operation due to exposed endpoints in the authentication framework.
Critical severity remote code execution vulnerabilities with a CVSSv3 score of 9.1. This vulnerability allows code execution by triggering deserialization of untrusted data through a malicious JDBC URI.
Important severity cross site request forgery vulnerability with a CVSSv3 score of 8.8. This vulnerability allows a malicious actor to trick a user into validating a malicious JDBC URI through cross site request forgery.
Important severity local privilege escalation vulnerability with a CVSSv3 score of 7.8. This vulnerability allows a malicious actor with local access to escalate privileges to ‘root.’
Moderate severity information disclosure vulnerability with a CVSSv3 score of 5.3. This vulnerability allows a malicious actor with remote access to leak the hostname of the targeted system potentially leading to targeting victims.
VMware recommends applying available patches as soon as possible to the vulnerabilities described in this bulletin. The patch instructions can be found in KB88099, also provided below in the sources section.
VMware has provided temporary workarounds; however, they is a high likelihood that these workarounds will impact business operation. As such, the CFC strongly recommends applying patches as soon as possible rather than applying workarounds. Information on performing the workaround can be found in KB88098; which is available below in the sources section.
This bulletin was written by Michal Nowakowski of the Kudelski Security Threat Detection & Research Team
Microsoft released on May 19th an out-of-band patch to address the authentication issues encountered on Windows Servers with Domain Controller service enabled induced by the initial patch released on May 10th. Please follow Microsoft’s guidance on how to update your Domain Controllers.
Microsoft and the U.S CyberSecurity & Infrastructure Security Agency (CISA) recommend that organizations avoid installing some patches released on May 10th on servers acting as domain controllers. Patches provided by Microsoft on May 10th are causing some authentication issues to users. As such, Microsoft recommends currently only installing the patch on Windows Workstations and Windows Servers without Domain Controller service enabled.
The patches causing issues include the first patches for the vulnerability described in this advisory (CVE-2022-26923). Additionally other patches released by Microsoft (such as a patch for CVE-2022-26925, known as PetitPotam) appear to also cause authentication issues.
Organizations who may have already deployed Microsoft’s patches for the Certificate Services vulnerability described in this blog may consider changing the registry key entry named StrongCertificateBindingEnforcement (described in the “Solutions & Patches” section of this blog post) to a value of “0” in order to disable certificate mapping checks temporarily – while Microsoft works on addressing issues caused by this patch. Alternatively, organizations may choose to review windows event audit logs to identify offending certificates, and then manually map certificates that are causing authentication failures.
This blog post will be updated with the most recent information about this vulnerability as the situation progresses.
On May 10th Microsoft recently disclosed an Active Directory Domain Privilege Escalation Vulnerability (CVE-2022-26923) which was part of May 2022 Security Updates. It is a high severity vulnerability, which could allow any domain user to escalate privileges to that of a Domain Administrator if Active Directory Certificate Services (AD CS) are running on the domain.
This vulnerability stems from a bug in how machine certificates are issued by Active Directory Certificate Services which fails to check the if the SAM Account Name of the entity requesting a certificate matches the dNSHostName attribute of an issued certificate. Additionally, AD Certificate Services did not explicitly check for a “$” at the end of an account name (used to denote a machine account). By abusing this vulnerability, an attacker can request (& receive) a certificate for the DNS hostname of a domain controller. This certificate can be abused to impersonate a domain controller.
There are already numbers of publicly available Proof of Concept (PoC) exploits for the vulnerability, including detailed write-ups on how it works and how to abuse it. Microsoft has chosen to patch this vulnerability in a staged manner, first enabling auditing of suspicious or misconfigured certificates, and then later disallowing authentication using such certificates. Microsoft’s decision was made in order to prevent potential impact on a client’s Active Directory environment. The patches released May 10th enable additional auditing of certificates that may have been issued in error or could be malicious.
The Cyber Fusion Center strongly recommends that organizations who run Active Directory Certificate Services apply Microsoft’s provided patches as quickly as possible. Applying such patches will enable organizations to begin auditing certificates that may have been issued incorrectly – or malicious certificates that may have been issued due to this vulnerability.
For details regarding how to immediately enable features that block such misconfigured or malicious certificates, please review the patches and solution section of this advisory. For temporary mitigation options, please review the mitigations section of this advisory.
To successfully exploit this Privilege Escalation vulnerability and perform DCSync attack, an adversary would perform the following steps:
Attackers in possession of such a certificate can retrieve a hash of the domain controller’s domain account. This hash could then be used to impersonate a domain controller and replicate all domain user’s password data (known as a “DCSync Attack”) to a system the attacker controls.
Microsoft has released patches for this vulnerability in a staggered fashion in order to limit impact for organizations who may have misconfigured certificates. The patches released on May 10th, enable auditing to help organizations identify misconfigured or malicious certificates that are being actively used for authentication and do not prevent the usage of malicious certificates by default. Organizations can choose to enable enforcement.
Microsoft recommends that organizations leave AD Certificate Services / Authentication systems in “audit mode” for at least a month and work to review audit logs related to misconfigured certificates. Once organizations are confident that there will be no or little operational impact to enforcing additional security requirements to use certificates for authentication, they can enable enforcement by editing the following registry key (only available after the patch is installed):
Note: Microsoft will issue a patch in May 2023 to automatically enable enforcement
The CFC strongly recommends organizations deploy the May 10th patch and review audit logs for misconfigured certificates prior to this deadline.
Organizations who are not able to patch their Active Directory Certificate Services systems, could potentially consider hardening Active Directory Certificate Services (AD CS) environment by restricting certificate enrollment. Additionally, organizations may consider disabling the ability for regular / non-administrative domain users from enrolling new machine accounts to the domain.
As mentioned previously, the ability for regular users to enroll new machine accounts is enabled by default. Organizations can modify their Active Directory schema by modifying the “MS-DS-Machine-Account-Quota” attribute to disallow non-privileged users from enrolling any machine accounts
Note: Modifying the MS-DS-Machine-Account-Quota attribute does not necessarily prevent exploitation but reduces your overall attack surface for this vulnerability.
To obtain visibility into any activity potential exploit or attack activity related to the vulnerability described in this document, the Cyber Fusion Center is investigating additional detection capabilities identifying the manipulation of the servicePrincipalName attribute performed using the setspn.exe process. This process is used either to delete values that contain dNSHostNam or add new ones.
The CFC will continue to test and validate its detection methodology, once validated, the CFC will begin deployment of the detection to all relevant clients with Active Directory Certificate Services (AD CS) enabled. MDR ONE Clients will have detection capabilities as soon as the detection is finalized.
In parallel, the latest Windows Security Update added several new Event IDs which are currently being investigated by the Detection Engineering to understand how they could be leveraged for detection in the future.
I recently presented work on the analysis of a file encryption solution that claimed to implement “AES-1024 military grade encryption“. Spoiler alert: I did not break AES, and this work does not concern the security of AES. You may find advanced research regarding this topic.
This project started during a forensic analysis. One of my colleagues came with a USB stick containing a vault encrypted with SanDisk Secure Access software. He asked me if it was possible to bruteforce the password of the vault to recover the content. I did not know this software thus, I started to research. It appeared that this solution is distributed by Sandisk by default on any storage device you buy from them.
The solution is convenient, it allows a user to run the binary on the disk and after entering her correct password her vault is unlocked and the files are accessible. Once the software is closed, the files are encrypted back and not accessible anymore. So far nothing uncommon, but one thing drew my attention. In the Options menu, you can choose your “Preferred encryption method“.
I could choose ( if I would bought the premium version of the software) between several methods: “AES 128 bit“, “AES 256 bit“, “AES 512 bit” and “AES 1024 bit“. It was surprising to me since AES keys are defined in the standard to be either 128, 192 or 256-bit long but not 512 nor 1024 bits. Thus I was definitely interested to know what was behind this solution.
I dug a bit deeper and I discovered that the solution is developed for SanDisk by a company called ENCSecurity. The interesting part is that the solution is general and distributed to Sony and Lexar as well under different names. ENCSecurity also sells their own paying version with more options. I was surprised that the solution was not supported yet by John the ripper nor Hascat. In addition, the security claims of their website are really strong.
They claimed to provide “Ultimate encryption using 1024 bit AES keys, Military grade”. Thus for all those reasons, I decided to analyze the solution to figure out how it was implemented.
The binary is a PE packed with UPX. PE explorer allowed me to unpack it and still run properly. In the ENCSecurity version of the software, an option allows enabling the log of the application. At the beginning of the log I had:
05:11:42.633 D utils.cpp 372 showMessage returned 0
05:11:42.633 I encmainwindow.cpp 738 Starting ENCDataVault70 version: 7.1.1W
05:11:42.633 I encmainwindow.cpp 739 Date: 28.04.2021 05:11
05:11:42.633 I encmainwindow.cpp 740 Qt library version: 5.9.6
05:11:42.638 I encmainwindow.cpp 741 OpenSSL system library: OpenSSL 1.0.2q 20 Nov 2018
05:11:42.638 I encmainwindow.cpp 742 OpenSSL version: OpenSSL 1.0.2q-fips 20 Nov 2018
05:11:42.638 I enclogging.cpp 322 Application name: "ENCDataVault70"I knew it used OpenSSL and Qt libraries and I got the version number as well. It allowed me to create a Ghidra Function ID database on the same libraries and Ghidra matched some of the function signatures in binary. It simplified a lot the analysis since all the Qt functions could be left apart since they concern the GUI and the interesting functions use OpenSSL for Cryptography algorithms.
In fact from a general point of view, I was analyzing a password hash function. The function takes as input a user password and hashes it to a key which is later used to encrypt or decrypt data. Usually, the password hash function takes as input a unique and randomly generated salt to avoid precomputed attacks like dictionary or rainbow table attacks. Another common parameter of the hash function is the iterations number which allows to adapt the work factor. The higher the iteration number is the longer it will takes to compute the hash and thus, the harder it will to bruteforce the password for an attacker. Currently the are various recommended algorithms like: PBKDF2, Scrypt or Argon2. Argon2 is the winner of the Password Hashing Competition and is now considered as the state of the art for password hashing.
For this analysis, I only needed to focus on PBKDF2. Its design is simple:
It uses a HMAC function with the user password used as the input key. The input message is simply the salt concatenated with the constant 1. In the previous figure, c is the number of iterations. At the end we obtain a key. However with the current construction, the key cannot be larger that the output of the HMAC. So how do we construct 1024-bit keys? PBKDF1 was originally designed with this limitation. However, in PBKDF2, the solution was found to iterate several time the construction but with the input message to be the salt concatenated with constant 1 to obtain the first key part key[1], then the constant 2 is used to obtain the second key part key[2] and so on … Then the derived key is simply the concatenation of all the key part obtained during the iterations.
If we go back to our binary, the key derivation function was not identified directly by Ghidra Function ID and I had to reverse it manually. Thankfully, some calls to the MD5 hash function were identified under several layers of calls. Finally, after some efforts, I was able to reverse it. Here is how it looks:
The design is similar to PBKDF2 but they used MD5 hash which is not an HMAC function. The last thing missing was the generation of the salt. I struggled hard to find where this was generated but finally, I figured out it was hardcoded in the code directly.
It looks randomly generated but it is definitively not unique since all vaults created with the software would use the same salt for the key derivation. In addition, users using the same password would end up with the same decryption key. Later I discovered that the same salt value is also shared among all the vendors: SanDisk, Sony and Lexar. A less critical problem is that the number of iterations is also fixed and set to 1000. This number of iterations was good when PBKDF2 was designed but nowadays the iteration number has to be higher. For example, OWASP recommends now 310000 iterations when PBKDF2 uses HMAC-SHA-256. Nevertheless, the construction itself of the key derivation function is flawed.
The part in red does not depend on the salt or the constant. Thus it allows making precomputation attacks even if the salt is randomly generated by precomputing the part in red and XOR the result with the salt afterward. It also reduces the complexity of generating large keys since the part in red can be reused at each iteration. This shows once again that trying to implement custom Cryptography often leads to failure. This was the first problem I reported to ENCSecurity and CVE-2021-36750 was issued for this problem. ENCSecurity later patched the problem by using OpenSSL implementation of PBKDF2-SHA256 together with a randomly generated salt and 100000 iterations.
Now that I got the key derivation function, I checked how the password was verified to be correct. In fact, a file name filesystem.dat sored in the folder C:\Users\user\AppData\Local\ENCSecurityBV\ENCDataVault70\ENCDataVault contains an encrypted magic value. When the decryption of this magic value gives 0xd2c3b4a1 then the password is considered correct. The decryption algorithm used OpenSSL AES encryption. In fact for the AES-128 option, the encryption is simply AES in CTR mode with a 128-bit key generated from the key derivation function described earlier. However for the other modes the construction is more curious.
It uses multiple AES encryptions. Two for AES-256 option, four for AES-512 and eight for AES-1024. Each time AES encryption is performed with a 128-bit key. The key parts generated previously with the key derivation function are XORed to the first eight bytes of the nonce prior to the encryption and finally, all the results are XORed together. Once the password is checked to be correct eight file encryption keys are decrypted with the same algorithms. Those keys are used to encrypt and decrypt the file stored in the vaults. This is a common way to proceed since it prevents re-encrypting all the files if a user changes her password. Only the file encryption key has to be re-encrypted in this case.
I got everything I needed to implement a John the ripper plugin that allows everybody to bruteforce AES-1024 military grade encryption! The plugin is now integrated into the main repository and also includes also the bruteforce of the new key derivation function based on HMAC-PBKDF-SHA256.
The latest point I needed to elucidate was how the files themselves are encrypted. First I thought they used the same encryption algorithm based on AES. For AES-128 is still the same method, AES in CTR mode. However, I was not able to decrypt the vault using other options. I came back to Ghidra and reversed the algorithm further. It turned out that the file decryption algorithm is different.
It appears that only two iterations of AES is performed for any other option and only the last file key, for example, key[8] for AES-1024, is used and XORed with the nonce and counter. However, the construction is closed to CTR mode of operation and thus also has the malleability property. It means that if an attacker has access to the encrypted data he can make modifications that would not be detected during the decryption and the same modification is applied to the decrypted file.
In addition, the previous construction gives only a maximum security level of 256 bits since we theoretically have to bruteforce the first file key, key[1], and the last one key[8]. But we can do more, if we assume we know that two blocks that have the corresponding plaintext equal to zero we can write the following formula.
The plaintext is not involved in the equations since it is zero. Then we can decrypt each part of the equations to have:
Finally, we XOR both equations and we obtained the following result.
There is no further dependency on the last file encryption key and thus it shows a reduction to 128 bits of security. Indeed we only need to bruteforce the first file key until we obtain the right part of the equation which is known. We made the assumption that we had found two separate blocks matching the encryption of a zero block. In fact, files are encrypted in a way that includes some zero blocks. Let’s look at the encrypted file format.
The IVs are in clear followed by the file name length. Then the file name is stored encrypted followed by zero blocks until offset 0x200 where the encrypted file content starts. Thus, our previous analysis holds for this solution and shows that we have only a level of security of 128-bits for all the encryption options. Those problems were also reported to ENCSecurity and CVE-2021-36751 was attributed to that.
This analysis shows again that it is difficult to roll a custom cryptographic algorithm and also that the level of security of a solution does not depend on the number of encryptions performed.
This bulletin was written by Yann Lehmann of the Kudelski Security Threat Detection & Research Team
According to a recent report from the U.S. Cybersecurity and Infrastructure Security Agency (CISA) and the Multi-State Information Sharing & Analysis Center (MS-ISAC) released on May 18th, exploitation of the vulnerability has been observed on both government and private sector’s network.
Several POCs of exploits have since been released to the public, making the exploitation of that vulnerability much more accessible, including to less sophisticated actors. The Cyber Fusion Center (CFC) strongly urges its clients to apply the required patches to their affected devices. If any BIG-IP’s management ports or self IPs are or were publicly exposed, the CFC recommends to consider those devices as compromised and hunt for malicious activity. CISA and MS-ISAC have provided numbers of signatures for that purpose in the “Detection Methods” of the following CyberSecurity Advisory.
iControl REST is an evolution of F5 iControl framework. Leveraging this Representational State Transfer (REST) API, an authenticated user can accomplish anything that can be accomplished from the F5 BIG-IP command line. It is an extremely powerful API.
On May 04, 2022, F5 disclosed a critical CVE, CVE-2022-1388. It may allow an unauthenticated attacker with network access to the management port or the self IP addresses of the BIG-IP system to leverage the iControl REST component. This is because some requests to iControl REST can directly bypass the authentication mechanism. Due to the capabilities of this component, anyone with network access to the management port or the self IP addresses can execute arbitrary system commands and modify services or files. From the nature of the iControl rest component, this is a control plane vulnerability that does not expose the data plane.
At the time of writing there is no publicly known exploit of that vulnerability and F5 did not disclose any details on the requests that are able to bypass the iControl REST authentication. Moreover, with a good architectural design of the BIG-IP appliances the management port and the self IP addresses should not be directly exposed without control. However, according to CFC experience, such undisclosed requests are frequently quickly reversed-engineered by security researchers and malicious actors. As such the CFC recommends mitigating the risk immediately by patching. In addition, two others less-impacting vulnerabilities, CVE-2022-26415 and CVE-2022-29474, will also be mitigated by patching.
This CVE-2022-1388 impacts only the following BIG-IP versions.
BranchVulnerable VersionFix introduced inSeverity / CVSSv3Impacted component16.x16.1.0 – 16.1.216.1.2.2Critical / 9.8iControl REST15.x15.1.0 – 15.1.515.1.5.1Critical / 9.8iControl REST14.x14.1.0 – 14.1.414.1.4.6Critical / 9.8iControl REST13.x13.1.0 – 13.1.413.1.5Critical / 9.8iControl REST12.x12.1.0 – 12.1.6Will not fixCritical / 9.8iControl REST11.x11.6.1 – 11.6.5Will not fixCritical / 9.8iControl REST
If you are running a later component that the one mentioned in the fixed column above, that version should contain the fix and you are not impacted.
F5 provided fixes for the most recent branches of BIG-IP devices. The CFC recommends immediately patching your vulnerable version. If it does not exist, the CFC recommends upgrading to a newer branch.
Until it is possible to install a fixed version, F5 provided temporary mitigations which restrict access to iControl REST to only trusted networks or devices. As this decreases the attack surface drastically, the CFC recommends applying the described mitigation steps immediately, until the BIG-IP devices have been patched.
Those mitigation include restricting or blocking iControl REST access through management interface or the self IP addresses. Another possibility to mitigate the CVE consists in modifying the httpd configuration.
Please refer to the official documentation https://support.f5.com/csp/article/K23605346#proc1 for full details on how to apply mitigations.
The CFC also recommends reviewing the audit logs with the BIG-IP appliance for any suspicious activity.
While there are currently no known exploits, the CFC is currently contacting all Security Device Management (SDM) clients on F5 to organize the patching of all their impacted appliances and ensure there are no traces of exploitation of this CVE.
On February 23rd, the UK National Cyber Security Center (NCSC) with the US Cybersecurity &
Infrastructure Security Agency (CISA) and other security agencies released information that the
threat actor group known as “Voodoo Bear” or “Sandworm” has been leveraging a modular and
fairly sophisticated implant dubbed “Cyclops Blink”.
Cyclops Blink appears to be a replacement of the previously discovered and documented VPNFilter modular implant framework, also previously leveraged by Sandworm. The VPNFilter and Cyclops Blink implants primarily target Small Office/Home Office (SOHO) network devices. The VPNFilter implant was previously used by the threat actor to redirect and manipulate traffic and infected devices were also used to maintain persistence on victim networks.
The devices infected by Cyclops Blink have been incorporated into a large-scale botnet operated
by the threat actor, which appears to have first become active as early as June 2019. As of today,
of the 1500+ impacted IPv4 that were reported, around 40% are geolocated in the United States.
In its current iteration, Cyclops Blink is highly modular and provides attackers several capabilities
(as well as writing and deploying implant modules on the fly). Cyclops Blink has been observed
primarily targeting SOHO devices from WatchGuard (Watchguard Firebox appliances). Additionally, Cyclops Blink is deployed persistently on infected WatchGuard devices by abusing the firmware upgrade mechanism.
While Cyclops Blink has only been observed on WatchGuard devices as of today, an assessment of the malware reveals that it could also be compiled and deployed onto other architectures and
firmware.
Organizations with WatchGuard firewalls should review the solution section of this advisory for
details on how to identify a potential infection and restore the system to a known good state. If the Watchguard management interface was exposed to the internet, organizations should assume the appliance has been compromised and investigate the system for signs of the implant prior to upgrading.
All Watchguard Firebox appliances are currently known vulnerable. As such organizations with
Firebox appliances must be upgraded to the latest versions for the Firebox appliances as soon as
possible. The latest Firmware for WatchGuard Firebox appliances is available for download from:
https://software.watchguard.com/
Before upgrading any appliances, it is critical to assess whether your Firebox appliance may have
been infected with Cyclops Blink. Watchguard, with the assistance of the NSA, CISA, and UK NCSC
have provided with different methods to investigate and identify a potential infection as described in https://detection.watchguard.com/
CISA and the NCSC both describe the Cyclops Blink malware as a successor to an earlier
Sandworm tool known as VPNFilter, which had infected over half a million routers before it
identified by Cisco and the FBI and dismantled in 2018.
This implant is a multi-stage, modular platform with versatile capabilities to support both
intelligence-collection and potentially destructive cyber-attack operations. It targets devices
running firmware based on Busybox and Linux and is compiled for several CPU architectures.
The first stage primary ensures persistence (via crontab) which sets it apart from other IOT
malware such as Mirai. Furthermore, it implements various redundant mechanisms to resolve the address of the second stage deployment server. The second stage once downloaded exposes the usual modules of a remotely management implant Command-and-Control including:
• File collection
• Command execution
• Data exfiltration
• Device management
However, some of the most interesting modules are implemented in a third stage and are
deployed independently as “plugins”. One such plugin implements a packet sniffer that allows
inspection of traffic and consequently theft of credentials.
The Cyclops Blink malware comes in the form of a firmware update which abuses Watchguard’s
standard firmware upgrade to install the malicious firmware. It leverages a vulnerability in the
firmware update process where the Hash-based Message Authentication Code (HMAC) can be
recalculated due to a hard-coded key in WatchGuard Firebox devices used to initialize hash
calculation. This allows persistence between reboots.
The Cyclops Blink malware has the following capabilities (most critical ones listed):
• Add a new module to Cyclops Blink.
• Update the Cyclops Blink Linux ELF executable.
• Update the list of C2 server IPv4 addresses
• Resend the current Cyclops Blink configuration to all running modules
• Gather all system information like sysinfo, /etc/passwd, /proc/mounts/, …
The full technical details are linked in the reference section.
Firmware upgrades are available and if you have a legitimate firmware running in your Fireboxes
you need to upgrade to the latest versions.
If your Fireboxes have been impacted by a malicious firmware you first need to remediate as
described in watchguard’s documentation listed below:
https://techsearch.watchguard.com/KB?type=Article&SFDCID=kA16S000000SNyiSAG&lang=en_US
To mitigate the risks until upgrading to the latest version the CFC recommends:
• Ensuring network devices’ management interfaces are not exposed to the internet.
• Ensuring strong authentication material, rotated regularly, on Firebox devices management
interface.
• Monitoring firewall management activities on Fireboxes that have not yet been updated
The CFC has created hunting campaigns and compiled IOCs to identify potential communication
with known Cyclops Blink C2 servers.
• https://www.cisa.gov/uscert/ncas/alerts/aa22-054a
• https://www.watchguard.com/wgrd-news/blog/important-detection-and-remediationactions-cyclops-blink-state-sponsored-botnet
• https://detection.watchguard.com/
https://techsearch.watchguard.com/KBtype=Article&SFDCID=kA16S000000SNyiSAG&lang=en_US
• https://www.ncsc.gov.uk/files/Cyclops-Blink-Malware-Analysis-Report.pdf
• https://www.shadowserver.org/news/shadowserver-special-reports-cyclops-blink/
• https://blog.talosintelligence.com/2018/05/VPNFilter.html
In the last few years, several practitioners have proposed zk-focused cryptographic constructions such as hashing and encryption primitives that operate on binary and prime fields and that have a low multiplicative complexity. They are also called arithmetization-oriented primitives. Some examples are the Reinforced Concrete, Rescue and MiMC hashing functions. These constructions typically target zkSNARKs and STARKs -based applications.
In this post, we focus on Ciminion, an authenticated-encryption scheme proposed by Dobraunig et al. and presented at EUROCRYPT 2021 and describe how it can be implemented using a domain specific language (DSL) for writing zkSNARKs circuits. Then, we compare our implementation with the MiMC cipher in Feistel mode (which uses a permutation that is widely used in circuits), and show how our Ciminion implementation outperforms it for a large number of plaintexts.
zkSNARKs make it possible to convince another party that a particular statement is true restricting other information about the statement to a minimum. In this case, the statement consists on a deterministic arithmetic circuit with inputs and outputs. The recent availability of domain specific languages (DSLs) for creating zk-focused applications and circuits (some examples are circom2 and Leo) allows to speed-up the creation of privacy- friendly applications.
There are certain categories of applications that can be easily described using zkSNARKs:
Finally, both zkSNARKs and STARKs are typically used in Layer-2 constructions and have been proposed in a wide range applications such as network traffic compliance and verifiable machine learning.
In this article, we focus on zkSNARKs DSLs, which provide a direct path for building privacy-friendly applications. We refer the reader to different resources for learning the specifics of zkSNARKs, together with recent advances such as PlonKup, elastic SNARKs and Nova.
Using a DSL such as circom2, one can describe a zkSNARK as an arithmetic circuit with inputs (which can be private, public or a mix of both) and outputs. The circom2 compiler transforms the circuit description into a Rank-1 Constraint System (R1CS). Other tools such as snarkjs rely on the output of the circom2 compiler to provide the verifier and prover components that can be used to build applications based on zkSNARKs.
Arithmetic operations in the circuit are always performed modulo a large prime and in the case of circom2, within the scalar field of the pairing-friendly curve BN2541 by default (whose security level was decreased to 103 bits in https://eprint.iacr.org/2019/885). However, it can be compiled to use the BLS-12-381 curve.
A zk-application might need to perform a hash operation, to encrypt a sensitive value or to derive an authentication tag of a message. Even if typical constructions such as SHA-3 and an AES modes could be implemented in a DSL, the performance in terms of number of constraints of the resulting circuits would be affected by schemes that rely on bitwise operations. For this reason, in the last few years several practitioners have proposed constructions such as the MiMC, Poseidon, and Rescue hashing algorithm and ciphers such as GMiMC and Ciminion. These constructions mainly operate on prime and binary fields and try to reduce the number of expensive arithmetic operations such as multiplications.
Ciminion is an authenticated-encryption scheme that was presented at EUROCRYPT 2021 by Dobraunig et al. It has been designed to target zero-knowledge proof applications such as zkSNARKs, STARKs and multi-party computation. It requires a limited number of field multiplication and it can be implemented over a prime field.
Ciminion reduces the amount of field multiplications by using the Toffoli gate and the Farfalle construction in order to minimize the number of rounds. In contrast, to other schemes such as MiMC that uses the power mapping f(x) = x^3, the Toffoli gate transforms a triple (a, b, c) into a triple (a, b, ab + c).
Farfalle is a permutation-based construction for a pseudorandom function (PRF) that focuses on parallelization and was designed by the Keccak Team in 2016. It typically uses a family of permutations with different number of rounds, and three layers: a mask derivation function, a compression layer (pC) and a expansion layer (pE). The Farfalle construction was designed with versatility in mind and can be transformed into an AE construction.
Ciminion receives the following input parameters: a nonce N and two subkeys (K_1 and K_2). It first applies the permutation pC to them and ouputs an intermediate state. Then, this state is transformed by the pE permutation. Two of the resulting elements are used to encrypt the first two plaintext elements P_1 and P_2. The rest of plaintext elements P_2i and P_2i+1 are processed as follows: another pair of subkey elements are added to the intermediate state. Then, the rolling function and the pE permutation are applied to obtain another two field elements that are finally used to encrypt the subsequent pair of plaintext field elements.
Both the pE and pC permutations transform a triple (a, b, c) using the round function with different number rounds:
RC are the fixed round constants. They are generated using SHAKE-256 and can be precomputed before performing the authenticated-encryption operation. Finally, the rolling function performs the Toffoli gate operation:
In Ciminion, a set of subketys needs to be generated for performing authenticated-encryption. This is performed using two master keys, MK1 and MK2 and a public IV. Ciminion expands the master key elements using a sponge construction that relies on the pC permutation:
For a given circuit written in circom2, the compiler generates the proof and a R1CS version of the circuit in the form of (A * B) – C = 0. Further, a zkSNARK implementation such as snarkjs can use either Groth16 or PLONK to verify the proof.
In circom2, each circuit is considered a component that can be imported in another circuit in a way that it is possible to generate a library of reusable gadgets such as circomlib. Constrains in the circom2 library are described using the “===” operator and by default, all the signals are private.
We refer the reader to the circom2 documentation for installation instructions and language details. We have found hardhat-circom and the circom2 syntax plugins for vscode and vim very useful.
In this section, we explain how to implement the Ciminion components in circom2.
First, we start with the smaller components and we start composing them in a bottom-up fashion til arriving at the Farfalle-like construction of Ciminion. The rolling function it is the simplest component operation of Ciminion. It just performs the Toffoli gate operation. This is a component with 3 inputs and 3 outputs, being the triple transformed the output:
pragma circom 2.0.3;
template Rolling() {
signal input s0;
signal input s1;
signal input s2;
signal output b0;
signal output b1;
signal output b2;
b0 <== s2 + s0*s1;
b1 <== s0;
b2 <== s1;
}The Ciminion round function involves the following inputs: the triple a, b, c (e.g. a_0, b_0, c_0), four round constants (e.g. RC_0, RC_1, RC_2, RC_3) and 3 outputs: a_1, b_1, c_1, that is,
the output triple after performing the transformation operation. Then, we can instantiate the permutation (round function f_i) to create the iterated permutations pC and pE:
pragma circom 2.0.3;
template Permutation() {
signal input a0;
signal input b0;
signal input c0;
signal input RC0;
signal input RC1;
signal input RC2;
signal input RC3;
signal output a1;
signal output b1;
signal output c1;
signal a0_mul_b0_plus_c0_plus_b0;
a0_mul_b0_plus_c0_plus_b0 <== a0*b0 + c0 + b0;
a1 <== c0 + a0*b0 + RC2;
b1 <== a0 + RC3*(a0_mul_b0_plus_c0_plus_b0) + RC0;
c1 <== a0_mul_b0_plus_c0_plus_b0 + RC1;
}Once we have the permutation implemented, we only need to iterate during a specific a number of rounds and the corresponding list of round constants:
template IteratedPermutationN() {
signal input a0;
signal input b0;
signal input c0;
signal output a1;
signal output b1;
signal output c1;
var c[536] = [
292334644102394411537362212093572878140,
250282066453690133315708418387534650045,
25210252274841859825108081164557115781,
16246747660448753010909888379129524409,
131669148524554050620166690622542333908,
73395003443371763039182051680716568403,
[...]Given a number of rounds nRounds per permutation, we instantiate one Permutation component per iteration (in circom2, a value can be assigned only once to a signal). The outputs of a permutation component i are redirected to the input of a permutation component i+1 and the final triple consists of the output of the permutation component nRounds – 1:
component perm[nRounds];
for (var i=0; i<nRounds; i++) {
perm[i] = Permutation();
RC0 = c[4*i];
RC1 = c[4*i + 1];
RC2 = c[4*i + 2];
RC3 = c[4*i + 3];
perm[i].RC0 <== RC0;
perm[i].RC1 <== RC1;
perm[i].RC2 <== RC2;
perm[i].RC3 <== RC3;
if (i == 0) {
perm[i].a0 <== a0;
perm[i].b0 <== b0;
perm[i].c0 <== c0;
} else {
perm[i].a0 <== perm[i-1].a1;
perm[i].b0 <== perm[i-1].b1;
perm[i].c0 <== perm[i-1].c1;
}
}
a1 <== perm[nRounds - 1].a1;
b1 <== perm[nRounds - 1].b1;
c1 <== perm[nRounds - 1].c1;
}The key generation operation in Ciminion takes as input the IV and two master keys. It iterates the permutation pC (permutation N in the Ciminion reference code) on this input in order to generate the subkeys K_i. The output corresponds to the first value of the output triple (a1, b1, c1), that is a_i for subkey K_i. We can generate a component that is instantiate according to the number of sub keys e.g. nKeys:
pragma circom 2.0.3;
include "permutation.circom";
template KeySchedule(nKeys) {
signal input s0;
signal input s1;
signal input s2;
signal output keys[nKeys];
component p_n[nKeys];
for (var i=0; i<nKeys; i++) {
p_n[i] = IteratedPermutationN();
if (i == 0) {
p_n[i].a0 <== s0;
p_n[i].b0 <== s1;
p_n[i].c0 <== s2;
} else {
p_n[i].a0 <== p_n[i-1].a1;
p_n[i].b0 <== p_n[i-1].b1;
p_n[i].c0 <== p_n[i-1].c1;
}
keys[i] <== p_n[i].a1;
}
}Finally, we have all the components to generate the authenticated-encryption
primitive.
This component will use:
We receive as inputs: the nonce and the two master key elements, nPairs
of plaintexts and we output: a TAG element that authenticates nPairs
of ciphertexts:
template CiminionEnc(nPairs) {
var nSubKeys = 2*nPairs + 3;
signal input MK_0;
signal input MK_1;
signal input nonce;
signal input PT[nPairs*2];
signal output CT[nPairs*2];
signal output TAG; The first part of the encryption operation starts the key schedule:
component key_schedule = KeySchedule(nSubKeys);
key_schedule.s0 <== 1;
key_schedule.s1 <== MK_0;
key_schedule.s2 <== MK_1; Then, the permutation pC is applied to the supplied nonce and to the first pair of subkeys.
Then, for each pair of plaintexts, the rolling and pE permutation are applied:
for (var i = 0; i < nPairs; i++) {
// roll
rolls[i] = Rolling();
if (i == 0) {
rolls[i].s0 <== p_n.a1 + key_schedule.keys[2*i + 4];
rolls[i].s1 <== p_n.b1 + key_schedule.keys[2*i + 3];
rolls[i].s2 <== p_n.c1;
} else {
rolls[i].s0 <== rolls[i-1].b0 + key_schedule.keys[2*i + 4];
rolls[i].s1 <== rolls[i-1].b1 + key_schedule.keys[2*i + 3];
rolls[i].s2 <== rolls[i-1].b2;
}
// second permutation pR
p_rs[i] = IteratedPermutationR();
p_rs[i].a0 <== rolls[i].b0;
p_rs[i].b0 <== rolls[i].b1;
p_rs[i].c0 <== rolls[i].b2;Afterwards, ciphertext pairs are generated and the MAC is updated:
CT[2*i] <== p_rs[i].a1 + PT[2*i];
CT[2*i + 1] <== p_rs[i].b1 + PT[2*i + 1];
// MAC generation
if (i == 0) {
acc_1[i] <== CT[2*i] * key_schedule.keys[0];
acc_2[i] <== acc_1[i] + CT[2*i + 1];
MAC[i] <== acc_2[i] * key_schedule.keys[0];
} else {
acc_1[i] <== (MAC[i-1] + CT[2*i]) * key_schedule.keys[0];
acc_2[i] <== acc_1[i] + CT[2*i + 1];
MAC[i] <== acc_2[i] * key_schedule.keys[0];
}
}The output, corresponds to the ciphertext pairs and the tag:
component p_r2 = IteratedPermutationR();
p_r2.a0 <== inner_upper_branches_0;
p_r2.b0 <== inner_upper_branches_1;
p_r2.c0 <== inner_upper_branches_2;
TAG <== MAC[nPairs - 1] + p_r2.a1;circom2 allows to debug and test a circuit implementation via Mocha. In this section, we show how we could test the Ciminion implementation that we have created. First, we’ll need to declare a main component in the circuit description that we want to test. We start with the Ciminion rolling function:
component main = Rolling();Via the ffjavascript package we can perform finite field arithmetic operations within the BN254 curve scalar field and can compare the results. For instance, we can generate random inputs for the Ciminion rolling function and execute the function in JavaScript:
const F1Field = require("ffjavascript").F1Field;
const Scalar = require("ffjavascript").Scalar;
const crypto = require('crypto').webcrypto;
exports.p = Scalar.fromString("21888242871839275222246405745257275088548364400416034343698204186575808495617");
const Fr = new F1Field(exports.p);
let a = new BigUint64Array(1);
let r1 = (crypto.getRandomValues(a)[0]);
let r2 = (crypto.getRandomValues(a)[0]);
let r3 = (crypto.getRandomValues(a)[0]);
const s0 = Scalar.fromString(r1);
const s1 = Scalar.fromString(r2);
const s2 = Scalar.fromString(r3);
const b0 = s2 + s0*s1;
const b1 = s0;
const b2 = s1; We obtain the witness values from the rolling circuit:
const circuit = await wasm_tester(path.join(__dirname, "circuits", "rolling.circom"));
let witness;
witness = await circuit.calculateWitness({ "s0": s0, "s1": s1, "s2":s2}, true);and compare:
await circuit.assertOut(witness, {"b0": b0});
await circuit.assertOut(witness, {"b1": b1});
await circuit.assertOut(witness, {"b2": b2});From command line, we invoke Moch:
$ mocha rolling.js
Rolling function
✔ Conformance test (47ms)
1 passing (52ms)Finally, we can also test that encryption was performed correctly by decrypting the result. In that case, we can first write a circuit that decrypts a set of ciphertexts and call both circuits from mocha.
In order to reverse the encryption operation, we need to obtain the plaintexts as:
PT[2*i] <== CT[2*i] - p_rs[i].a1;
PT[2*i + 1] <== CT[2*i + 1] - p_rs[i].b1 ;We import both encryption and decryption circuits and check the authentication
tag and the decryption values:
/* Decryption test for Ciminion circuit */
const chai = require("chai");
const path = require("path");
const F1Field = require("ffjavascript").F1Field;
const Scalar = require("ffjavascript").Scalar;
exports.p = Scalar.fromString("21888242871839275222246405745257275088548364400416034343698204186575808495617");
const Fr = new F1Field(exports.p);
const wasm_tester = require("circom_tester").wasm;
const assert = chai.assert;
describe("Ciminion - encryption operation", function () {
this.timeout(100000);
it("Authentication tag check", async() => {
const ciminion_input = {
"MK_0": "0",
"MK_1": "0",
"nonce": "1",
"IV": "1",
"PT": ["21888242871839275222246405745257275088548364400416034343692024637573625142322", "21888242871839275222246405745257275088548364400416034343693920155242279081918", "21888242871839275222246405745257275088548364400416034343692024637573625142322", "21888242871839275222246405745257275088548364400416034343693920155242279081918"]
};
const ciminion_input_dec = {
"MK_0": "0",
"MK_1": "0",
"nonce": "1",
"IV": "1",
"CT": ["21592519839218542425120198614531742298033892440087867998118713380820756220718","7889798674627961413366316750795654309310714845357364960283444849787781529858","21049421697506414118152249991945313702405695293538082623907752021251428302407","5714257272097132615426035247399194719164619087183836862864633319728296164225"]
};
const circuit = await wasm_tester(path.join(__dirname, "circuits", "ciminion_enc.circom"));
const circuit_dec = await wasm_tester(path.join(__dirname, "circuits", "ciminion_dec.circom"));
let witness;
let witness_dec;
witness = await circuit.calculateWitness(ciminion_input, true);
await circuit.assertOut(witness, {"TAG": "1300322832108596540141310981879129316384285895603221372961580627161106587830"});
await circuit.assertOut(witness, {"CT": ["21592519839218542425120198614531742298033892440087867998118713380820756220718","7889798674627961413366316750795654309310714845357364960283444849787781529858","21049421697506414118152249991945313702405695293538082623907752021251428302407","5714257272097132615426035247399194719164619087183836862864633319728296164225"]});
});
it("Decryption check", async() => {
const ciminion_input = {
"MK_0": "0",
"MK_1": "0",
"nonce": "1",
"IV": "1",
"PT": ["21888242871839275222246405745257275088548364400416034343692024637573625142322", "21888242871839275222246405745257275088548364400416034343693920155242279081918", "21888242871839275222246405745257275088548364400416034343692024637573625142322", "21888242871839275222246405745257275088548364400416034343693920155242279081918"]
};
const ciminion_input_dec = {
"MK_0": "0",
"MK_1": "0",
"nonce": "1",
"IV": "1",
"CT": ["21592519839218542425120198614531742298033892440087867998118713380820756220718","7889798674627961413366316750795654309310714845357364960283444849787781529858","21049421697506414118152249991945313702405695293538082623907752021251428302407","5714257272097132615426035247399194719164619087183836862864633319728296164225"]
};
const circuit_dec = await wasm_tester(path.join(__dirname, "circuits", "ciminion_dec.circom"));
let witness_dec;
witness_dec = await circuit_dec.calculateWitness(ciminion_input_dec, true);
await circuit_dec.assertOut(witness_dec, {"PT": ["21888242871839275222246405745257275088548364400416034343692024637573625142322", "21888242871839275222246405745257275088548364400416034343693920155242279081918", "21888242871839275222246405745257275088548364400416034343692024637573625142322", "21888242871839275222246405745257275088548364400416034343693920155242279081918"]});
});
});Finally, we can also test a circuit that just recompute the MAC of a given ciphertext and import it:
it("MAC recheck", async() => {
const ciminion_input_dec = {
"MK_0": "0",
"MK_1": "0",
"nonce": "1",
"IV": "1",
"CT": ["21592519839218542425120198614531742298033892440087867998118713380820756220718","7889798674627961413366316750795654309310714845357364960283444849787781529858","21049421697506414118152249991945313702405695293538082623907752021251428302407","5714257272097132615426035247399194719164619087183836862864633319728296164225"]
};
const circuit_mac = await wasm_tester(path.join(__dirname, "circuits", "ciminion_mac.circom"));
let witness_mac;
witness_mac = await circuit_mac.calculateWitness(ciminion_input_dec, true);
await circuit_mac.assertOut(witness_mac, {"TAG": "1300322832108596540141310981879129316384285895603221372961580627161106587830"});
});We have compared the number of constraints required for implementing Ciminion with those of MiMC in encryption mode (particulary Feistel MiMC-2n/n). The MiMC construction is typically used in circom2 circuits. We see that Ciminion scales better for larger plaintexts, due to the utilization of the Farfalle construction in comparison to the MiMC construction based on the Feistel structure.
We have released the code and tests utilized in this article in our GitHub repository.
Part of this work was done during the 2nd 0xPARC Learning Group.
Notes
1The BN254 curve security level has been estimated in around 103 bits at the time of writing this post. See https://eprint.iacr.org/2022/586.
Last update: 14th July 2022