[Note: My original intention was to publish this as a tutorial. However, I had mixed feelings about publishing it as such, since it had not changed much in RFC. I finally decided to just leave it in meditations.]
Introduction
This tutorial covers (very basically) the concept of Identity Based Encryption (IBE) using Pairings Based Cryptography (PBC). It gives examples of implementing IBE schemes in perl and discusses some of the features and drawbacks of IBE schemes. I am writing this to try to spread the word about how much fun this stuff can be.
IBE allows us to use the identity of a person, computer, NIC, email account, or some other identifier as a public key for encryption and authentication. It is frequently said to be "self-authenticating" since every party in an IBE network can (indeed, must) generate the public key for any other party using their knowledge of the target identity [2].
[This entire post runs as one giant program using the download link.]
Shamir is usually credited as the first person to cook up this whole idea, but the important paper, cited everywhere is Boneh & Franklin: [1]. These technologies have been maturing at a nice pace, but Elliptic Curve Cryptography (ECC), PBC, and IBE are all very young fields and there are a lot of unsolved problems (like what to do with it). An interesting side effect of using ECC/PBC to implement IBE is that you get the same crypto-protection from 160bit keys in ECC that you would from 1024bits of in RSA [3].
Despite how cool IBE sounds at first, it has some major drawbacks. Consider the role of the Certificate Authority in SSL/TLS. You need to get signed before people believe you. That's not so bad. In IBE, it's slightly worse. You have to have a TA (Trusted Authority) that generates all the private keys in the system. And that does mean the TA can decrypt everything in the IBE system! The TA is sometimes called a TTP (Trusted Third Party) or a KGC (Key Generating Center). I tend to despise the term KGC for crypto because of my KGC, but that's a personal problem...
Actually, the TA picks a master-secret s (a value in a cyclic group) that it uses for key generation. It also picks a bi-linear pairing (usually called ê), a generator P (an element in a group that can generate the whole group), and various other things [1]. For example, since your identity never expires, it's typical to see researchers put other things in there with the identity, like version numbers and expiration dates. As described by Hoeper and Gong, that'd be Qi = H1(IDi, expiration, version) [2]. H1() is a function that maps real life values into the pairing, so Qi just describes a point (or points) on a curve.
Diffie-Hellman[-Merkle]
Many other documents cover DH in much more detail than I intend to here. Please visit the Wikipedia page on the subject of Diffie-Hellman for the full skinny. Basically, the idea is that the two sides negotiate to form a secret that they never transmit over the untrusted network.
How does DH relate to IBE? It doesn't, but I'm in no position to explain the inner workings of ECC or PBC, so instead I'm going to compare it to DH. ECC and PBC math is based on Group Theory and other abstract algebra. It is a bit over my head. DH serves as an example though, because in the PBC model of IBE, PBC serves the role of a harder version of the computational Diffie-Hellman problem [1].
Since this site is all about code, I won't bother explaining the protocol in English. Here's a by-hand implementation to read. It does not differ greatly from Crypt::DH except that the following isn't directly usable. Also, I'm very serious about this, don't use rand() for crypto.
#!/usr/bin/perl use strict; use warnings; use Math::BigInt lib => 'GMP'; my $g = new Math::BigInt('5'); # typically 2 or 5 my $p = new Math::BigInt( "537139360602477525125655043677356597740" . "672426915294213641576278281056255413159" . "9074907426010737503501" # any 100+ digit prime will do ); my $a = new Math::BigInt(join("", map(chr(48+int rand 10), 1 .. 50))); # $a is the lhs secret my $b = new Math::BigInt(join("", map(chr(48+int rand 10), 1 .. 50))); # $b is the rhs secret my ($A, $B, $Kab, $Kba); print "g=$g\n"; # $p and $g generate a group print "p=$p\n"; # cyclic group G print "a=$a\n"; # $p and $g are chosen in the clear print "b=$b\n"; print "\n"; # it's safe to send A=g^a mod p in the clear $A = $g->copy->bmodpow( $a, $p ); # it's safe to send B=g^b mod p in the clear $B = $g->copy->bmodpow( $b, $p ); # g^b^a mod p should be equal to g^a^b mod p $Kba = $B->copy->bmodpow( $a, $p ); $Kab = $A->copy->bmodpow( $b, $p ); # so we both know the secret without transmitting it! # magic! print "These better be equal:\n\t$Kab\n\t$Kba\n\n";
The reason I included the above is to convey just how simple these crypto systems really are. They sound massively complex — and the math certainly can be for PBC — but mostly they just depend on math problems that are really hard to do backwards (the discrete log problem in this case).
The reason you can calculate the secret so fast in DH is because they're in a cyclic group (which also makes them hard to solve). Rather than calculating $a ** $p and $b ** $p and then taking the modulo, you take the modulo at each iteration of the pow() loop. bmodpow() is a special super-fast GMP call for that very purpose.
The PBC Library @ Stanford
Sadly, GMP can't handle the esoteric matrix operations required to do parings calculations on a curve. Fortunately for us, Ben Lynn started up this project: http://crypto.stanford.edu/pbc/. It is a generic PBC library, so it is capable of a lot more than just IBE, which is only one of many areas where PBC can be used. I have ported libpbc to perl in the form of Crypt::PBC, which is part of the reason I'm writing this document. Since PBC and IBE are very young, it isn't always clear how to approach the problem. There are various ways to do things and no general agreement on The One True Way.Let's get started. First, we'll select a pairing. There are a staggering number of choices — in fact, they may be infinite for all I know. They're divided into broad categories (by Lynn at least and possibly others): a, a1, d, e and f. They represent different types of curves and are documented reasonably well in the libpbc manual.
Since, I think this stuff is too young to actually be used by anyone that can't double check the math on their own (i.e., not me), I tend to just use one of the example pairing parameter files that comes with the libpbc distribution. I'd guess Lynn usually chooses d-type pairings, since he provides a big .zip file full of choices on the libpbc website, but I tend to use a-type pairings since they're symmetric (meaning G1 and G2 elements can be interchanged because they are "algebraically similar").
Hrm, I should back up a little. In our DH example above, we had one cyclic group generated by $g and $p. In PBC we'll have elements in G1, G2, Gt and Zr — all are cyclic groups having something to do with the bi-linear pairing we selected in the parameters file. I'm happy to say we do not need to care overmuch what they represent, but if you are curious there are many works on the subject — choose google and have fun.
Setup
Anyway, let's select a curve. I have included an a-type pairing, a d-type pairing and an e-type pairing in the Crypt::PBC module distribution, but it doesn't install them anywhere; so, you'll have to snag them from your .cpan/build/Crypt-PBC dir (they're the *.txt files). While we're at it, let's also build our Trusted Authority values. Again, the TA is the master-secret holder and the entity that builds all the secrets in the system.
use Crypt::PBC; my $pairing = new Crypt::PBC("params_d.txt"); my $P = $pairing->init_G2->random; # generator in G2 my $s = $pairing->init_Zr->random; # master secret my $P_pub = $pairing->init_G2->pow_zn($P, $s); # master public key
Hey, that wasn't so hard! Note that in [1] the public key is listed as sP. In group theory what looks like multiplication really refers to some operation, not necessarily multiplication. In these IBE examples we'll mostly use pow_zn() and e_hat() to mix the elements. From now on, I will be referring to pow_zn($P, $s) as $s$P.
Next, let's build a public key for an identity. Note that any node in the network will have $pairing, $P, $P_pub, and params_d.txt. The only thing that's secret is $s. Suppose my identity is jettero, which I'll encode as node=16186 and then map to an element in G1:
use Digest::SHA1 qw(sha1); my $ID_i = q(node_id=16186); my $Q_i = $pairing->init_G1->set_to_hash( sha1($ID_i) ); print "ID_i=$ID_i\nQ_i=", $Q_i->as_hex, "\n";
According to Lynn, it's pretty meaningless to try to pass more than around 160 bits to set_to_hash(). Happily, sha1() returns precisely 160 bits. Note that all nodes have their own $pairing and all nodes generate $Q_i on their own. The only keys and secrets transmitted (or negotiated) are the private keys. The node identified by $ID_i has to ask the TA for their private key $s$Q_i which is generated like this:
my $d_i = $pairing->init_G1->pow_zn( $Q_i, $s ); # the private key cor +responding to $Q_i
There exist various strategies for transmitting the private key over open networks. I might have chosen SSL/TLS or Crypt::DH to exchange the secret had Hoper and Gong not referred to a "blinding technique" [2] they cite in [4]. It can instead be elegantly achieved (as in [4]) fairly easily, but we'll come back to the secure distribution of $d_i in a bit. We have a few more things to go over first.
Encrypt/Decrypt
What do you do with $d_i and $Q_i to encrypt and decrypt things? According to [1], there are a few properties we can use. First, we construct $g_i = ê( $Q_i, $P_pub ) in G2, a random number $r in Zr, and calculate $r$P. We then use $r$g_i as a shared secret that $ID_i can recover with $r$g_i = ê( $d_i, $r$P ).
use Crypt::CBC; use Crypt::Blowfish; my $g_i = $pairing->init_GT->e_hat( $Q_i, $P_pub ); my $r = $pairing->init_Zr->random; my $rP = $pairing->init_G2->pow_zn( $P, $r ); my $W1 = $g_i->clone->pow_zn( $r ); my $C1 = new Crypt::CBC({header=>'randomiv', key=>$W1->as_bytes, ciphe +r=>"Blowfish"}); my @m = ($rP, $C1->encrypt("LOL! Funny URL: blither blather message" +)); # Note that the message is a two tuple, not just the ciphertext. # We transmit @m in the clear. No worries. my $W2 = $pairing->init_GT->e_hat( $d_i, $m[0] ); my $C2 = new Crypt::CBC({header=>"randomiv", key=>$W2->as_bytes, ciph +er=>"Blowfish"}); my $txt = $C2->decrypt( $m[1] ); print "W1 =? W2\nW1=", substr($W1->as_base64, 0, 80), "\nW2=", substr( +$W2->as_base64, 0, 80), "\n"; print "And here's the original message: $txt\n\n";
There are a few interesting things going on here. First, notice that the encryption is symmetric — both sides have the secret. The sender could even be coerced into decrypting the message unless she carefully throws away the secret $W1 and the random nonce $r after all encrypt/decrypt operations are complete. Second, this communication is repudiable (i.e., the sender can claim they never sent it). And third, the receiver has no way to know who this message came from, meaning it is un-authenticated.
Authenticated Encrypt/Decrypt
Most applications I'm familiar with will have fewer uses for un-authenticated (but secure) channels than for authentic ones. It is a good thing then, that every node in the IBE system can compute a non-negotiated self-authenticating shared secret that they can use as a key for a symmetric cipher or as a secret in a MAC (message authenticating code). That secret is $K_ij = ê( $d_i, $Q_j ) = ê( $Q_i, $d_j ) [5]-[6].
Before we can get started though, we'll have to select a new pairing. It's required that e_hat() be called in this fashion: GT = e_hat(G1, G2). In the d-type pairing we selected above (an asymmetric one), G1 is represented as a 1x2 ([GMP, GMP]); G2 by a 2x3 ([[GMP, GMP, GMP], [GMP, GMP, GMP]]). e_hat() will take (G2, G1), but only if the arguments are "algebraically similar." If we switch to an a-type paring, then G1 and G2 are both represented by a 1x2. You can make identical elements for $Q_i in G1 and in G2 and make identical elements for $d_i in G1 and in G2 just so you can swap the argument order in e_hat(), but I find that it's simpler to just make a symmetric pairing. Lastly, you can't reliably mix elements from different pairings. It might work here and there (as a quirk of memory management accidents), but I'm reasonably certain it will cause trouble eventually.
$pairing = new Crypt::PBC("params_a.txt"); $P = $pairing->init_G2->random; # generator in G2 $s = $pairing->init_Zr->random; # master secret $P_pub = $pairing->init_G2->pow_zn($P, $s); # master public key my $Q_0 = $pairing->init_G1->set_to_hash( sha1("node_id=22609") ); # +tye my $Q_1 = $pairing->init_G1->set_to_hash( sha1("node_id=9073") ); # +merlyn my $d_0 = $pairing->init_G1->pow_zn( $Q_0, $s ); my $d_1 = $pairing->init_G1->pow_zn( $Q_1, $s ); my $K_01_a = $pairing->init_GT->e_hat( $Q_0, $d_1 ); # merlyn's versio +n of K_01 my $K_01_b = $pairing->init_GT->e_hat( $d_0, $Q_1 ); # tye's version print "K_01 (these better be the same):\n\t", substr($K_01_a->as_base6 +4, 0, 80), "\n\t", substr($K_01_b->as_base64, 0, 80), "\n"; my $K_10_a = $pairing->init_GT->e_hat( $Q_1, $d_0 ); # tye's version o +f K_10 my $K_10_b = $pairing->init_GT->e_hat( $d_1, $Q_0 ); # merlyn's versio +n print "K_10 (these also better be the same):\n\t", substr($K_10_a->as_ +base64, 0, 80), "\n\t", substr($K_10_b->as_base64, 0, 80), "\n\n";
In my experience, $K_10 is always the same as $K_01, but I have never seen a proof of that in a paper — at least that I understood was proof of it. In fact, the proof may be obvious by inspection to people familiar with Abstract Algebra and Group Theory! In any case, I tend to treat $K_10 and $K_01 as if they were different and choose to select the node with the lowest ASCII sort $ID for the left hand $Q. $ID_0 sorts before $ID_1 in the example above, so I would use $K_01.
The features of the $K_ij secret are fascinating. First, no negotiation is required [2]. Tye and Merlyn can each calculate that secret on their own. That could be really helpful for networks where low network load is really important — like wireless nodes with very limited battery supplies [7]. Compare this with Crypt::DH, where the sender and receiver have to exchange several messages to build their shared secret. The only thing Tye and Merlyn can't calculate on their own is their private key (distribution of which is the very next section). Second, the secret and any messages ciphered with it are pre-authenticated. Only the two nodes involved can make that secret — not counting the TA, which can calculate all secrets.
We can use the secrets in one of two ways:
# We can construct authenticated ciphers: my $authcipha = new Crypt::CBC({header=>"randomiv", key=>$K_01_a->as +_bytes, cipher=>"Blowfish"}); my $authciphb = new Crypt::CBC({header=>"randomiv", key=>$K_01_b->as +_bytes, cipher=>"Blowfish"}); # or we can use the secrets to construct authentic clear-text messag +es: my @verifiable_message; SCOPE1: { my $msg = "This is verifiable."; my $sha = new Digest::SHA1; $sha->add( $msg ); $sha->add( $K_01_a->as_bytes ); my $MAC = $sha->digest; @verifiable_message = ( $msg, $MAC ); } SCOPE2: { my $sha = new Digest::SHA1; $sha->add( $verifiable_message[0] ); $sha->add( $K_01_b->as_bytes ); my $MAC = $sha->digest; print "Verified message from ID_0: $verifiable_message[0]\n\n" if $MAC eq $verifiable_message[1]; }
One thing we can't do (if we're $ID_1) is prove to a third party that $ID_0 produced the message. The verifiable message is therefore said to be repudiable, which just means you can take back what you said if someone tries to hold it against you. There are schemes to sign messages (e.g., BLS Signatures), but they're not covered here.
Secure Key Distribution
Since $d_i can be used to decrypt anything intended for $ID_i, we need a scheme to get the key from the TA to $ID_i in a secure fashion. We can use more equations with ê() to solve this problem. First, we need a random nonce $x_i in Zr with which we calculate $X_i = $x_i$P [Note: Xx differ only by height in my browser]. Next, we send $X_i to the TA along with our request for $d_i. We can now rely on the fact that ê($s$X_i, $P_pub) = ê($P_pub, $P_pub)$x to calculate a shared secret with which we can construct an authentic secure channel [4].
my $ID_c = 'node_id=1382'; # chromatic is looking to join our IBE my $Q_c = $pairing->init_G1->set_to_hash( sha1($ID_c) ); my $x_c = $pairing->init_Zr->random; my $X_c = $pairing->init_G2->pow_zn( $P, $x_c ); my $req = $X_c->as_bytes; # we transmit $X_c in the open along with our request for $d_c # the TA then builds our private key and constructs a secret $W_0. # IRL, the TA would calculate $Q_c on its own ... my $dtmp = $pairing->init_G1->pow_zn( $Q_c, $s ); my $W_0 = $pairing->init_GT->e_hat( $pairing->init_G2->set_to_bytes($req)->pow_zn( $s ), # only the +TA can make this $P_pub ); my $cipher0 = new Crypt::CBC({header=>"randomiv", cipher=>"Blowfish" +, key=>$W_0->as_bytes}); my $reqfil = $cipher0->encrypt( $dtmp->as_bytes ); # Back at the $ID_c node, we can recover our private key # from $reqfil like so: my $W_1 = $pairing->init_GT->e_hat( $P_pub, $P_pub )->pow_zn($x_ +c); my $cipher1 = new Crypt::CBC({header=>"randomiv", cipher=>"Blowfish" +, key=>$W_1->as_bytes}); my $d_c = $pairing->init_G1->set_to_bytes( $cipher1->decrypt( $r +eqfil ) ); print "I have aquired my key from the TA over a secure authentic cha +nnel:\n\t", substr($dtmp->as_base64, 0, 80), "\n\t", substr($d_c->as_base64, 0, 80), "\n\n";
Master-Secret Sharing
The same paper that talks about secure key distribution ([4]) talks about master-secret sharing to protect privacy. In fact, in the paper, the two concepts are completely tied together. It should be reasonable clear how to recombine them, so I'll keep this example as simple as possible.
Their idea is that there's an inherent "key escrow" problem in IBE. They see the same problem I do: that the TA can decrypt everything. So they consider the idea of having privacy partners that keep the master-secret safe. The idea is that as long as at least one of the Privacy Authority (PA) entities is honest, the others cannot maliciously build any of the private keys ($d_i)in the system.
The biggest difference here is that instead of using a single secret $s, we have a list of secrets @s — one for each PA (plus the TA). The public key is called $Y, rather than $P_pub, and it combines all the secrets together: $Y = $s0$s1$s2 ... $sn$P. Of course, none of the PAs will want to hand their $s[$i] over to their neighbor. They instead pass $s[$i]$P[$i-1] to their next-in-line. Next-in-line? Yes. Order matters building $Y and $d_i!
# $P is chosen the same way as the examples above, so we'll just use t +hat. my $N = 10; # the number of PAs, plus the TA my @s = map( $pairing->init_Zr->random, 1 .. $N ); my @P = map( $P->clone->pow_zn( $_ ), @s ); my $Y = $P->clone; $Y->pow_zn( $_ ) for @s; # The TA calculates P0 := $s[0]$P and transmits to the first PA who # calculates P1 := $s[1]$P[0] and so on. Notice the in-efficiency? # Hint: $P[0] == ($P->clone->pow_zn($s[0])). In fact, @P isn't needed # at all, unless you're combining shared-secrets with secure key # distribution. # $Q_0 (tye) and $Q_1 (merlyn) are defined above ... $d_0 = $Q_0->clone; $d_0->pow_zn( $_ ) for @s; $d_1 = $Q_1->clone; $d_1->pow_zn( $_ ) for @s; $K_01_a = $pairing->init_GT->e_hat( $Q_0, $d_1 ); $K_01_b = $pairing->init_GT->e_hat( $d_0, $Q_1 ); print "[Y] authenticated secret is the same:\n\t", substr($K_01_a->as_ +base64, 0, 80), "\n\t", substr($K_01_b->as_base64, 0, 80), "\n\n"; $r = $pairing->init_Zr->random; $rP = $P->clone->pow_zn( $r ); $W1 = $pairing->init_GT->e_hat( $Q_0, $Y )->pow_zn( $r ); $W2 = $pairing->init_GT->e_hat( $d_0, $rP ); print "[Y] un-authenticated secret is the same:\n\t", substr($W1->as_b +ase64, 0, 80), "\n\t", substr($W2->as_base64, 0, 80), "\n\n";
Some Closing Thoughts
Please consider that this document is exceedingly myopic in it's coverage of Pairings Based Cryptography — in that it only covers Identity-Based Encryption and not very thoroughly at that. Some content that I considered including was omitted to help keep the article focused. For example, every scheme above is repudiable, since I did not cover signature schemes at all. If this article is well received, I may write a second article on PBC and try to cover more PBC and IBE concepts.
Although I love IBE and I hope it really takes hold somewhere ... eventually. I hope it never pops up in email systems. It seems like a natural fit at first glace, but compare it to GnuPG/OpenPGP and it seems to be lacking a few things. Having no central authority is certainly a feature I'm not willing to live without. The addition of the Privacy Authorities helps a little, but use your imagination: What if the privacy authorities were The Whitehouse, the FBI, Verisign, and Microsoft? Do you feel secure that they won't try to read your mail?
That said, it does seem like it'd be a good fit at work, where the TA could be your mail administrator and your PAs could be a couple of Industry Vice Admirals or some HR managers or something. It is probably appropriate under most circumstances that your employer should be able to read your email — well, work emails anyway.
My primary goal in writing this is the hope that a genius or a lucky person might read it and come up with the most clever use of all ... whatever that is ...
-Paul
- D. Boneh and M. Franlink. "Identity-Based Encryption from the Weil Pairing," Advances in Cryptology - CRYPTO '2001, LNCS 2139, pp. 213-229, 2001.
- K. Hoeper and G. Gong, "Bootstrapping Security in Mobile Ad Hoc Networks Using Identity-Based Schemes with Key Revocation," Department of Electrical and Computer Engineering, University of Waterloo, 1/25 2006.
- Y. Hu, Q. Li, and J. Kuo, "Efficient Implementation of Elliptic Curve Cryptography (ECC) on VLIW-Micro-Architecture Media Processor," Multimedia and Expo, 2004. ICME '04. 2004 IEEE International Conference on, pp 879-882 Vol. 2, 2004
- B. Lee, C. Boyd, E. Dawson, K. Kim, J. Yang, and S. Yoo, "Secure Key Issuing in ID-Based Cryptography," CRPIT '04: Proceedings of the second workshop on Australasian information security, Data Mining and Web Intelligence, and Software Internationalisation, Australian Computer Society, Inc., 2004, pp. 69-74.
- B. Lynn, "Authenticated identity-based encryption," Cryptology ePrint Archive, Report 2002/072, 2002.
- R. Sakai, K. Ohgishi, and M. Kasahara, "Cryptosystems Based on Pairings," The 2000 Sympo- sium on Cryptography and Information Security, 2000.
- A. Khalili, J. Katz, and W.A. Arbaugh, "Toward Secure Key Distribution in Truly Ad-Hoc Networks," Proceedings of the 2003 Symposium on Applications and the Internet Workshops (SAINT'03 Workshops), IEEE Computer Society, pp. 342-346, 2003.