Introduction
What is SDP1?
SDP1 is a protocol that permits cryptographically secured datagrams to be passed between two cooperating parties. Each datagram is secured within a context that establishes shared secrets for encryption and MACs.
What Doco is there?
More information is found in the SDP1 defining document.
How does it work?
In a nutshell, SDP1 uses the previously established context to acquire a secret key, an IV, a MAC secret, and a token identifying the other end. The payload is padded and then encrypted with the secret key and the IV. This ciphertext is then concatonated with the token, and then the both are MACed. The datagram is formed of the token, the ciphertext and the MAC.
The receiving end uses the token to find its copy of the context. It checks the MAC, then uses its copies of the shared secrets to decrypt the payload.
Status
The protocol itself is in draft, and is not fixed. There is only one implementation, and it is not as yet deployed. Until implementations are deployed and therefore need to be relied upon, SDP1 remains changeable.
In practice, work continues apace on deployment without waiting for stability of SDP1, as current implemented code works well. In practice, changes would only happen if bugs were found or it was convenient to tune; a future SDP2 is the place to fix any dramatic changes.
How Does SDP1 Work?
The Doc
For most answers in this section, you are best served by reading the defining document, Secure Datagram Protocol #1.
How does the datagram layout?
On the wire, the datagram is the concatonation of three elements: the token, the ciphertext, and the MAC.
What is the token for?
The token identifies the end-point. Each receiver can maintain a list of tokens, that point to contexts. Within each context are the shared secrets that are needed to decrypt the datagram.
Most practical applications require multiple connections or contexts. For this reason, we added the token as the first element.
What is the context for?
The context is the operating environment of the Secure Datagram Protocol. The SDP1 context primarily requires these parameters for the algorithms: MAC secrets, the bulk encryption keys and IVs for each end-point, in both the read and the write directions.
How Does Secret Sharing Work?
Intro to secret sharing
All protocols use a secret key algorithm such as AES to encrypt the data. (These algorothims are also known as symmetric ciphers, because the work the same both ways.) A secret key algorithm is generally very strong, in fact these alorithms are the strongest we know. They are also very fast, and relatively easy to code and to use.
But a secret key algorithm requires a secret key to drive it! This secret key represents a bit of a difficulty: how do we share the secret? We cannot use the algorithm to share the secret key, because we have no key as yet; hence this is a bootstrapping problem.
All protocols share secrets. Most traditional approaches try and bootstrap public key infrastructures ("PKI") of some form and use a public key algorithm to encrypt the secret to the public key of the recipient.
Problems with secret sharing
There are several problems with the traditional PKI approach. The major one is simply that the users have to have public and private keys. In some sense this makes sharing easier, as users can simply share the public keys, with impunity from security. But in other senses, this introduces a whole host of management problems.
In practice, frequently the use of a PKI adds such burdens that it stops the deployment in its tracks. The canonical case of this is web service. This page you are reading right now is not encrypted, and the reason is very simple: the PKI adds such costs to the deployment of a public key that the WebFunds project simply can't afford to protect the privacy and integrity of these pages.
Yet, these costs are only driven by the choices of the architects of the system. If you were to view these pages over a terminal service program, it's almost certain that you would be using SSH, another public key system. In that system, the choices of the architects dictated that the cost of public keys was zero and your pages would almost certainly be protected.
What this amounts to is that secret sharing can either be simple and effective, or difficult, costly and impractical. SDP1 takes the approach that secret sharing is as easy or as complex as you are going to make it; regardless, it is up to you, the user or the architect, to organise how you want to do that.
How then are these secrets shared?
How the secret is shared is beyond the strict domains of the datagram protocol. In effect, it's up to the application to do that. Here are some methods used by extant cryptosystems:
SharedSecretRequest
SOX uses a SharedSecretRequest. The client creates two half contexts, and sends them to the server. The server creates another two half contexts, and returns them. Each context is then made of two halves, where one half comes from each node.
As each Request within SOX is already secured by the strong protection of the SOX protocol, this represents a highly secure key exchange.
SDT's KEX
In SDT - secure datagram tunnel - the Key Exchange agreement takes the basic model above and refines it. Each side creates a packet with some paramaters and a 96byte random lump. These are exchanged.
Then, both sides take 16 bytes from the two random lumps. They feed the two blocks into AES-ECB mode as key and plaintext, ordered according to whether the side is client or server. The resultant ciphertext then becomes the 16 byte key for that section; the conceptual action here is to do a simple hash of the two random values. This is done 6 times, once each for each of 6 keys required (twice key, CIV, Mac secret).
This process fixes some minor weaknesses in the SOX mechanism above.
Password-generated secrets - "Key Derivation Function"
A program takes a password and generates all the necessary keys directly from this using a Key Derivation Function (KDF). This algorithm is a simple key expansion using the fixed keynames, each concatonated with the password and hashed. The method is suitable for starting up two pairs of cooperating servers where an administrator is accessing them both via ssh(1).
The KDF for SDP1 is defined in Secret Sharing Password. The program SSPassword can be used to run the KDF and generate SSContexts.
Ad-hoc
An administrator runs a program on one node to create a context, and it is copied to the two communicating nodes using whatever means are to hand (in practice, SSH). The contexts are placed in files, and recovered on startup.
(This under development, and looks like more trouble than it is worth, as it seems to involve more code than adding a simple key exchange from an initial position.)
Is it SDP or SDP1 ?
SDP1 is designed to be replaced easily by SDP2, SDP3, etc. The context negotiation, or secret sharing process, has to specify that "number one" being SDP1 is the secure datagram protocol to use. When or if SDP2 ever makes an appearance, SDP will be the family of these protocols.
Coding
What implementations exist?
So far, Java, PHP and C. At some stage, we'll probably do Perl as well unless someone beats us to it.
Java
Webfunds has a Java implementation. This is located in the source repository, and is available in under the Download page (look for the source link in the README for the latest source download).
Inside the source, SDP1 is located in the package webfunds.sox.sdp. Also needed will be some elements of the package webfunds.util. Let us know if any other dependencies are found.
PHP
XML/X demo website has a PHP implementation. This is located in the source repository, but is not yet available under the Download page (look for the source link in the README for the latest source download).
Inside the source, SDP1 is located in the directory comms/sdp. Run the standalone self test php -Cq comms/sdp/SDP1Test. Also needed will be some elements of the package util. Let us know if any other dependencies are found.
C
C has an early version here which isn't really part of a proper distro as we don't have any C distros to base it on. It uses either/or HMACs from NSS or OpenSSL; and either/or AES from OpenSSL or the original RBB code.
Licence
XML/X and WebFunds are made available under a Mozilla style licence that requires open availability of any changes made. As an exception to this general licence, and in addition, the SDP1 and util packages are also issued under a much wider range of licence. Specifically, the Cryptix 2 party BSD style licence may be inferred for SDP1 code and for code in packages marked as util.
How to Help!
We probably need implementations in many languages.
The best way to do this would be to either create it from scratch by reading the Secure Datagram Protocol #1 document. This might be a bit slow. A faster way is to grab an existing implementation and port it across. Note however that this won't then have the added advantage of showing that our documents are accurate and our code conforms to the documented protocol.
It took one of the designers 2 days coding to get PHP written and self-tested from scratch. It took 10 days to do C to the same level!
Packet Size
Best Practical UDP Size
When used over UDP, there are many limits that hit in different places. Some are listed in the following section.
The upshot of the limits is that packets might do well to stay at or below 516 bytes in order to avoid fragmentation. If the UDP packet included just an SDP1 packet, then we would need to subtract 21 bytes for the MAC, 2 for the ciphertext length and (say) 7 for a token. Call it 30 for a round number.
Then, inside the ciphertext layer, there is a Pad of 16 to 31 bytes, and another length of 2 bytes. So 33 bytes lost.
Which all leaves us a target of 516 - 30 - 30 or 446 bytes. Notice this is not an accurate figure, but will do as a working rule for open transmission over the network.
For more accurate numbers, one would have to test.
Protocol Limits
The IP version 4 (what we now use) says this: "Each UDP datagram is sent within a single IP datagram. Although, the IP datagram may be fragmented during transmission, the receiving IP implementation will re-assemble it before presenting it to the UDP layer. All IP implementations are required to accept datagrams of 576 bytes, which, allowing for maximum-size IP header of 60 bytes means that a UDP datagram of 516 bytes is acceptable to all implementations. Many implementations will accept larger datagrams, but this is not guaranteed."
IPv6 has a more reasonable limit of around 1500 bytes, as does Ethernet.
Speed
It's fast enough - the biggest delay is how fast the AES and SHA1 HMACs run to. The PHP version runs encrypt / decrypt cycles in about 50ms for an average 8k packet (on an AMD Opteron 64bit machine). Most apps will not notice the delay.
Intellectual Property Issues
Protocol
The SDP1 protocol is open and no regime or rules is imposed. Anyone can use SDP1 for any purpose, commercial or otherwise with no licence or restrictions.
Patents
No patents are applicable to any of the algorithms used. Only AES and SHA1 as formal algorithms are used, and neither of these two have patent concerns nor licensing concerns.
There are no patents being filed nor filable on the basic design. It is well described in the literature and is as old as the hills.
Dox
It would be appreciated if links back to the sources are preserved, authors are credited and if any experiences or changes are made available. But, this is not essential nor required.
Documentation located here is subject to normal principles of academic propriety. Please quote the authors and sources, and feel free to reuse parts of the documentation. Plagiarism is a fairly mild issue compared to the crime of not spreading strong cryptography.
Security
How strong is it?
SDP1 is pretty darn strong. It uses AES which is an algorithm chosen by the United States government for all non-classified cryptography. This effectively means AES becomes the world wide defacto standard for most needs.
Could it be stronger? Are there weaknesses?
Yes. Specific points of interest (weaknesses?) are the smallish 128 bit keys, and the SHA1 hash which is now showing its age.
General
In fact, the competition to design AES reinvigorated the secret key cipher world, and since then there have been many efforts to improve on Rijndael, the algorithm that won (and earnt the new title AES, or advanced encryption standard). Further, the standardisation problem caused a re-thinking in the issue of message authentication codes ("MACs") which is leading to many innovative designs.
Unfortunately, the dust has not yet settled on these efforts. It is simply not clear that any new MAC construction delivers better results, and there is little code out there for any of these new designs. Also, some of the better choices are under cloud of patents, so many users will not be able to use them. Likewise, even though newer ciphers show promise, none of them have been analysed to the same extent as AES.
So in a sense, the choice of AES with a SHA1 HMAC is a conservative choice. But, note that the protocol is designed such that SDP1 is replacable. Expect to see SDP2 roll out in a couple of years.
Choice of AES-128 over AES-256
AES-128 is Pareto-complete. This means that there is no Pareto-secure-improvement that can be made that will deliver a better result, including AES-256. To check this for yourself, try the Key Length Calculator/ and figure out when the "secure until this year" mark is for 128 bit keys. I calculated it as 2088, which is good enough for me!
What about Side-channel Attacks
Dan Bernstein recently announced that a side-channel attack can reveal the key of AES, due to difficulties in creating a constant time implementation. This involves measuring the decryption time of many packets and then doing statistics based on how the key is looked up with different packets.
SDP1 is immune to an injection form of side-channel attack because packets are protected by the HMAC in encrypt-then-authenticate mode. That is, if an attacker were to send packets to time their decryptions, he would also need to HMAC the packets, which implies he already has the full key set. If he doesn't have the HMAC key and instead sends in a garbage packet, it won't ever be decrypted as the HMAC will fail.
SDP1 packets may still be vulnerable to a passive timing attack. If an attacker can watch both the incoming packet and identify the matching reply, then this may give enough information to analyse the decrypt time.
Helping the timing attack is that as the decrypt is done over many blocks, presumably this gives a more accurate time, divided by the number of blocks. Against the timing attack is that the attacker has to factor out the HMAC time, any time spent doing work in order to reply, the time of the reply preparation, and any network delays.
Whether SDP1 becomes subject to this attack then probably depends on the protocol. In Ricardo for example, the number of packets is O(100) and the size is O(100 blocks). The amount of work done with most packets where there is a timing possibility involves one or two public key signatures or verifications and several internal process context switches, so it is unlikely that any measurement of decrypt times is possible.
Choice of SHA-1 over SHA-256
The reason for choosing SHA-1 is that it is widely coded into HMACs. Recent results has indicated that SHA-1 has now been reduced in collision resistance from 80 bits to 69 bits. Whilst a phenomenal result, this does not effect the MAC construction as far as we know, and for that purpose, SHA-1 remains strong.
And, frankly, until the cryptographic community has reviewed the entire message digest field (including whether SHA-256 has vulnerabilities) and the message authentication code field has settled, it is better to settle for what we know.
How much review has SDP1 had?
Almost none. The designers have evolved the protocol through lots of internal discussions, but only one anonymous outsiders has commented (and seen no problems).
SDP1 is designed with known and accepted weaknesses, see above. If any more weaknesses are found, they will be evaluated in the context of the existing weaknesses, and a future design of SDP2 will benefit from the experience. In any event, this is no real reason to hold back from using the protocol, if it fits the needs.
How much data should be encrypted?
Limits of the IV
This is a tricky question. The main weakness is that each successive datagram uses the same context. The practical upshot of weaknesses here is that the software may get stuck creating poor quality initialisation values ("IVs"). If the IV were to be non-unique, for example, it leads to potential trouble.
Calculation of IVs is very difficult to determine outside the application. For this reason, a lot of attention was paid to the design of the IV. It is intended to be strongly unique for each new datagram, drawing on a nonce, the time, and random data in order to achieve that.
The cryptosystem was designed for an application that uses no more than 1000 datagrams from the same context. This was judged to be acceptable. Other security situations will vary.
Limits of the Context
An additional concern is that the Context, which generates the IV, is effectively a shared secret. So as time goes on, there is an increased danger of compromise of the Context through attacks outside the protocol. Therefore it is wise to plan roll-overs from time to time.
That's an issue for each application to address. One application negotiates a context for every session, and only when the application is restarted, and the in-memory copy of the context is lost, is the context re-negotiated. Another application does a manual key exchange and only re-negotiates when the system administrator does the work. Clearly, that's a vulnerability, but that's the choice of the system administrator.
I'm unsure whether it is secure enough. What do I do?
Unless you have a really serious threat, don't worry about it. Use whatever seems easiest. If indeed you are one of the lucky few on this planet to ever experience a breach in a cryptosystem, then this breach will tell you where to improve your efforts. In the meantime you will have gained from countless protected sessions.
Never hold back from using a cryptosystem because it might have some theoretical weakness: remember that for a weakness to be exploited, there has to be an attacker that wants to exploit it. Almost all attackers are too lazy or too busy.
In general, the only threats where you want to take really serious care about your cryptosystem are where you life is in danger or you are facing pervasive attempts by national governments that can deploy real assets against the cryptosystem. The most common cases of this would be insurgents, freedom fighters, reporters and international compliance workers. For these people, take a bit more care.
For almost all other cases: financial data, personal data, chat, instant messaging, email, credit card purchase, and protection of corporate data, remember this: an attack will almost always go around the cryptosystem. By far the best thing you can do is to put in place any crypto system you can lay your hands on, and then think about how to go around it.
What should I worry about?
In practice, the only specific thing to pay attention to is the IV. SDP1 uses a novel construction to merge a count, the time, and random data into a Pad which forms the real IV of the cipher.
This construction is designed to deliver a unique IV under adverse conditions. If you have a good count as a nonce, and a strong time base, with a good feed of random data, then you have little to worry about.
If however your random numbers generator is spitting out all zeros, your clock has stopped, and your count keeps getting reset on each datagram, then you no longer have an IV worth diddly squat. But, if that's your world, you will already know this.
Most situations will come out of the box with all three of these factors well and truley under control. And, the protocol is designed to keep going even if one or even two of the factors are out of wack.
Why does the Pad use so many inputs?
Because we find it so hard to get them right! Consider you've decided to rely on your TPM's RNG. Here's what Peter Gutmann, the cryptoplumber's cryptoplumber says:
You have to be pretty careful here. Most of the TPM chips are just rebadged smart cards, and the RNGs on those are often rather dubious. A standard technique is to repeatedly encrypt some stored seed with an onboard block cipher (e.g. DES) as your "RNG". Beyond the obvious attacks (DES as a PRNG isn't particularly strong) there are the usual paranoia concerns (how do we know the manufacturer doesn't keep a log of the seed and key?) and stupidity concerns (all devices use the same hardwired key, which some manufacturers have done in the past). There are also active attacks possible, e.g. request values from the device until the EEPROM locks up, after which you get constant "random" values. Finally, some devices have badly-designed challenge-response protocols that give you an infinite amount of RNG output to analyse, as well as helping cycle the RNG to lockup.
So the only hardware RNG I'd trust is one of the noise-based ones on full- scale crypto processors like the Broadcom or HiFn devices, or the Via x86's. There are some smart-card vendors who've tried to replicate this type of generator in a card form-factor device, but from what little technical info is available about generators on smart cards it seems to be mostly smoke and mirrors.
(As an extension of this, the lack of access to a TPM's RNG isn't really any great loss. If it's there, you can mix it opportunistically into your own RNG, but I wouldn't rely on it).
So, we provide 3 methods, and hope you are lucky enough to get two working.
My Random numbers are a bit sloppy, what do I do?
Use what random numbers you have easily available. Make sure that you use really good random numbers in the calculation of the context. And, keep a close eye on the count and timebase that the context uses to seed the Pad.
SDP1 itself is designed to work without good random numbers. On the other hand, the context creation almost certainly requires good random numbers, and as the IV is predictable to some extent, a non-random context will result in a relatively easy attack. That is, if you use your password for the context, then an optomised password checker could do an easy dictionary attack as the first decryption would lead to a matchable IV.
This is the tradeoff: context creation is a rare, expensive event. There, we put in the best randomness we can, even if it takes time to collect the entropy. In the calculation of each datagram, we just aim for uniqueness in the IV.
What about traffic analysis?
This is one area which was ruled out of the requirements for SDP1. Traffic analysis was not a goal. Having said that, there are more or less some things to consider.
In order to analyse SDP1 traffic, it is relatively easy to identify and track context-related packets, because the token is sent in cleartext at the beginning of the packet. Further, some extant versions include a leading byte 0x5d to signal that an SDP1 packet follows.
So it is possible to build up a map of who is talking to which nodes according to the crypto context, as established by the secret key negotiation (see above). FWIW, a defender could create multiple contexts and switch around them, or could layer all traffic over one context.
The length of the packet is a good indicator of what the data contains, in terms of higher layer protocols. That is, a request for a payment will be X bytes whereas a request for a key exchange will be Y bytes.
In the SDP1 packet, it is possible to fudge this a little by increasing short packet sizes. This is done by increasing the size of the Pad. It is defined to be at least 16 bytes, and generally no more than 31. But, receiving implementations should handle longer Pads. As this is just random data, it serves no useful purpose, but may be used to hide a short packet.
This should be done with care, though, as fiddling around at this level may introduce unexpected consequences. You should check this out with an experienced cryptoengineer.
Some notes on this area are published in this rant: Indistinguishable from Random. Note that these are musings into the far future, collected more for the purpose of saving them so that when and if we get around to doing it all again, we have the wisdom collected.
Wider Issues
Aren't datagrams a bit hokey?
Not all tasks are connection-oriented. Most in fact are not, but for the convenience of avoiding all the communications code that is needed, it is often thought to be easier to simply use a connection and not worry about the details.
For example, HTTP is not connection-oriented, as a task. A request goes out, a page comes back. This makes it a connectionless task, which just so happens to be conveniently layered over a connection. By further example, protecting financial data is almost always a datagram task, as most important data is sent in discrete lumps that need to be treated as such.
Shouldn't everyone use SSL?
Not really. SSL or TLS is a very complete connection-oriented protocol. It is suitable for connection oriented tasks such as terminal service (and in fact SSH2 uses much the same design internally).
The use of SSL presents three issues: Firstly, the costs of incorporating the very expensive certificate structure. Practically speaking, for most cases, SSL can be used cheaply by deployment of self-signed certificates, which gets around these costs to some extent, but most code bases and servers simply aren't set up to bootstrap with them.
Secondly, SSL is overkill for a lot of tasks. SSL code is quite large and involves a lot of complexity. This is balanced by the availability of a lot of experience in its use, the number of toolkits available, and also a decade of scrutiny of the protocol (three rewrites!). However, none of this helps much if a developer needs to move quickly to deploy a security architecture.
Thirdly, the use of SSL implies the use of connections which bring in hidden dangers when datagrams should be used.
For example, on many web sites you will see a little warning that says "do not press the button twice" right where you are about to purchase that very expensive white elephant. This is a classic indication that we are dealing with a datagram task, and the software has not been adequately written to deal with making the datagrams move properly over the net.
In many such cases, the designers of such systems have thought that using SSL would secure their data, and prevent any data from being misordered or otherwise manipulated. Not so, as SSL only protects the data on the wire, and the threats are almost always concentrated off the wire. (In the above case, not only are they caught out by users pressing the button twice, but they are caught out by software that conspires to re-deliver the connection in its entirety if a failure is indicated.)
Why doesn't everyone do this?
It is a highly controversial approach.
The 1990s saw a school of cryptography emerge that championed no-risk cryptography, an approach to securing data with no weaknesses. Unfortunately this led to the arisal of PKIs which involve quite significant costs. Worse, using PKIs does not guaruntee any improvement in security, because mostly what they do is shift the burden to a bunch of companies that we know little about and are asked to trust on face value. I.e., no-risk was only achieved by assuming away the risks, not by removing them.
In response to the failure of wide-spread deployment of no-risk cryptography, an alternate approach of opportunistic cryptography emerged, championed by a competing system called SSH. In this system, instead of shifting the burden of security to some external party, the risk was kept in-house, and dealt with on a best-efforts basis. This works because for the most part, there is usually a good relationship on which to build with between the parties.
It is actually very rare in commerce and social affairs to find a need to secure a communication between two parties that have no prior relationship. Opportunistic cryptography simply searches for that prior relationship and bootstraps the security from that.
The difference is and was dramatic. In comparing like for like, SSH dominated and crushed all competing software systems within its problem space (including the SSL variant). Now, SSH is the only way in which terminal communications are served in any serious installation. In contrast, SSL is estimated to secure less than 1% of the web traffic (measured by server certificate statistics). No matter what one thinks of the security models employed, the market data is very clear: SSH secures almost every thing in its grasp, whereas SSL secures almost nothing.
Won't firewalls stop any datagrams?
Yes. This is the one good reason to use connections. But, even in this case, if your task is datagram oriented, and your packets really matter, then you should design the architecture to be datagram oriented.
In which case, what you should do is layer your datagrams over a TCP/IP connection, and over HTTP. That is, in order to send a packet, open a connection, send HTTP headers, then the SDP1 datagram. This will go through firewalls.
But, it is very important to understand that what you are doing is a datagram task layered over a HTTP "tunnel." Firewalls require hacks to get through, and such is life.
Miscellaneous
Random Links (WIP)
In the fullness of time, these should be incorporated as full references, or disappear.
NIST's Pages on Modes and Proposed AES Modes
Dave Wagner's " Why people should use CTR mode" white paper for the NIST Modes of Operation project.
Bellare, Rogaway - 2000 Encode-then-encipher encryption: How to exploit nonces or redundancy in plaintexts for efficient cryptography
Bryce 'Zooko' Wilcox-O'Hearn, Introduction to the EGTP version 2 Architecture, The Mnet Project.
Phil Rogaway's OCB is a new and interesting algorithm, but is too expensive.
The Key Length Calculator/ which codes up the formulas in Arjen K. Lenstra and Eric R. Verheul, Selecting Cryptographic Key Sizes. Journal of Cryptology, 14(4):255-293, August 2001. Also see DOC slides.