# Micro Digital Signatures Howto

Posted February 22nd, 2011 by rybolovWith RSA wrapping up, I figured I would do something fun with Alice, Bob, and crypto. There is a need for small digital signatures (Micro Digital Signatures/”MicroDigiSigs” if I can be as bold as to think I can start a nerdy meme) and tools to support them over small message spaces such as The Twitters, SMS/Text Messaging, barcodes, jabber/xmpp, and probably tons of other things I haven’t even thought of.

Elliptic Curve Cryptography (ECC) provides a solution because of some inherent traits in the algorithms:

- Speed to compute
- Low processor load
- Small keys
- Small signatures

Some general-type info to know before we go further with this:

- OpenSSL 1.00 supports ECC functions. This is teh awesome, thank you OpenSSL peoples.
- You can check out the OpenSSL HOWTO, I derived a ton of info from this resource http://www.madboa.com/geek/openssl/
- Issues with ECC support in OpenSSL:
- ECC is poorly documented in OpenSSL. Pls fix kthanx.
- Some targets are missing from OpenSSL (ECC Digital Signature Algorithm signatures with SHA-256).

Now on to the step-by-step process. Feel free to shoot holes in this, I’m sure there are tons of other ways to do things.

**Show all the available curves:**

rybolov@ryzhe:~$ openssl ecparam -list_curves

secp112r1 : SECG/WTLS curve over a 112 bit prime field

secp112r2 : SECG curve over a 112 bit prime field

secp128r1 : SECG curve over a 128 bit prime field

secp128r2 : SECG curve over a 128 bit prime field

secp160k1 : SECG curve over a 160 bit prime field

secp160r1 : SECG curve over a 160 bit prime field

secp160r2 : SECG/WTLS curve over a 160 bit prime field

secp192k1 : SECG curve over a 192 bit prime field

secp224k1 : SECG curve over a 224 bit prime field

secp224r1 : NIST/SECG curve over a 224 bit prime field

secp256k1 : SECG curve over a 256 bit prime field

secp384r1 : NIST/SECG curve over a 384 bit prime field

secp521r1 : NIST/SECG curve over a 521 bit prime field

prime192v1: NIST/X9.62/SECG curve over a 192 bit prime field

prime192v2: X9.62 curve over a 192 bit prime field

prime192v3: X9.62 curve over a 192 bit prime field

prime239v1: X9.62 curve over a 239 bit prime field

prime239v2: X9.62 curve over a 239 bit prime field

prime239v3: X9.62 curve over a 239 bit prime field

prime256v1: X9.62/SECG curve over a 256 bit prime field

sect113r1 : SECG curve over a 113 bit binary field

sect113r2 : SECG curve over a 113 bit binary field

sect131r1 : SECG/WTLS curve over a 131 bit binary field

sect131r2 : SECG curve over a 131 bit binary field

sect163k1 : NIST/SECG/WTLS curve over a 163 bit binary field

sect163r1 : SECG curve over a 163 bit binary field

sect163r2 : NIST/SECG curve over a 163 bit binary field

sect193r1 : SECG curve over a 193 bit binary field

sect193r2 : SECG curve over a 193 bit binary field

sect233k1 : NIST/SECG/WTLS curve over a 233 bit binary field

sect233r1 : NIST/SECG/WTLS curve over a 233 bit binary field

sect239k1 : SECG curve over a 239 bit binary field

sect283k1 : NIST/SECG curve over a 283 bit binary field

sect283r1 : NIST/SECG curve over a 283 bit binary field

sect409k1 : NIST/SECG curve over a 409 bit binary field

sect409r1 : NIST/SECG curve over a 409 bit binary field

sect571k1 : NIST/SECG curve over a 571 bit binary field

sect571r1 : NIST/SECG curve over a 571 bit binary field

c2pnb163v1: X9.62 curve over a 163 bit binary field

c2pnb163v2: X9.62 curve over a 163 bit binary field

c2pnb163v3: X9.62 curve over a 163 bit binary field

c2pnb176v1: X9.62 curve over a 176 bit binary field

c2tnb191v1: X9.62 curve over a 191 bit binary field

c2tnb191v2: X9.62 curve over a 191 bit binary field

c2tnb191v3: X9.62 curve over a 191 bit binary field

c2pnb208w1: X9.62 curve over a 208 bit binary field

c2tnb239v1: X9.62 curve over a 239 bit binary field

c2tnb239v2: X9.62 curve over a 239 bit binary field

c2tnb239v3: X9.62 curve over a 239 bit binary field

c2pnb272w1: X9.62 curve over a 272 bit binary field

c2pnb304w1: X9.62 curve over a 304 bit binary field

c2tnb359v1: X9.62 curve over a 359 bit binary field

c2pnb368w1: X9.62 curve over a 368 bit binary field

c2tnb431r1: X9.62 curve over a 431 bit binary field

wap-wsg-idm-ecid-wtls1: WTLS curve over a 113 bit binary field

wap-wsg-idm-ecid-wtls3: NIST/SECG/WTLS curve over a 163 bit binary field

wap-wsg-idm-ecid-wtls4: SECG curve over a 113 bit binary field

wap-wsg-idm-ecid-wtls5: X9.62 curve over a 163 bit binary field

wap-wsg-idm-ecid-wtls6: SECG/WTLS curve over a 112 bit prime field

wap-wsg-idm-ecid-wtls7: SECG/WTLS curve over a 160 bit prime field

wap-wsg-idm-ecid-wtls8: WTLS curve over a 112 bit prime field

wap-wsg-idm-ecid-wtls9: WTLS curve over a 160 bit prime field

wap-wsg-idm-ecid-wtls10: NIST/SECG/WTLS curve over a 233 bit binary field

wap-wsg-idm-ecid-wtls11: NIST/SECG/WTLS curve over a 233 bit binary field

wap-wsg-idm-ecid-wtls12: WTLS curvs over a 224 bit prime field

Oakley-EC2N-3:

IPSec/IKE/Oakley curve #3 over a 155 bit binary field.

Not suitable for ECDSA.

Questionable extension field!

Oakley-EC2N-4:

IPSec/IKE/Oakley curve #4 over a 185 bit binary field.

Not suitable for ECDSA.

Questionable extension field!

**ECC keys are specific to curves. Make a key for secp256k1, it’s fairly standard (ie, specified in NIST’s DSA Signature Standard (DSS) as are all of the secp* curves).**

rybolov@ryzhe:~$ openssl ecparam -out key.test.pem -name prime256v1 -genkey

rybolov@ryzhe:~$ cat key.test.pem

—–BEGIN EC PARAMETERS—–

BggqhkjOPQMBBw==

—–END EC PARAMETERS—–

—–BEGIN EC PRIVATE KEY—–

MHcCAQEEIGkhtOzaKTpxETF9VNQc7Nu7SMX5/klNvObBbJo/riKsoAoGCCqGSM49

AwEHoUQDQgAEXmD6Hz/c8rxVYe1klFTUVOxxKwT4nLRcOLREQnC5GL+qNayqx7d0

Q+yal6sVSk013EbJr9Ukw/aiQzbrlcU1VA==

—–END EC PRIVATE KEY—–

**Make a public key. This is poorly documented and I had to extrapolate from the RSA key generation process.**

rybolov@ryzhe:~$ openssl ec -in key.test.pem -pubout -out key.test.pub

read EC key

writing EC key

rybolov@ryzhe:~$ cat key.test.pub

—–BEGIN PUBLIC KEY—–

MFkwEwYHKoZIzj0CAQYIKoZIzj0DAQcDQgAEXmD6Hz/c8rxVYe1klFTUVOxxKwT4

nLRcOLREQnC5GL+qNayqx7d0Q+yal6sVSk013EbJr9Ukw/aiQzbrlcU1VA==

—–END PUBLIC KEY—–

**Make a test message:**

rybolov@ryzhe:~$ echo “destroy all monsters” > msg.test

rybolov@ryzhe:~$ cat msg.test

destroy all monsters

**Generate MD5, SHA-1, and SHA-256 hashes:**

rybolov@ryzhe:~$ openssl dgst -md5 msg.test

MD5(msg.test)= a4a5e7ccfda28fdeb43697b6e619ed45

rybolov@ryzhe:~a$ openssl dgst -sha1 msg.test

SHA1(msg.test)= 4d1d1b917377448a66b94e1060e3a4c467bae01c

rybolov@ryzhe:~$ openssl dgst -sha256 msg.test

SHA256(msg.test)= efd54922696e25c7fed4023b116882d38cd1f0e4dcc35e38548eae9947aedd23

**Make a signature, note that every time you make a signature with ECC it will be different.**

rybolov@ryzhe:~$ cat msg.test | openssl dgst -sha1 -sign key.test.pem -out test.sha1.sig

rybolov@ryzhe:~$ cat msg.test | openssl dgst -sha1 -sign key.test.pem

0E!ÔøΩÔøΩÔøΩEÔøΩ-y

ÔøΩÔøΩ1K2ÔøΩÔøΩ›§{!ÔøΩv4+ÔøΩÔøΩÔøΩÔøΩ WÔøΩ ÔøΩcÔøΩÔøΩP≈ô—áÔøΩaÔøΩ*~)@aÔøΩ1ÔøΩJ>ÔøΩdÔøΩ

**Make the signature readable/text by encoding it with Base64:**

rybolov@ryzhe:~$ openssl enc -base64 -in test.sha1.sig

MEUCIGbR7ftdgICMZCGefKfd6waMvOM23DJo3S0adTvNH5tYAiEAuJ6Qumt83ZsL

sxDqJ1JNH7XzUl28M/eYf52ocMZgyrk=

rybolov@ryzhe:~$ wc -m test.sha1.sig.asc

98

rybolov@ryzhe:~$ openssl enc -base64 -in test.sha1.sig > test.sha1.sig.asc

**Validate the signature:**

rybolov@ryzhe:~$ openssl dgst -sha1 -verify key.test.pub -signature test.sha1.sig msg.test

Verified OK

**OpenSSL is dumb here because it can’t read base64:**

rybolov@ryzhe:~$ openssl dgst -sha1 -verify key.test.pub -signature test.sha1.sig.asc msg.test

Error Verifying Data

3077905144:error:0D0680A8:asn1 encoding routines:ASN1_CHECK_TLEN:wrong tag:tasn_dec.c:1320:

3077905144:error:0D07803A:asn1 encoding routines:ASN1_ITEM_EX_D2I:nested asn1 error:tasn_dec.c:382:Type=ECDSA_SIG

**So we can use OpenSSL encode with the -d flag to make a binary version:**

rybolov@ryzhe:~$ openssl enc -base64 -d -in test.sha1.sig.asc -out test.sha1.sig.bin

rybolov@ryzhe:~$ cat test.sha1.sig.

test.sha1.sig.asc test.sha1.sig.bin

rybolov@ryzhe:~$ cat test.sha1.sig.bin

0E fÔøΩÔøΩÔøΩ]ÔøΩÔøΩÔøΩd!ÔøΩ|ÔøΩÔøΩÔøΩÔøΩÔøΩÔøΩ6ÔøΩ2hÔøΩ-u;ÔøΩÔøΩX!ÔøΩÔøΩÔøΩÔøΩk|›õ

ÔøΩÔøΩ’RMÔøΩÔøΩR]ÔøΩ3ÔøΩÔøΩÔøΩÔøΩpÔøΩ` π

rybolov@ryzhe:~$ openssl dgst -sha1 -verify key.test.pub -signature test.sha1.sig.bin msg.test

Verified OK

**We can also do a prverify which is to verify the signature using the private key:**

rybolov@ryzhe:~$ openssl dgst -sha1 -prverify key.test.pem -signature test.sha1.sig.bin msg.test

Verified OK

**Now to use this whole thing, you’ll need concatenate the signature with the massage and add a delimiter or send 2 messages, one with the message, the other with the signature. Any kind of special character like |!^% etc works great as a delimeter, so something like this works:**

MEUCIGbR7ftdgICMZCGefKfd6waMvOM23DJo3S0adTvNH5tYAiEAuJ6Qumt83ZsLsxDqJ1JNH7XzUl28M/eYf52ocMZgyrk=destroy all monsters

destroy all monsters|MEUCIGbR7ftdgICMZCGefKfd6waMvOM23DJo3S0adTvNH5tYAiEAuJ6Qumt83ZsLsxDqJ1JNH7XzUl28M/eYf52ocMZgyrk=

**Topics for further research:**

I haven’t talked at all about key distribution. This gets real hard real fast just for the simple fact that you have to get an initial key to both ends of the conversation. You can do key rotation inband, but that first hookup is a logistical effort. Glad to hear ideas on this.

To get a smaller signature, use MD5 and secp112r1. Normally you wouldn’t create digital signatures using MD5 (US Government standard is moving to SHA-256), but it’s a tradeoff in paranoia/crackability with signature size. You have to do each of the steps manually because the objects for ECDSA only use SHA-1:

- Hash the command
- Encrypt the hash using the private key
- Convert the encrypted hash to base64

You can use the OpenSSL shell prompt to save some keystrokes: openssl<enter> You can also call OpenSSL as a C library, which should work nicely for embedded code.

I’m interested in building a comparison table of the following items, I just haven’t had time to build a script to compare all the data for me:

- ECC Curve
- Time to Compute a Signature
- Size of Signature
- Relative key and signature strength

Similar Posts:

Posted in Hack the Planet, NIST, Technical, What Works **|** 3 Comments »

Tags: alice • bob • crypto • cryptography • ECC • infosec • OpenSSL • security • signatures

February 22nd, 2011 at 5:01 pm

Better yet, stick the signature as the target of a shortened uri which is embedded into the signed micromessage.

February 25th, 2011 at 12:23 am

[…] This post was mentioned on Twitter by rybolov, novainfosec. novainfosec said: #NOVABLOGGER: Micro Digital Signatures Howto http://bit.ly/egxste http://j.mp/nispblog […]

February 28th, 2011 at 11:40 am

[…] Micro Digital Signatures Howto | The Guerilla CISO […]