Repository files navigation

• Build status:
• Code coverage:report

Thecosign tool allows multiple cooperating parties to generate an RSAkey and split the private key into shards between themselves, and thenperform partial signatures of a message that can be combined into a singlevalid RSA signature of that message, without any of the parties havinga complete copy of the private key after the initial key generation stage.

In the unanimous mode the number of parties is unlimited, although in thismode all thecosigning parties must perform their partial signatureto be able to generate a valid RSA signature. It is also simplifiedin that the initial key splitting stage requires a "trusted dealer"to perform the split and hand the shards to the parties.

There is a separate threshold mode that splits the key into three shards,two of which are required for signatures, a so called 2-of-3 threshold scheme.If the third shard is lost, the two can be recombined to create a newset of three shards. This also requires a trusted dealer for generationor re-sharding.

WARNINGcosign is currently in the proof-of-concept stage. The securityproperties of the key sharding has not been reviewed for vulnerabilitiesand the Python modular exponentiation function is not side-channel safe.

One use case for this sort of signature system is an automated CertificateAuthority (CA) that signs SSL certs. By splitting the CA's Root Key tomultiple separate machines it becomes harder for an attacker to stealthe root key and produce unauthorized signed certs for domains they donot control. The logging mechanisms can also be spread across multiplemachines, making it harder for rogue certs to be secretly signed.

Another example use for this is to interoperate with UEFI Secureboot,which requires a single RSA signature on an executable to accept it.For high-assurance use cases, it is desirable that multiple parties mustreproducibly build the firmware image and individually sign the imageso that no single developer can subvert the security of the boot process.

In the unanimous mode (or a k-of-k threshold), a valid signature alsoindicates unanimous consent by the parties performing the signing.If any of them do not sign or provide a bad partial signature, then theresulting merged signature will not be valid. It is not possible toidentify which party generated an invalid partial signature.

The tool has a few modes: key generation (unanimous or threshold),partial signature generation, partial signature merging, andthreshold key regeneration.

cosign genkey N basename

Produces a 2048 bit RSA key pair in memory and divides it into N private keysharesbasename-0.key,basename-1.key, ...basename-(N-1).keyand the public keybasename.pub. The public key can be published andthe inidividual key shares should be sent to the cosigners under separatesecured channels.

After generation the shares should never be brought together since theprivate key can be regenerated from all of them together.Additionally, the key shards currently are not password protected,so the recipients must protect them.

cosign threshold basename [keyN.key keyM.key]

Generates a 2048 bit RSA key pair in memory, or if two shards areprovided regenerates the private key from them, then divides theprivate key into three private key shares.

After generation the shares should never be brought together since theprivate key can be regenerated from all of them together.Additionally, the key shards currently are not password protected,so the recipients must protect them.

These threshold keys are not proper RSA keys and must be used withthecosign tool. Two out of the three are required to producea signature.

cosign sign key-n.key < file > sig-n

Uses partial key to hash stdin and pad the hash with PKCS#1 v1.5, thensign the padded value with the partial key and writes signature to stdout.Each cosigning party must do this separately and send their partialsignatures to a coordinator to combine them.

This process must be done on a trusted machine to avoid leakingthe private key shard. The cosigning parties can work in paralleland do not need to communicate other than that they are all signingthe same message.

For threshold keys the signatures are done twice, once for eachpair-wise portion of the private key that they hold. Only twoof the three are required for merging.

cosign merge key.pub sig-* > file.sig

Merges the partial signature files into a full signature. Forunanimous keys all of the cosigning parties must produce partialsignatures, while threshold keys only require two of the threeshards. In either case the partial signatures are sentto the coordinator to combine them withmerge.

This process requires no secret information (assuming the partialsignatures do not leak any key material), nor the contents of the messageitself, so it can be done by an untrusted machine or by any number ofmachines in public to produce the valid RSA signature on the message.

Since the messages are deterministicly padded with PKCS#1 v1.5,it is possible for the merge operation to detect that invalidpartial signatures have been provided, but not to determine whichparty sent the invalid file.

openssl dgst -verify key.pub -signature file.sig < file

Verify the merged signature with the public key. The value thatis actually signed is an PKCS#1-v1.5 encoded structure defined inRFC 3447 section 9.2.

openssl rsautl -verify -pubin -inkey key.pub -asn1parse -in file

Produce an ASN1 tree of the signed file for debugging ifthe verification fails for some reason.

cosign requires a trusted dealer to perform the key split.The dealer can keep a copy of the whole private key or leak itto one of the conspiring parties.

cosign does not have a general threshold system. 2-of-3 is implementedsince it only requires two signature operations; beyond that thecombinatorial complexity is quite high. This requires doing two signatureoperations for each signature and then selecting the correct of these fora pairwise combination that produces a valid signature. Larger N-of-Kschemes are possible in the literature but this is was an easy approach.

The private key is recoverable if all of the shards are combined (ortwo of the three threshold keys). This is a good thing if it isdesirable to be able to re-shard the key. If the shards are stored ina hardware token, it might be difficult to recover the shard in a formatthat would allow recombination.

The security properties of the partial signatures is not known.The randomd_i values do not meet the coprime conditions, for instance.

Unfortunately the partial private keys are not compatible with hardwaretokens like Yubikeys since the key shards do not have theChinese Remainder Theorem (CRT)values, nor the primesp &q and thedp &dq values, that thehardware tokens use to perform efficient RSA operations. The thresholdkeys especially are not suitable for hardware since they use non-standardrepresentation.

• Why RSA?

The main reason is that it is widely used, despite the calls toseriously, fuck RSA.The UEFI SecureBoot infrastructure uses it, so for interoperabilityit is necessary to support it as well as the padding modes that it uses.

• Why 2048 bit keys?

Again interoperability with common devices. Many of the firmwares outthere won't handle RSA 4Kb keys, so sticking with the "reasonable"value of 2048 works for now. It is just a parameter in the Python code,so it could easily be increasedwith a command line argument.

• Why PKCS#1 v1.5 instead of OEAP or RSA-PSS?

The determinism that makes PKCS#1 v1.5 potentially dangerous as apadding oracle is also what enables the offline signing of messageswithout any communication.OAEP andRSA-PSSavoid the oracle attack, but require the signing parties to agreeupon the random salt values before signing. This doesn't work forthe CI or some of the other use cases where the different signers aresupposed to arrive at the same input message without communication.

• What about algorithms to eliminate the Trusted Dealer phase?

Pull requests welcome!Most of the academic papers are difficult to follow and few have providedthe source code behind their algorithms. For many use cases the trusteddealer is unfortunate but not a deal breaker, and it was expedient toimplement.

This is inspired by an replyposted to crypto.stackexchange.com by@ponchoas a "fairly straight-forward method using RSA", which is likely based on Boyd'sadditive secret sharing:

Key generation phase:

The dealer selects a random RSA public/private keypair$(n,e,d)$

The dealer then selects$N$ values$d1,d2,…,dN$ with the constraint that$d1+d2+…+dN≡d(modλ(n))$

The dealer privately sends$d_i$ to party$i$, and publishes the public key$(n,e)$

Signature generation phase:

Each party gets a copy of the value to be signed$S$

Each party$i$ deterministically pads$S$ (perhaps using PKCS #1.5 signature padding,perhaps using PSS using randomness seeded by$S$), and then raises that to the power of$d_i mod n$;that is, it computes$sig_i=Pad(S)^{di} mod n$

Each party sends sigi to a collector, which computes$sig=sig1⋅sig2⋅…⋅s_n mod n$, and broadcasts it

Everyone checks if$sig$ is a valid signature to the value$s$; if not, then a malicious party is detected

There has been lots of other research into multiparty RSA going back toBoyd ("Digital multisignatures" Cryptography and Coding, 1986). Most ofthe algorithm research has focused on threshold RSA and distributedprivate key generation, although none of the literature seems to haveusable implementations.

There are some startups in this space as well, but they are notusing open source software nor publishing their algorithms, so theyare essentially both a trusted dealer and all of the trusted parties.