|
3
|
1 \documentclass[b5paper]{book} |
|
|
2 \usepackage{hyperref} |
|
|
3 \usepackage{makeidx} |
|
|
4 \usepackage{amssymb} |
|
|
5 \usepackage{color} |
|
|
6 \usepackage{alltt} |
|
|
7 \usepackage{graphicx} |
|
|
8 \usepackage{layout} |
|
|
9 \def\union{\cup} |
|
|
10 \def\intersect{\cap} |
|
|
11 \def\getsrandom{\stackrel{\rm R}{\gets}} |
|
|
12 \def\cross{\times} |
|
|
13 \def\cat{\hspace{0.5em} \| \hspace{0.5em}} |
|
|
14 \def\catn{$\|$} |
|
|
15 \def\divides{\hspace{0.3em} | \hspace{0.3em}} |
|
|
16 \def\nequiv{\not\equiv} |
|
|
17 \def\approx{\raisebox{0.2ex}{\mbox{\small $\sim$}}} |
|
|
18 \def\lcm{{\rm lcm}} |
|
|
19 \def\gcd{{\rm gcd}} |
|
|
20 \def\log{{\rm log}} |
|
|
21 \def\ord{{\rm ord}} |
|
|
22 \def\abs{{\mathit abs}} |
|
|
23 \def\rep{{\mathit rep}} |
|
|
24 \def\mod{{\mathit\ mod\ }} |
|
|
25 \renewcommand{\pmod}[1]{\ ({\rm mod\ }{#1})} |
|
|
26 \newcommand{\floor}[1]{\left\lfloor{#1}\right\rfloor} |
|
|
27 \newcommand{\ceil}[1]{\left\lceil{#1}\right\rceil} |
|
|
28 \def\Or{{\rm\ or\ }} |
|
|
29 \def\And{{\rm\ and\ }} |
|
|
30 \def\iff{\hspace{1em}\Longleftrightarrow\hspace{1em}} |
|
|
31 \def\implies{\Rightarrow} |
|
|
32 \def\undefined{{\rm ``undefined"}} |
|
|
33 \def\Proof{\vspace{1ex}\noindent {\bf Proof:}\hspace{1em}} |
|
|
34 \let\oldphi\phi |
|
|
35 \def\phi{\varphi} |
|
|
36 \def\Pr{{\rm Pr}} |
|
|
37 \newcommand{\str}[1]{{\mathbf{#1}}} |
|
|
38 \def\F{{\mathbb F}} |
|
|
39 \def\N{{\mathbb N}} |
|
|
40 \def\Z{{\mathbb Z}} |
|
|
41 \def\R{{\mathbb R}} |
|
|
42 \def\C{{\mathbb C}} |
|
|
43 \def\Q{{\mathbb Q}} |
|
|
44 |
|
|
45 \def\twiddle{\raisebox{0.3ex}{\mbox{\tiny $\sim$}}} |
|
|
46 |
|
|
47 \def\gap{\vspace{0.5ex}} |
|
|
48 \makeindex |
|
|
49 \begin{document} |
|
|
50 \title{A Tiny Crypto Library, \\ LibTomCrypt \\ Version 0.95} |
|
|
51 \author{Tom St Denis \\ |
|
|
52 \\ |
|
|
53 [email protected] \\ |
|
|
54 http://libtomcrypt.org \\ \\ |
|
|
55 Phone: 1-613-836-3160\\ |
|
|
56 111 Banning Rd \\ |
|
|
57 Kanata, Ontario \\ |
|
|
58 K2L 1C3 \\ |
|
|
59 Canada |
|
|
60 } |
|
|
61 \maketitle |
|
|
62 This text and source code library are both hereby placed in the public domain. This book has been |
|
|
63 formatted for B5 [176x250] paper using the \LaTeX{} {\em book} macro package. |
|
|
64 |
|
|
65 \vspace{10cm} |
|
|
66 |
|
|
67 \begin{flushright}Open Source. Open Academia. Open Minds. |
|
|
68 |
|
|
69 \mbox{ } |
|
|
70 |
|
|
71 Tom St Denis, |
|
|
72 |
|
|
73 Ontario, Canada |
|
|
74 \end{flushright} |
|
|
75 \newpage |
|
|
76 \tableofcontents |
|
|
77 \chapter{Introduction} |
|
|
78 \section{What is the LibTomCrypt?} |
|
|
79 LibTomCrypt is a portable ANSI C cryptographic library that supports symmetric ciphers, one-way hashes, |
|
|
80 pseudo-random number generators, public key cryptography (via RSA,DH or ECC/DH) and a plethora of support |
|
|
81 routines. It is designed to compile out of the box with the GNU C Compiler (GCC) version 2.95.3 (and higher) |
|
|
82 and with MSVC version 6 in win32. |
|
|
83 |
|
|
84 The library has been successfully tested on quite a few other platforms ranging from the ARM7TDMI in a |
|
|
85 Gameboy Advanced to various PowerPC processors and even the MIPS processor in the PlayStation 2. Suffice it |
|
|
86 to say the code is portable. |
|
|
87 |
|
|
88 The library is designed so new ciphers/hashes/PRNGs can be added at runtime and the existing API (and helper API functions) will |
|
|
89 be able to use the new designs automatically. There exist self-check functions for each cipher and hash to ensure that |
|
|
90 they compile and execute to the published design specifications. The library also performs extensive parameter error checking |
|
|
91 and will give verbose error messages when possible. |
|
|
92 |
|
|
93 Essentially the library saves the time of having to implement the ciphers, hashes, prngs yourself. Typically implementing |
|
|
94 useful cryptography is an error prone business which means anything that can save considerable time and effort is a good |
|
|
95 thing. |
|
|
96 |
|
|
97 \subsection{What the library IS for?} |
|
|
98 |
|
|
99 The library typically serves as a basis for other protocols and message formats. For example, it should be possible to |
|
|
100 take the RSA routines out of this library, apply the appropriate message padding and get PKCS compliant RSA routines. |
|
|
101 Similarly SSL protocols could be formed on top of the low-level symmetric cipher functions. The goal of this package is |
|
|
102 to provide these low level core functions in a robust and easy to use fashion. |
|
|
103 |
|
|
104 The library also serves well as a toolkit for applications where they don't need to be OpenPGP, PKCS, etc. compliant. |
|
|
105 Included are fully operational public key routines for encryption, decryption, signature generation and verification. |
|
|
106 These routines are fully portable but are not conformant to any known set of standards. They are all based on established |
|
|
107 number theory and cryptography. |
|
|
108 |
|
|
109 \subsection{What the library IS NOT for?} |
|
|
110 |
|
|
111 The library is not designed to be in anyway an implementation of the SSL or OpenPGP standards. The library |
|
|
112 is not designed to be compliant with any known form of API or programming hierarchy. It is not a port of any other |
|
|
113 library and it is not platform specific (like the MS CSP). So if you're looking to drop in some buzzword |
|
|
114 compliant crypto library this is not for you. The library has been written from scratch to provide basic functions as |
|
|
115 well as non-standard higher level functions. |
|
|
116 |
|
|
117 This is not to say that the library is a ``homebrew'' project. All of the symmetric ciphers and one-way hash functions |
|
|
118 conform to published test vectors. The public key functions are derived from publicly available material and the majority |
|
|
119 of the code has been reviewed by a growing community of developers. |
|
|
120 |
|
|
121 \subsubsection{Why not?} |
|
|
122 You may be asking why I didn't choose to go all out and support standards like P1363, PKCS and the whole lot. The reason |
|
|
123 is quite simple too much money gets in the way. When I tried to access the P1363 draft documents and was denied (it |
|
|
124 requires a password) I realized that they're just a business anyways. See what happens is a company will sit down and |
|
|
125 invent a ``standard''. Then they try to sell it to as many people as they can. All of a sudden this ``standard'' is |
|
|
126 everywhere. Then the standard is updated every so often to keep people dependent. Then you become RSA. If people are |
|
|
127 supposed to support these standards they had better make them more accessible. |
|
|
128 |
|
|
129 \section{Why did I write it?} |
|
|
130 You may be wondering, ``Tom, why did you write a crypto library. I already have one.''. Well the reason falls into |
|
|
131 two categories: |
|
|
132 \begin{enumerate} |
|
|
133 \item I am too lazy to figure out someone else's API. I'd rather invent my own simpler API and use that. |
|
|
134 \item It was (still is) good coding practice. |
|
|
135 \end{enumerate} |
|
|
136 |
|
|
137 The idea is that I am not striving to replace OpenSSL or Crypto++ or Cryptlib or etc. I'm trying to write my |
|
|
138 {\bf own} crypto library and hopefully along the way others will appreciate the work. |
|
|
139 |
|
|
140 With this library all core functions (ciphers, hashes, prngs) have the {\bf exact} same prototype definition. They all load |
|
|
141 and store data in a format independent of the platform. This means if you encrypt with Blowfish on a PPC it should decrypt |
|
|
142 on an x86 with zero problems. The consistent API also means that if you learn how to use blowfish with my library you |
|
|
143 know how to use Safer+ or RC6 or Serpent or ... as well. With all of the core functions there are central descriptor tables |
|
|
144 that can be used to make a program automatically pick between ciphers, hashes and PRNGs at runtime. That means your |
|
|
145 application can support all ciphers/hashes/prngs without changing the source code. |
|
|
146 |
|
|
147 \subsection{Modular} |
|
|
148 The LibTomCrypt package has also been written to be very modular. The block ciphers, one-way hashes and |
|
|
149 pseudo-random number generators (PRNG) are all used within the API through ``descriptor'' tables which |
|
|
150 are essentially structures with pointers to functions. While you can still call particular functions |
|
|
151 directly (\textit{e.g. sha256\_process()}) this descriptor interface allows the developer to customize their |
|
|
152 usage of the library. |
|
|
153 |
|
|
154 For example, consider a hardware platform with a specialized RNG device. Obviously one would like to tap |
|
|
155 that for the PRNG needs within the library (\textit{e.g. making a RSA key}). All the developer has todo |
|
|
156 is write a descriptor and the few support routines required for the device. After that the rest of the |
|
|
157 API can make use of it without change. Similiarly imagine a few years down the road when AES2 (\textit{or whatever they call it}) is |
|
|
158 invented. It can be added to the library and used within applications with zero modifications to the |
|
|
159 end applications provided they are written properly. |
|
|
160 |
|
|
161 This flexibility within the library means it can be used with any combination of primitive algorithms and |
|
|
162 unlike libraries like OpenSSL is not tied to direct routines. For instance, in OpenSSL there are CBC block |
|
|
163 mode routines for every single cipher. That means every time you add or remove a cipher from the library |
|
|
164 you have to update the associated support code as well. In LibTomCrypt the associated code (\textit{chaining modes in this case}) |
|
|
165 are not directly tied to the ciphers. That is a new cipher can be added to the library by simply providing |
|
|
166 the key setup, ECB decrypt and encrypt and test vector routines. After that all five chaining mode routines |
|
|
167 can make use of the cipher right away. |
|
|
168 |
|
|
169 |
|
|
170 \section{License} |
|
|
171 |
|
|
172 All of the source code except for the following files have been written by the author or donated to the project |
|
|
173 under a public domain license: |
|
|
174 |
|
|
175 \begin{enumerate} |
|
|
176 \item rc2.c |
|
|
177 \item safer.c |
|
|
178 \end{enumerate} |
|
|
179 |
|
|
180 `mpi.c'' was originally written by Michael Fromberger ([email protected]) but has since been replaced with my LibTomMath |
|
|
181 library. |
|
|
182 |
|
|
183 ``rc2.c'' is based on publicly available code that is not attributed to a person from the given source. ``safer.c'' |
|
|
184 was written by Richard De Moliner ([email protected]) and is public domain. |
|
|
185 |
|
|
186 The project is hereby released as public domain. |
|
|
187 |
|
|
188 \section{Patent Disclosure} |
|
|
189 |
|
|
190 The author (Tom St Denis) is not a patent lawyer so this section is not to be treated as legal advice. To the best |
|
|
191 of the authors knowledge the only patent related issues within the library are the RC5 and RC6 symmetric block ciphers. |
|
|
192 They can be removed from a build by simply commenting out the two appropriate lines in the makefile script. The rest |
|
|
193 of the ciphers and hashes are patent free or under patents that have since expired. |
|
|
194 |
|
|
195 The RC2 and RC4 symmetric ciphers are not under patents but are under trademark regulations. This means you can use |
|
|
196 the ciphers you just can't advertise that you are doing so. |
|
|
197 |
|
|
198 \section{Building the library} |
|
|
199 |
|
|
200 To build the library on a GCC equipped platform simply type ``make'' at your command prompt. It will build the library |
|
|
201 file ``libtomcrypt.a''. |
|
|
202 |
|
|
203 To install the library copy all of the ``.h'' files into your ``\#include'' path and the single libtomcrypt.a file into |
|
|
204 your library path. |
|
|
205 |
|
|
206 With MSVC you can build the library with ``nmake -f makefile.msvc''. This will produce a ``tomcrypt.lib'' file which |
|
|
207 is the core library. Copy the header files into your MSVC include path and the library in the lib path (typically |
|
|
208 under where VC98 is installed). |
|
|
209 |
|
|
210 \section{Building against the library} |
|
|
211 |
|
|
212 In the recent versions the build steps have changed. The build options are now stored in ``mycrypt\_custom.h'' and |
|
|
213 no longer in the makefile. If you change a build option in that file you must re-build the library from clean to |
|
|
214 ensure the build is intact. The perl script ``config.pl'' will help setup the custom header and a custom makefile |
|
|
215 if you want one (the provided ``makefile'' will work with custom configs). |
|
|
216 |
|
|
217 \section{Thanks} |
|
|
218 I would like to give thanks to the following people (in no particular order) for helping me develop this project: |
|
|
219 \begin{enumerate} |
|
|
220 \item Richard van de Laarschot |
|
|
221 \item Richard Heathfield |
|
|
222 \item Ajay K. Agrawal |
|
|
223 \item Brian Gladman |
|
|
224 \item Svante Seleborg |
|
|
225 \item Clay Culver |
|
|
226 \item Jason Klapste |
|
|
227 \item Dobes Vandermeer |
|
|
228 \item Daniel Richards |
|
|
229 \item Wayne Scott |
|
|
230 \item Andrew Tyler |
|
|
231 \item Sky Schulz |
|
|
232 \item Christopher Imes |
|
|
233 \end{enumerate} |
|
|
234 |
|
|
235 \chapter{The Application Programming Interface (API)} |
|
|
236 \section{Introduction} |
|
|
237 \index{CRYPT\_ERROR} \index{CRYPT\_OK} |
|
|
238 |
|
|
239 In general the API is very simple to memorize and use. Most of the functions return either {\bf void} or {\bf int}. Functions |
|
|
240 that return {\bf int} will return {\bf CRYPT\_OK} if the function was successful or one of the many error codes |
|
|
241 if it failed. Certain functions that return int will return $-1$ to indicate an error. These functions will be explicitly |
|
|
242 commented upon. When a function does return a CRYPT error code it can be translated into a string with |
|
|
243 |
|
|
244 \begin{verbatim} |
|
|
245 const char *error_to_string(int errno); |
|
|
246 \end{verbatim} |
|
|
247 |
|
|
248 An example of handling an error is: |
|
|
249 \begin{verbatim} |
|
|
250 void somefunc(void) |
|
|
251 { |
|
|
252 int errno; |
|
|
253 |
|
|
254 /* call a cryptographic function */ |
|
|
255 if ((errno = some_crypto_function(...)) != CRYPT_OK) { |
|
|
256 printf("A crypto error occured, %s\n", error_to_string(errno)); |
|
|
257 /* perform error handling */ |
|
|
258 } |
|
|
259 /* continue on if no error occured */ |
|
|
260 } |
|
|
261 \end{verbatim} |
|
|
262 |
|
|
263 There is no initialization routine for the library and for the most part the code is thread safe. The only thread |
|
|
264 related issue is if you use the same symmetric cipher, hash or public key state data in multiple threads. Normally |
|
|
265 that is not an issue. |
|
|
266 |
|
|
267 To include the prototypes for ``LibTomCrypt.a'' into your own program simply include ``mycrypt.h'' like so: |
|
|
268 \begin{verbatim} |
|
|
269 #include <mycrypt.h> |
|
|
270 int main(void) { |
|
|
271 return 0; |
|
|
272 } |
|
|
273 \end{verbatim} |
|
|
274 |
|
|
275 The header file ``mycrypt.h'' also includes ``stdio.h'', ``string.h'', ``stdlib.h'', ``time.h'', ``ctype.h'' and ``mpi.h'' |
|
|
276 (the bignum library routines). |
|
|
277 |
|
|
278 \section{Macros} |
|
|
279 |
|
|
280 There are a few helper macros to make the coding process a bit easier. The first set are related to loading and storing |
|
|
281 32/64-bit words in little/big endian format. The macros are: |
|
|
282 |
|
|
283 \index{STORE32L} \index{STORE64L} \index{LOAD32L} \index{LOAD64L} |
|
|
284 \index{STORE32H} \index{STORE64H} \index{LOAD32H} \index{LOAD64H} \index{BSWAP} |
|
|
285 \begin{small} |
|
|
286 \begin{center} |
|
|
287 \begin{tabular}{|c|c|c|} |
|
|
288 \hline STORE32L(x, y) & {\bf unsigned long} x, {\bf unsigned char} *y & $x \to y[0 \ldots 3]$ \\ |
|
|
289 \hline STORE64L(x, y) & {\bf unsigned long long} x, {\bf unsigned char} *y & $x \to y[0 \ldots 7]$ \\ |
|
|
290 \hline LOAD32L(x, y) & {\bf unsigned long} x, {\bf unsigned char} *y & $y[0 \ldots 3] \to x$ \\ |
|
|
291 \hline LOAD64L(x, y) & {\bf unsigned long long} x, {\bf unsigned char} *y & $y[0 \ldots 7] \to x$ \\ |
|
|
292 \hline STORE32H(x, y) & {\bf unsigned long} x, {\bf unsigned char} *y & $x \to y[3 \ldots 0]$ \\ |
|
|
293 \hline STORE64H(x, y) & {\bf unsigned long long} x, {\bf unsigned char} *y & $x \to y[7 \ldots 0]$ \\ |
|
|
294 \hline LOAD32H(x, y) & {\bf unsigned long} x, {\bf unsigned char} *y & $y[3 \ldots 0] \to x$ \\ |
|
|
295 \hline LOAD64H(x, y) & {\bf unsigned long long} x, {\bf unsigned char} *y & $y[7 \ldots 0] \to x$ \\ |
|
|
296 \hline BSWAP(x) & {\bf unsigned long} x & Swaps the byte order of x. \\ |
|
|
297 \hline |
|
|
298 \end{tabular} |
|
|
299 \end{center} |
|
|
300 \end{small} |
|
|
301 |
|
|
302 There are 32-bit cyclic rotations as well: |
|
|
303 \index{ROL} \index{ROR} |
|
|
304 \begin{center} |
|
|
305 \begin{tabular}{|c|c|c|} |
|
|
306 \hline ROL(x, y) & {\bf unsigned long} x, {\bf unsigned long} y & $x << y$ \\ |
|
|
307 \hline ROR(x, y) & {\bf unsigned long} x, {\bf unsigned long} y & $x >> y$ \\ |
|
|
308 \hline |
|
|
309 \end{tabular} |
|
|
310 \end{center} |
|
|
311 |
|
|
312 \section{Functions with Variable Length Output} |
|
|
313 Certain functions such as (for example) ``rsa\_export()'' give an output that is variable length. To prevent buffer overflows you |
|
|
314 must pass it the length of the buffer\footnote{Extensive error checking is not in place but it will be in future releases so it is a good idea to follow through with these guidelines.} where |
|
|
315 the output will be stored. For example: |
|
|
316 \begin{small} |
|
|
317 \begin{verbatim} |
|
|
318 #include <mycrypt.h> |
|
|
319 int main(void) { |
|
|
320 rsa_key key; |
|
|
321 unsigned char buffer[1024]; |
|
|
322 unsigned long x; |
|
|
323 int errno; |
|
|
324 |
|
|
325 /* ... Make up the RSA key somehow */ |
|
|
326 |
|
|
327 /* lets export the key, set x to the size of the output buffer */ |
|
|
328 x = sizeof(buffer); |
|
|
329 if ((errno = rsa_export(buffer, &x, PK_PUBLIC, &key)) != CRYPT_OK) { |
|
|
330 printf("Export error: %s\n", error_to_string(errno)); |
|
|
331 return -1; |
|
|
332 } |
|
|
333 |
|
|
334 /* if rsa_export() was successful then x will have the size of the output */ |
|
|
335 printf("RSA exported key takes %d bytes\n", x); |
|
|
336 |
|
|
337 /* ... do something with the buffer */ |
|
|
338 |
|
|
339 return 0; |
|
|
340 } |
|
|
341 \end{verbatim} |
|
|
342 \end{small} |
|
|
343 In the above example if the size of the RSA public key was more than 1024 bytes this function would not store anything in |
|
|
344 either ``buffer'' or ``x'' and simply return an error code. If the function suceeds it stores the length of the output |
|
|
345 back into ``x'' so that the calling application will know how many bytes used. |
|
|
346 |
|
|
347 \section{Functions that need a PRNG} |
|
|
348 Certain functions such as ``rsa\_make\_key()'' require a PRNG. These functions do not setup the PRNG themselves so it is |
|
|
349 the responsibility of the calling function to initialize the PRNG before calling them. |
|
|
350 |
|
|
351 \section{Functions that use Arrays of Octets} |
|
|
352 Most functions require inputs that are arrays of the data type ``unsigned char''. Whether it is a symmetric key, IV |
|
|
353 for a chaining mode or public key packet it is assumed that regardless of the actual size of ``unsigned char'' only the |
|
|
354 lower eight bits contain data. For example, if you want to pass a 256 bit key to a symmetric ciphers setup routine |
|
|
355 you must pass it in (a pointer to) an array of 32 ``unsigned char'' variables. Certain routines |
|
|
356 (such as SAFER+) take special care to work properly on platforms where an ``unsigned char'' is not eight bits. |
|
|
357 |
|
|
358 For the purposes of this library the term ``byte'' will refer to an octet or eight bit word. Typically an array of |
|
|
359 type ``byte'' will be synonymous with an array of type ``unsigned char''. |
|
|
360 |
|
|
361 \chapter{Symmetric Block Ciphers} |
|
|
362 \section{Core Functions} |
|
|
363 |
|
|
364 Libtomcrypt provides several block ciphers all in a plain vanilla ECB block mode. Its important to first note that you |
|
|
365 should never use the ECB modes directly to encrypt data. Instead you should use the ECB functions to make a chaining mode |
|
|
366 or use one of the provided chaining modes. All of the ciphers are written as ECB interfaces since it allows the rest of |
|
|
367 the API to grow in a modular fashion. |
|
|
368 |
|
|
369 All ciphers store their scheduled keys in a single data type called ``symmetric\_key''. This allows all ciphers to |
|
|
370 have the same prototype and store their keys as naturally as possible. All ciphers provide five visible functions which |
|
|
371 are (given that XXX is the name of the cipher): |
|
|
372 \index{Cipher Setup} |
|
|
373 \begin{verbatim} |
|
|
374 int XXX_setup(const unsigned char *key, int keylen, int rounds, |
|
|
375 symmetric_key *skey); |
|
|
376 \end{verbatim} |
|
|
377 |
|
|
378 The XXX\_setup() routine will setup the cipher to be used with a given number of rounds and a given key length (in bytes). |
|
|
379 The number of rounds can be set to zero to use the default, which is generally a good idea. |
|
|
380 |
|
|
381 If the function returns successfully the variable ``skey'' will have a scheduled key stored in it. Its important to note |
|
|
382 that you should only used this scheduled key with the intended cipher. For example, if you call |
|
|
383 ``blowfish\_setup()'' do not pass the scheduled key onto ``rc5\_ecb\_encrypt()''. All setup functions do not allocate |
|
|
384 memory off the heap so when you are done with a key you can simply discard it (e.g. they can be on the stack). |
|
|
385 |
|
|
386 To encrypt or decrypt a block in ECB mode there are these two functions: |
|
|
387 \index{Cipher Encrypt} \index{Cipher Decrypt} |
|
|
388 \begin{verbatim} |
|
|
389 void XXX_ecb_encrypt(const unsigned char *pt, unsigned char *ct, |
|
|
390 symmetric_key *skey); |
|
|
391 |
|
|
392 void XXX_ecb_decrypt(const unsigned char *ct, unsigned char *pt, |
|
|
393 symmetric_key *skey); |
|
|
394 \end{verbatim} |
|
|
395 These two functions will encrypt or decrypt (respectively) a single block of text\footnote{The size of which depends on |
|
|
396 which cipher you are using.} and store the result where you want it. It is possible that the input and output buffer are |
|
|
397 the same buffer. For the encrypt function ``pt''\footnote{pt stands for plaintext.} is the input and ``ct'' is the output. |
|
|
398 For the decryption function its the opposite. To test a particular cipher against test vectors\footnote{As published in their design papers.} call: \index{Cipher Testing} |
|
|
399 \begin{verbatim} |
|
|
400 int XXX_test(void); |
|
|
401 \end{verbatim} |
|
|
402 This function will return {\bf CRYPT\_OK} if the cipher matches the test vectors from the design publication it is |
|
|
403 based upon. Finally for each cipher there is a function which will help find a desired key size: |
|
|
404 \begin{verbatim} |
|
|
405 int XXX_keysize(int *keysize); |
|
|
406 \end{verbatim} |
|
|
407 Essentially it will round the input keysize in ``keysize'' down to the next appropriate key size. This function |
|
|
408 return {\bf CRYPT\_OK} if the key size specified is acceptable. For example: |
|
|
409 \begin{small} |
|
|
410 \begin{verbatim} |
|
|
411 #include <mycrypt.h> |
|
|
412 int main(void) |
|
|
413 { |
|
|
414 int keysize, errno; |
|
|
415 |
|
|
416 /* now given a 20 byte key what keysize does Twofish want to use? */ |
|
|
417 keysize = 20; |
|
|
418 if ((errno = twofish_keysize(&keysize)) != CRYPT_OK) { |
|
|
419 printf("Error getting key size: %s\n", error_to_string(errno)); |
|
|
420 return -1; |
|
|
421 } |
|
|
422 printf("Twofish suggested a key size of %d\n", keysize); |
|
|
423 return 0; |
|
|
424 } |
|
|
425 \end{verbatim} |
|
|
426 \end{small} |
|
|
427 This should indicate a keysize of sixteen bytes is suggested. An example snippet that encodes a block with |
|
|
428 Blowfish in ECB mode is below. |
|
|
429 |
|
|
430 \begin{small} |
|
|
431 \begin{verbatim} |
|
|
432 #include <mycrypt.h> |
|
|
433 int main(void) |
|
|
434 { |
|
|
435 unsigned char pt[8], ct[8], key[8]; |
|
|
436 symmetric_key skey; |
|
|
437 int errno; |
|
|
438 |
|
|
439 /* ... key is loaded appropriately in ``key'' ... */ |
|
|
440 /* ... load a block of plaintext in ``pt'' ... */ |
|
|
441 |
|
|
442 /* schedule the key */ |
|
|
443 if ((errno = blowfish_setup(key, 8, 0, &skey)) != CRYPT_OK) { |
|
|
444 printf("Setup error: %s\n", error_to_string(errno)); |
|
|
445 return -1; |
|
|
446 } |
|
|
447 |
|
|
448 /* encrypt the block */ |
|
|
449 blowfish_ecb_encrypt(pt, ct, &skey); |
|
|
450 |
|
|
451 /* decrypt the block */ |
|
|
452 blowfish_ecb_decrypt(ct, pt, &skey); |
|
|
453 |
|
|
454 return 0; |
|
|
455 } |
|
|
456 \end{verbatim} |
|
|
457 \end{small} |
|
|
458 |
|
|
459 \section{Key Sizes and Number of Rounds} |
|
|
460 \index{Symmetric Keys} |
|
|
461 As a general rule of thumb do not use symmetric keys under 80 bits if you can. Only a few of the ciphers support smaller |
|
|
462 keys (mainly for test vectors anyways). Ideally your application should be making at least 256 bit keys. This is not |
|
|
463 because you're supposed to be paranoid. Its because if your PRNG has a bias of any sort the more bits the better. For |
|
|
464 example, if you have $\mbox{Pr}\left[X = 1\right] = {1 \over 2} \pm \gamma$ where $\vert \gamma \vert > 0$ then the |
|
|
465 total amount of entropy in N bits is $N \cdot -log_2\left ({1 \over 2} + \vert \gamma \vert \right)$. So if $\gamma$ |
|
|
466 were $0.25$ (a severe bias) a 256-bit string would have about 106 bits of entropy whereas a 128-bit string would have |
|
|
467 only 53 bits of entropy. |
|
|
468 |
|
|
469 The number of rounds of most ciphers is not an option you can change. Only RC5 allows you to change the number of |
|
|
470 rounds. By passing zero as the number of rounds all ciphers will use their default number of rounds. Generally the |
|
|
471 ciphers are configured such that the default number of rounds provide adequate security for the given block size. |
|
|
472 |
|
|
473 \section{The Cipher Descriptors} |
|
|
474 \index{Cipher Descriptor} |
|
|
475 To facilitate automatic routines an array of cipher descriptors is provided in the array ``cipher\_descriptor''. An element |
|
|
476 of this array has the following format: |
|
|
477 |
|
|
478 \begin{verbatim} |
|
|
479 struct _cipher_descriptor { |
|
|
480 char *name; |
|
|
481 unsigned long min_key_length, max_key_length, |
|
|
482 block_length, default_rounds; |
|
|
483 int (*setup) (const unsigned char *key, int keylength, |
|
|
484 int num_rounds, symmetric_key *skey); |
|
|
485 void (*ecb_encrypt)(const unsigned char *pt, unsigned char *ct, |
|
|
486 symmetric_key *key); |
|
|
487 void (*ecb_decrypt)(const unsigned char *ct, unsigned char *pt, |
|
|
488 symmetric_key *key); |
|
|
489 int (*test) (void); |
|
|
490 int (*keysize) (int *desired_keysize); |
|
|
491 }; |
|
|
492 \end{verbatim} |
|
|
493 |
|
|
494 Where ``name'' is the lower case ASCII version of the name. The fields ``min\_key\_length'', ``max\_key\_length'' and |
|
|
495 ``block\_length'' are all the number of bytes not bits. As a good rule of thumb it is assumed that the cipher supports |
|
|
496 the min and max key lengths but not always everything in between. The ``default\_rounds'' field is the default number |
|
|
497 of rounds that will be used. |
|
|
498 |
|
|
499 The remaining fields are all pointers to the core functions for each cipher. The end of the cipher\_descriptor array is |
|
|
500 marked when ``name'' equals {\bf NULL}. |
|
|
501 |
|
|
502 As of this release the current cipher\_descriptors elements are |
|
|
503 |
|
|
504 \begin{small} |
|
|
505 \begin{center} |
|
|
506 \begin{tabular}{|c|c|c|c|c|c|} |
|
|
507 \hline Name & Descriptor Name & Block Size & Key Range & Rounds \\ |
|
|
508 \hline Blowfish & blowfish\_desc & 8 & 8 $\ldots$ 56 & 16 \\ |
|
|
509 \hline X-Tea & xtea\_desc & 8 & 16 & 32 \\ |
|
|
510 \hline RC2 & rc2\_desc & 8 & 8 $\ldots$ 128 & 16 \\ |
|
|
511 \hline RC5-32/12/b & rc5\_desc & 8 & 8 $\ldots$ 128 & 12 $\ldots$ 24 \\ |
|
|
512 \hline RC6-32/20/b & rc6\_desc & 16 & 8 $\ldots$ 128 & 20 \\ |
|
|
513 \hline SAFER+ & saferp\_desc &16 & 16, 24, 32 & 8, 12, 16 \\ |
|
|
514 \hline Safer K64 & safer\_k64\_desc & 8 & 8 & 6 $\ldots$ 13 \\ |
|
|
515 \hline Safer SK64 & safer\_sk64\_desc & 8 & 8 & 6 $\ldots$ 13 \\ |
|
|
516 \hline Safer K128 & safer\_k128\_desc & 8 & 16 & 6 $\ldots$ 13 \\ |
|
|
517 \hline Safer SK128 & safer\_sk128\_desc & 8 & 16 & 6 $\ldots$ 13 \\ |
|
|
518 \hline AES & aes\_desc & 16 & 16, 24, 32 & 10, 12, 14 \\ |
|
|
519 \hline Twofish & twofish\_desc & 16 & 16, 24, 32 & 16 \\ |
|
|
520 \hline DES & des\_desc & 8 & 7 & 16 \\ |
|
|
521 \hline 3DES (EDE mode) & des3\_desc & 8 & 21 & 16 \\ |
|
|
522 \hline CAST5 (CAST-128) & cast5\_desc & 8 & 5 $\ldots$ 16 & 12, 16 \\ |
|
|
523 \hline Noekeon & noekeon\_desc & 16 & 16 & 16 \\ |
|
|
524 \hline Skipjack & skipjack\_desc & 8 & 10 & 32 \\ |
|
|
525 \hline |
|
|
526 \end{tabular} |
|
|
527 \end{center} |
|
|
528 \end{small} |
|
|
529 |
|
|
530 \subsection{Notes} |
|
|
531 For the 64-bit SAFER famliy of ciphers (e.g K64, SK64, K128, SK128) the ecb\_encrypt() and ecb\_decrypt() |
|
|
532 functions are the same. So if you want to use those functions directly just call safer\_ecb\_encrypt() |
|
|
533 or safer\_ecb\_decrypt() respectively. |
|
|
534 |
|
|
535 Note that for ``DES'' and ``3DES'' they use 8 and 24 byte keys but only 7 and 21 [respectively] bytes of the keys are in |
|
|
536 fact used for the purposes of encryption. My suggestion is just to use random 8/24 byte keys instead of trying to make a 8/24 |
|
|
537 byte string from the real 7/21 byte key. |
|
|
538 |
|
|
539 Note that ``Twofish'' has additional configuration options that take place at build time. These options are found in |
|
|
540 the file ``mycrypt\_cfg.h''. The first option is ``TWOFISH\_SMALL'' which when defined will force the Twofish code |
|
|
541 to not pre-compute the Twofish ``$g(X)$'' function as a set of four $8 \times 32$ s-boxes. This means that a scheduled |
|
|
542 key will require less ram but the resulting cipher will be slower. The second option is ``TWOFISH\_TABLES'' which when |
|
|
543 defined will force the Twofish code to use pre-computed tables for the two s-boxes $q_0, q_1$ as well as the multiplication |
|
|
544 by the polynomials 5B and EF used in the MDS multiplication. As a result the code is faster and slightly larger. The |
|
|
545 speed increase is useful when ``TWOFISH\_SMALL'' is defined since the s-boxes and MDS multiply form the heart of the |
|
|
546 Twofish round function. |
|
|
547 |
|
|
548 \begin{small} |
|
|
549 \begin{center} |
|
|
550 \begin{tabular}{|l|l|l|} |
|
|
551 \hline TWOFISH\_SMALL & TWOFISH\_TABLES & Speed and Memory (per key) \\ |
|
|
552 \hline undefined & undefined & Very fast, 4.2KB of ram. \\ |
|
|
553 \hline undefined & defined & As above, faster keysetup, larger code (1KB more). \\ |
|
|
554 \hline defined & undefined & Very slow, 0.2KB of ram. \\ |
|
|
555 \hline defined & defined & Somewhat faster, 0.2KB of ram, larger code. \\ |
|
|
556 \hline |
|
|
557 \end{tabular} |
|
|
558 \end{center} |
|
|
559 \end{small} |
|
|
560 |
|
|
561 To work with the cipher\_descriptor array there is a function: |
|
|
562 \begin{verbatim} |
|
|
563 int find_cipher(char *name) |
|
|
564 \end{verbatim} |
|
|
565 Which will search for a given name in the array. It returns negative one if the cipher is not found, otherwise it returns |
|
|
566 the location in the array where the cipher was found. For example, to indirectly setup Blowfish you can also use: |
|
|
567 \begin{small} |
|
|
568 \begin{verbatim} |
|
|
569 #include <mycrypt.h> |
|
|
570 int main(void) |
|
|
571 { |
|
|
572 unsigned char key[8]; |
|
|
573 symmetric_key skey; |
|
|
574 int errno; |
|
|
575 |
|
|
576 /* you must register a cipher before you use it */ |
|
|
577 if (register_cipher(&blowfish_desc)) == -1) { |
|
|
578 printf("Unable to register Blowfish cipher."); |
|
|
579 return -1; |
|
|
580 } |
|
|
581 |
|
|
582 /* generic call to function (assuming the key in key[] was already setup) */ |
|
|
583 if ((errno = cipher_descriptor[find_cipher("blowfish")].setup(key, 8, 0, &skey)) != CRYPT_OK) { |
|
|
584 printf("Error setting up Blowfish: %s\n", error_to_string(errno)); |
|
|
585 return -1; |
|
|
586 } |
|
|
587 |
|
|
588 /* ... use cipher ... */ |
|
|
589 } |
|
|
590 \end{verbatim} |
|
|
591 \end{small} |
|
|
592 |
|
|
593 A good safety would be to check the return value of ``find\_cipher()'' before accessing the desired function. In order |
|
|
594 to use a cipher with the descriptor table you must register it first using: |
|
|
595 \begin{verbatim} |
|
|
596 int register_cipher(const struct _cipher_descriptor *cipher); |
|
|
597 \end{verbatim} |
|
|
598 Which accepts a pointer to a descriptor and returns the index into the global descriptor table. If an error occurs such |
|
|
599 as there is no more room (it can have 32 ciphers at most) it will return {\bf{-1}}. If you try to add the same cipher more |
|
|
600 than once it will just return the index of the first copy. To remove a cipher call: |
|
|
601 \begin{verbatim} |
|
|
602 int unregister_cipher(const struct _cipher_descriptor *cipher); |
|
|
603 \end{verbatim} |
|
|
604 Which returns {\bf CRYPT\_OK} if it removes it otherwise it returns {\bf CRYPT\_ERROR}. Consider: |
|
|
605 \begin{small} |
|
|
606 \begin{verbatim} |
|
|
607 #include <mycrypt.h> |
|
|
608 int main(void) |
|
|
609 { |
|
|
610 int errno; |
|
|
611 |
|
|
612 /* register the cipher */ |
|
|
613 if (register_cipher(&rijndael_desc) == -1) { |
|
|
614 printf("Error registering Rijndael\n"); |
|
|
615 return -1; |
|
|
616 } |
|
|
617 |
|
|
618 /* use Rijndael */ |
|
|
619 |
|
|
620 /* remove it */ |
|
|
621 if ((errno = unregister_cipher(&rijndael_desc)) != CRYPT_OK) { |
|
|
622 printf("Error removing Rijndael: %s\n", error_to_string(errno)); |
|
|
623 return -1; |
|
|
624 } |
|
|
625 |
|
|
626 return 0; |
|
|
627 } |
|
|
628 \end{verbatim} |
|
|
629 \end{small} |
|
|
630 This snippet is a small program that registers only Rijndael only. |
|
|
631 |
|
|
632 \section{Symmetric Modes of Operations} |
|
|
633 \subsection{Background} |
|
|
634 A typical symmetric block cipher can be used in chaining modes to effectively encrypt messages larger than the block |
|
|
635 size of the cipher. Given a key $k$, a plaintext $P$ and a cipher $E$ we shall denote the encryption of the block |
|
|
636 $P$ under the key $k$ as $E_k(P)$. In some modes there exists an initial vector denoted as $C_{-1}$. |
|
|
637 |
|
|
638 \subsubsection{ECB Mode} |
|
|
639 ECB or Electronic Codebook Mode is the simplest method to use. It is given as: |
|
|
640 \begin{equation} |
|
|
641 C_i = E_k(P_i) |
|
|
642 \end{equation} |
|
|
643 This mode is very weak since it allows people to swap blocks and perform replay attacks if the same key is used more |
|
|
644 than once. |
|
|
645 |
|
|
646 \subsubsection{CBC Mode} |
|
|
647 CBC or Cipher Block Chaining mode is a simple mode designed to prevent trivial forms of replay and swap attacks on ciphers. |
|
|
648 It is given as: |
|
|
649 \begin{equation} |
|
|
650 C_i = E_k(P_i \oplus C_{i - 1}) |
|
|
651 \end{equation} |
|
|
652 It is important that the initial vector be unique and preferably random for each message encrypted under the same key. |
|
|
653 |
|
|
654 \subsubsection{CTR Mode} |
|
|
655 CTR or Counter Mode is a mode which only uses the encryption function of the cipher. Given a initial vector which is |
|
|
656 treated as a large binary counter the CTR mode is given as: |
|
|
657 \begin{eqnarray} |
|
|
658 C_{-1} = C_{-1} + 1\mbox{ }(\mbox{mod }2^W) \nonumber \\ |
|
|
659 C_i = P_i \oplus E_k(C_{-1}) |
|
|
660 \end{eqnarray} |
|
|
661 Where $W$ is the size of a block in bits (e.g. 64 for Blowfish). As long as the initial vector is random for each message |
|
|
662 encrypted under the same key replay and swap attacks are infeasible. CTR mode may look simple but it is as secure |
|
|
663 as the block cipher is under a chosen plaintext attack (provided the initial vector is unique). |
|
|
664 |
|
|
665 \subsubsection{CFB Mode} |
|
|
666 CFB or Ciphertext Feedback Mode is a mode akin to CBC. It is given as: |
|
|
667 \begin{eqnarray} |
|
|
668 C_i = P_i \oplus C_{-1} \nonumber \\ |
|
|
669 C_{-1} = E_k(C_i) |
|
|
670 \end{eqnarray} |
|
|
671 Note that in this library the output feedback width is equal to the size of the block cipher. That is this mode is used |
|
|
672 to encrypt whole blocks at a time. However, the library will buffer data allowing the user to encrypt or decrypt partial |
|
|
673 blocks without a delay. When this mode is first setup it will initially encrypt the initial vector as required. |
|
|
674 |
|
|
675 \subsubsection{OFB Mode} |
|
|
676 OFB or Output Feedback Mode is a mode akin to CBC as well. It is given as: |
|
|
677 \begin{eqnarray} |
|
|
678 C_{-1} = E_k(C_{-1}) \nonumber \\ |
|
|
679 C_i = P_i \oplus C_{-1} |
|
|
680 \end{eqnarray} |
|
|
681 Like the CFB mode the output width in CFB mode is the same as the width of the block cipher. OFB mode will also |
|
|
682 buffer the output which will allow you to encrypt or decrypt partial blocks without delay. |
|
|
683 |
|
|
684 \subsection{Choice of Mode} |
|
|
685 My personal preference is for the CTR mode since it has several key benefits: |
|
|
686 \begin{enumerate} |
|
|
687 \item No short cycles which is possible in the OFB and CFB modes. |
|
|
688 \item Provably as secure as the block cipher being used under a chosen plaintext attack. |
|
|
689 \item Technically does not require the decryption routine of the cipher. |
|
|
690 \item Allows random access to the plaintext. |
|
|
691 \item Allows the encryption of block sizes that are not equal to the size of the block cipher. |
|
|
692 \end{enumerate} |
|
|
693 The CTR, CFB and OFB routines provided allow you to encrypt block sizes that differ from the ciphers block size. They |
|
|
694 accomplish this by buffering the data required to complete a block. This allows you to encrypt or decrypt any size |
|
|
695 block of memory with either of the three modes. |
|
|
696 |
|
|
697 The ECB and CBC modes process blocks of the same size as the cipher at a time. Therefore they are less flexible than the |
|
|
698 other modes. |
|
|
699 |
|
|
700 \subsection{Implementation} |
|
|
701 \index{CBC Mode} \index{CTR Mode} |
|
|
702 \index{OFB Mode} \index{CFB Mode} |
|
|
703 The library provides simple support routines for handling CBC, CTR, CFB, OFB and ECB encoded messages. Assuming the mode |
|
|
704 you want is XXX there is a structure called ``symmetric\_XXX'' that will contain the information required to |
|
|
705 use that mode. They have identical setup routines (except ECB mode for obvious reasons): |
|
|
706 \begin{verbatim} |
|
|
707 int XXX_start(int cipher, const unsigned char *IV, |
|
|
708 const unsigned char *key, int keylen, |
|
|
709 int num_rounds, symmetric_XXX *XXX); |
|
|
710 |
|
|
711 int ecb_start(int cipher, const unsigned char *key, int keylen, |
|
|
712 int num_rounds, symmetric_ECB *ecb); |
|
|
713 \end{verbatim} |
|
|
714 |
|
|
715 In each case ``cipher'' is the index into the cipher\_descriptor array of the cipher you want to use. The ``IV'' value is |
|
|
716 the initialization vector to be used with the cipher. You must fill the IV yourself and it is assumed they are the same |
|
|
717 length as the block size\footnote{In otherwords the size of a block of plaintext for the cipher, e.g. 8 for DES, 16 for AES, etc.} |
|
|
718 of the cipher you choose. It is important that the IV be random for each unique message you want to encrypt. The |
|
|
719 parameters ``key'', ``keylen'' and ``num\_rounds'' are the same as in the XXX\_setup() function call. The final parameter |
|
|
720 is a pointer to the structure you want to hold the information for the mode of operation. |
|
|
721 |
|
|
722 Both routines return {\bf CRYPT\_OK} if the cipher initialized correctly, otherwise they return an error code. To |
|
|
723 actually encrypt or decrypt the following routines are provided: |
|
|
724 \begin{verbatim} |
|
|
725 int XXX_encrypt(const unsigned char *pt, unsigned char *ct, |
|
|
726 symmetric_XXX *XXX); |
|
|
727 int XXX_decrypt(const unsigned char *ct, unsigned char *pt, |
|
|
728 symmetric_XXX *XXX); |
|
|
729 |
|
|
730 int YYY_encrypt(const unsigned char *pt, unsigned char *ct, |
|
|
731 unsigned long len, symmetric_YYY *YYY); |
|
|
732 int YYY_decrypt(const unsigned char *ct, unsigned char *pt, |
|
|
733 unsigned long len, symmetric_YYY *YYY); |
|
|
734 \end{verbatim} |
|
|
735 Where ``XXX'' is one of (ecb, cbc) and ``YYY'' is one of (ctr, ofb, cfb). In the CTR, OFB and CFB cases ``len'' is the |
|
|
736 size of the buffer (as number of chars) to encrypt or decrypt. The CTR, OFB and CFB modes are order sensitive but not |
|
|
737 chunk sensitive. That is you can encrypt ``ABCDEF'' in three calls like ``AB'', ``CD'', ``EF'' or two like ``ABCDE'' and ``F'' |
|
|
738 and end up with the same ciphertext. However, encrypting ``ABC'' and ``DABC'' will result in different ciphertexts. All |
|
|
739 five of the modes will return {\bf CRYPT\_OK} on success from the encrypt or decrypt functions. |
|
|
740 |
|
|
741 To decrypt in either mode you simply perform the setup like before (recall you have to fetch the IV value you used) |
|
|
742 and use the decrypt routine on all of the blocks. When you are done working with either mode you should wipe the |
|
|
743 memory (using ``zeromem()'') to help prevent the key from leaking. For example: |
|
|
744 \newpage |
|
|
745 \begin{small} |
|
|
746 \begin{verbatim} |
|
|
747 #include <mycrypt.h> |
|
|
748 int main(void) |
|
|
749 { |
|
|
750 unsigned char key[16], IV[16], buffer[512]; |
|
|
751 symmetric_CTR ctr; |
|
|
752 int x, errno; |
|
|
753 |
|
|
754 /* register twofish first */ |
|
|
755 if (register_cipher(&twofish_desc) == -1) { |
|
|
756 printf("Error registering cipher.\n"); |
|
|
757 return -1; |
|
|
758 } |
|
|
759 |
|
|
760 /* somehow fill out key and IV */ |
|
|
761 |
|
|
762 /* start up CTR mode */ |
|
|
763 if ((errno = ctr_start(find_cipher("twofish"), IV, key, 16, 0, &ctr)) != CRYPT_OK) { |
|
|
764 printf("ctr_start error: %s\n", error_to_string(errno)); |
|
|
765 return -1; |
|
|
766 } |
|
|
767 |
|
|
768 /* somehow fill buffer than encrypt it */ |
|
|
769 if ((errno = ctr_encrypt(buffer, buffer, sizeof(buffer), &ctr)) != CRYPT_OK) { |
|
|
770 printf("ctr_encrypt error: %s\n", error_to_string(errno)); |
|
|
771 return -1; |
|
|
772 } |
|
|
773 |
|
|
774 /* make use of ciphertext... */ |
|
|
775 |
|
|
776 /* clear up and return */ |
|
|
777 zeromem(key, sizeof(key)); |
|
|
778 zeromem(&ctr, sizeof(ctr)); |
|
|
779 |
|
|
780 return 0; |
|
|
781 } |
|
|
782 \end{verbatim} |
|
|
783 \end{small} |
|
|
784 |
|
|
785 \section{Encrypt and Authenticate Modes} |
|
|
786 |
|
|
787 \subsection{EAX Mode} |
|
|
788 LibTomCrypt provides support for a mode called EAX\footnote{See |
|
|
789 M. Bellare, P. Rogaway, D. Wagner, A Conventional Authenticated-Encryption Mode.} in a manner similar to the |
|
|
790 way it was intended to be used. |
|
|
791 |
|
|
792 First a short description of what EAX mode is before I explain how to use it. EAX is a mode that requires a cipher, |
|
|
793 CTR and OMAC support and provides encryption and authentication. It is initialized with a random ``nonce'' that can |
|
|
794 be shared publicly as well as a ``header'' which can be fixed and public as well as a random secret symmetric key. |
|
|
795 |
|
|
796 The ``header'' data is meant to be meta-data associated with a stream that isn't private (e.g. protocol messages). It can |
|
|
797 be added at anytime during an EAX stream and is part of the authentication tag. That is, changes in the meta-data can |
|
|
798 be detected by an invalid output tag. |
|
|
799 |
|
|
800 The mode can then process plaintext producing ciphertext as well as compute a partial checksum. The actual checksum |
|
|
801 called a ``tag'' is only emitted when the message is finished. In the interim though the user can process any arbitrary |
|
|
802 sized message block to send to the recipient as ciphertext. This makes the EAX mode especially suited for streaming modes |
|
|
803 of operation. |
|
|
804 |
|
|
805 The mode is initialized with the following function. |
|
|
806 \begin{verbatim} |
|
|
807 int eax_init(eax_state *eax, int cipher, |
|
|
808 const unsigned char *key, unsigned long keylen, |
|
|
809 const unsigned char *nonce, unsigned long noncelen, |
|
|
810 const unsigned char *header, unsigned long headerlen); |
|
|
811 \end{verbatim} |
|
|
812 |
|
|
813 Where ``eax'' is the EAX state. ``cipher'' is the index of the desired cipher in the descriptor table. |
|
|
814 ``key'' is the shared secret symmetric key of length ``keylen''. ``nonce'' is the random public string of |
|
|
815 length ``noncelen''. ``header'' is the random (or fixed or \textbf{NULL}) header for the message of length |
|
|
816 ``headerlen''. |
|
|
817 |
|
|
818 When this function completes ``eax'' will be initialized such that you can now either have data decrypted or |
|
|
819 encrypted in EAX mode. Note that if ``headerlen'' is zero you may pass ``header'' as \textbf{NULL}. It will still |
|
|
820 initialize the EAX ``H'' value to the correct value. |
|
|
821 |
|
|
822 To encrypt or decrypt data in a streaming mode use the following. |
|
|
823 \begin{verbatim} |
|
|
824 int eax_encrypt(eax_state *eax, const unsigned char *pt, |
|
|
825 unsigned char *ct, unsigned long length); |
|
|
826 |
|
|
827 int eax_decrypt(eax_state *eax, const unsigned char *ct, |
|
|
828 unsigned char *pt, unsigned long length); |
|
|
829 \end{verbatim} |
|
|
830 The function ``eax\_encrypt'' will encrypt the bytes in ``pt'' of ``length'' bytes and store the ciphertext in |
|
|
831 ``ct''. Note that ``ct'' and ``pt'' may be the same region in memory. This function will also send the ciphertext |
|
|
832 through the OMAC function. The function ``eax\_decrypt'' decrypts ``ct'' and stores it in ``pt''. This also allows |
|
|
833 ``pt'' and ``ct'' to be the same region in memory. |
|
|
834 |
|
|
835 Note that both of these functions allow you to send the data in any granularity but the order is important. While |
|
|
836 the eax\_init() function allows you to add initial header data to the stream you can also add header data during the |
|
|
837 EAX stream with the following. |
|
|
838 |
|
|
839 Also note that you cannot both encrypt or decrypt with the same ``eax'' context. For bi-directional communication you |
|
|
840 will need to initialize two EAX contexts (preferably with different headers and nonces). |
|
|
841 |
|
|
842 \begin{verbatim} |
|
|
843 int eax_addheader(eax_state *eax, |
|
|
844 const unsigned char *header, unsigned long length); |
|
|
845 \end{verbatim} |
|
|
846 |
|
|
847 This will add the ``length'' bytes from ``header'' to the given ``eax'' stream. Once the message is finished the |
|
|
848 ``tag'' (checksum) may be computed with the following function. |
|
|
849 |
|
|
850 \begin{verbatim} |
|
|
851 int eax_done(eax_state *eax, |
|
|
852 unsigned char *tag, unsigned long *taglen); |
|
|
853 \end{verbatim} |
|
|
854 This will terminate the EAX state ``eax'' and store upto ``taglen'' bytes of the message tag in ``tag''. The function |
|
|
855 then stores how many bytes of the tag were written out back into ``taglen''. |
|
|
856 |
|
|
857 The EAX mode code can be tested to ensure it matches the test vectors by calling the following function. |
|
|
858 \begin{verbatim} |
|
|
859 int eax_test(void); |
|
|
860 \end{verbatim} |
|
|
861 This requires that the AES (or Rijndael) block cipher be registered with the cipher\_descriptor table first. |
|
|
862 |
|
|
863 \subsection{OCB Mode} |
|
|
864 LibTomCrypt provides support for a mode called OCB\footnote{See |
|
|
865 P. Rogaway, M. Bellare, J. Black, T. Krovetz, ``OCB: A Block Cipher Mode of Operation for Efficient Authenticated Encryption''.} |
|
|
866 in a mode somewhat similar to as it was meant to be used. |
|
|
867 |
|
|
868 OCB is an encryption protocol that simultaneously provides authentication. It is slightly faster to use than EAX mode |
|
|
869 but is less flexible. Let's review how to initialize an OCB context. |
|
|
870 |
|
|
871 \begin{verbatim} |
|
|
872 int ocb_init(ocb_state *ocb, int cipher, |
|
|
873 const unsigned char *key, unsigned long keylen, |
|
|
874 const unsigned char *nonce); |
|
|
875 \end{verbatim} |
|
|
876 |
|
|
877 This will initialize the ``ocb'' context using cipher descriptor ``cipher''. It will use a ``key'' of length ``keylen'' |
|
|
878 and the random ``nonce''. Note that ``nonce'' must be a random (public) string the same length as the block ciphers |
|
|
879 block size (e.g. 16 for AES). |
|
|
880 |
|
|
881 This mode has no ``Associated Data'' like EAX mode does which means you cannot authenticate metadata along with the stream. |
|
|
882 To encrypt or decrypt data use the following. |
|
|
883 |
|
|
884 \begin{verbatim} |
|
|
885 int ocb_encrypt(ocb_state *ocb, const unsigned char *pt, unsigned char *ct); |
|
|
886 int ocb_decrypt(ocb_state *ocb, const unsigned char *ct, unsigned char *pt); |
|
|
887 \end{verbatim} |
|
|
888 |
|
|
889 This will encrypt (or decrypt for the latter) a fixed length of data from ``pt'' to ``ct'' (vice versa for the latter). |
|
|
890 They assume that ``pt'' and ``ct'' are the same size as the block cipher's block size. Note that you cannot call |
|
|
891 both functions given a single ``ocb'' state. For bi-directional communication you will have to initialize two ``ocb'' |
|
|
892 states (with different nonces). Also ``pt'' and ``ct'' may point to the same location in memory. |
|
|
893 |
|
|
894 When you are finished encrypting the message you call the following function to compute the tag. |
|
|
895 |
|
|
896 \begin{verbatim} |
|
|
897 int ocb_done_encrypt(ocb_state *ocb, |
|
|
898 const unsigned char *pt, unsigned long ptlen, |
|
|
899 unsigned char *ct, |
|
|
900 unsigned char *tag, unsigned long *taglen); |
|
|
901 \end{verbatim} |
|
|
902 |
|
|
903 This will terminate an encrypt stream ``ocb''. If you have trailing bytes of plaintext that will not complete a block |
|
|
904 you can pass them here. This will also encrypt the ``ptlen'' bytes in ``pt'' and store them in ``ct''. It will also |
|
|
905 store upto ``taglen'' bytes of the tag into ``tag''. |
|
|
906 |
|
|
907 Note that ``ptlen'' must be less than or equal to the block size of block cipher chosen. Also note that if you have |
|
|
908 an input message equal to the length of the block size then you pass the data here (not to ocb\_encrypt()) only. |
|
|
909 |
|
|
910 To terminate a decrypt stream and compared the tag you call the following. |
|
|
911 |
|
|
912 \begin{verbatim} |
|
|
913 int ocb_done_decrypt(ocb_state *ocb, |
|
|
914 const unsigned char *ct, unsigned long ctlen, |
|
|
915 unsigned char *pt, |
|
|
916 const unsigned char *tag, unsigned long taglen, |
|
|
917 int *res); |
|
|
918 \end{verbatim} |
|
|
919 |
|
|
920 Similarly to the previous function you can pass trailing message bytes into this function. This will compute the |
|
|
921 tag of the message (internally) and then compare it against the ``taglen'' bytes of ``tag'' provided. By default |
|
|
922 ``res'' is set to zero. If all ``taglen'' bytes of ``tag'' can be verified then ``res'' is set to one (authenticated |
|
|
923 message). |
|
|
924 |
|
|
925 To make life simpler the following two functions are provided for memory bound OCB. |
|
|
926 |
|
|
927 \begin{verbatim} |
|
|
928 int ocb_encrypt_authenticate_memory(int cipher, |
|
|
929 const unsigned char *key, unsigned long keylen, |
|
|
930 const unsigned char *nonce, |
|
|
931 const unsigned char *pt, unsigned long ptlen, |
|
|
932 unsigned char *ct, |
|
|
933 unsigned char *tag, unsigned long *taglen); |
|
|
934 \end{verbatim} |
|
|
935 |
|
|
936 This will OCB encrypt the message ``pt'' of length ``ptlen'' and store the ciphertext in ``ct''. The length ``ptlen'' |
|
|
937 can be any arbitrary length. |
|
|
938 |
|
|
939 \begin{verbatim} |
|
|
940 int ocb_decrypt_verify_memory(int cipher, |
|
|
941 const unsigned char *key, unsigned long keylen, |
|
|
942 const unsigned char *nonce, |
|
|
943 const unsigned char *ct, unsigned long ctlen, |
|
|
944 unsigned char *pt, |
|
|
945 const unsigned char *tag, unsigned long taglen, |
|
|
946 int *res); |
|
|
947 \end{verbatim} |
|
|
948 |
|
|
949 Similarly this will OCB decrypt and compare the internally computed tag against the tag provided. ``res'' is set |
|
|
950 appropriately. |
|
|
951 |
|
|
952 |
|
|
953 |
|
|
954 \chapter{One-Way Cryptographic Hash Functions} |
|
|
955 \section{Core Functions} |
|
|
956 |
|
|
957 Like the ciphers there are hash core functions and a universal data type to hold the hash state called ``hash\_state''. |
|
|
958 To initialize hash XXX (where XXX is the name) call: |
|
|
959 \index{Hash Functions} |
|
|
960 \begin{verbatim} |
|
|
961 void XXX_init(hash_state *md); |
|
|
962 \end{verbatim} |
|
|
963 |
|
|
964 This simply sets up the hash to the default state governed by the specifications of the hash. To add data to the |
|
|
965 message being hashed call: |
|
|
966 \begin{verbatim} |
|
|
967 int XXX_process(hash_state *md, const unsigned char *in, unsigned long len); |
|
|
968 \end{verbatim} |
|
|
969 |
|
|
970 Essentially all hash messages are virtually infinitely\footnote{Most hashes are limited to $2^{64}$ bits or 2,305,843,009,213,693,952 bytes.} long message which |
|
|
971 are buffered. The data can be passed in any sized chunks as long as the order of the bytes are the same the message digest |
|
|
972 (hash output) will be the same. For example, this means that: |
|
|
973 \begin{verbatim} |
|
|
974 md5_process(&md, "hello ", 6); |
|
|
975 md5_process(&md, "world", 5); |
|
|
976 \end{verbatim} |
|
|
977 Will produce the same message digest as the single call: |
|
|
978 \index{Message Digest} |
|
|
979 \begin{verbatim} |
|
|
980 md5_process(&md, "hello world", 11); |
|
|
981 \end{verbatim} |
|
|
982 |
|
|
983 To finally get the message digest (the hash) call: |
|
|
984 \begin{verbatim} |
|
|
985 int XXX_done(hash_state *md, |
|
|
986 unsigned char *out); |
|
|
987 \end{verbatim} |
|
|
988 |
|
|
989 This function will finish up the hash and store the result in the ``out'' array. You must ensure that ``out'' is long |
|
|
990 enough for the hash in question. Often hashes are used to get keys for symmetric ciphers so the ``XXX\_done()'' functions |
|
|
991 will wipe the ``md'' variable before returning automatically. |
|
|
992 |
|
|
993 To test a hash function call: |
|
|
994 \begin{verbatim} |
|
|
995 int XXX_test(void); |
|
|
996 \end{verbatim} |
|
|
997 |
|
|
998 This will return {\bf CRYPTO\_OK} if the hash matches the test vectors, otherwise it returns an error code. An |
|
|
999 example snippet that hashes a message with md5 is given below. |
|
|
1000 \begin{small} |
|
|
1001 \begin{verbatim} |
|
|
1002 #include <mycrypt.h> |
|
|
1003 int main(void) |
|
|
1004 { |
|
|
1005 hash_state md; |
|
|
1006 unsigned char *in = "hello world", out[16]; |
|
|
1007 |
|
|
1008 /* setup the hash */ |
|
|
1009 md5_init(&md); |
|
|
1010 |
|
|
1011 /* add the message */ |
|
|
1012 md5_process(&md, in, strlen(in)); |
|
|
1013 |
|
|
1014 /* get the hash in out[0..15] */ |
|
|
1015 md5_done(&md, out); |
|
|
1016 |
|
|
1017 return 0; |
|
|
1018 } |
|
|
1019 \end{verbatim} |
|
|
1020 \end{small} |
|
|
1021 |
|
|
1022 \section{Hash Descriptors} |
|
|
1023 \index{Hash Descriptors} |
|
|
1024 Like the set of ciphers the set of hashes have descriptors too. They are stored in an array called ``hash\_descriptor'' and |
|
|
1025 are defined by: |
|
|
1026 \begin{verbatim} |
|
|
1027 struct _hash_descriptor { |
|
|
1028 char *name; |
|
|
1029 unsigned long hashsize; /* digest output size in bytes */ |
|
|
1030 unsigned long blocksize; /* the block size the hash uses */ |
|
|
1031 void (*init) (hash_state *); |
|
|
1032 int (*process)(hash_state *, const unsigned char *, unsigned long); |
|
|
1033 int (*done) (hash_state *, unsigned char *); |
|
|
1034 int (*test) (void); |
|
|
1035 }; |
|
|
1036 \end{verbatim} |
|
|
1037 |
|
|
1038 Similarly ``name'' is the name of the hash function in ASCII (all lowercase). ``hashsize'' is the size of the digest output |
|
|
1039 in bytes. The remaining fields are pointers to the functions that do the respective tasks. There is a function to |
|
|
1040 search the array as well called ``int find\_hash(char *name)''. It returns -1 if the hash is not found, otherwise the |
|
|
1041 position in the descriptor table of the hash. |
|
|
1042 |
|
|
1043 You can use the table to indirectly call a hash function that is chosen at runtime. For example: |
|
|
1044 \begin{small} |
|
|
1045 \begin{verbatim} |
|
|
1046 #include <mycrypt.h> |
|
|
1047 int main(void) |
|
|
1048 { |
|
|
1049 unsigned char buffer[100], hash[MAXBLOCKSIZE]; |
|
|
1050 int idx, x; |
|
|
1051 hash_state md; |
|
|
1052 |
|
|
1053 /* register hashes .... */ |
|
|
1054 if (register_hash(&md5_desc) == -1) { |
|
|
1055 printf("Error registering MD5.\n"); |
|
|
1056 return -1; |
|
|
1057 } |
|
|
1058 |
|
|
1059 /* register other hashes ... */ |
|
|
1060 |
|
|
1061 /* prompt for name and strip newline */ |
|
|
1062 printf("Enter hash name: \n"); |
|
|
1063 fgets(buffer, sizeof(buffer), stdin); |
|
|
1064 buffer[strlen(buffer) - 1] = 0; |
|
|
1065 |
|
|
1066 /* get hash index */ |
|
|
1067 idx = find_hash(buffer); |
|
|
1068 if (idx == -1) { |
|
|
1069 printf("Invalid hash name!\n"); |
|
|
1070 return -1; |
|
|
1071 } |
|
|
1072 |
|
|
1073 /* hash input until blank line */ |
|
|
1074 hash_descriptor[idx].init(&md); |
|
|
1075 while (fgets(buffer, sizeof(buffer), stdin) != NULL) |
|
|
1076 hash_descriptor[idx].process(&md, buffer, strlen(buffer)); |
|
|
1077 hash_descriptor[idx].done(&md, hash); |
|
|
1078 |
|
|
1079 /* dump to screen */ |
|
|
1080 for (x = 0; x < hash_descriptor[idx].hashsize; x++) |
|
|
1081 printf("%02x ", hash[x]); |
|
|
1082 printf("\n"); |
|
|
1083 return 0; |
|
|
1084 } |
|
|
1085 \end{verbatim} |
|
|
1086 \end{small} |
|
|
1087 |
|
|
1088 Note the usage of ``MAXBLOCKSIZE''. In Libtomcrypt no symmetric block, key or hash digest is larger than MAXBLOCKSIZE in |
|
|
1089 length. This provides a simple size you can set your automatic arrays to that will not get overrun. |
|
|
1090 |
|
|
1091 There are three helper functions as well: |
|
|
1092 \index{hash\_memory()} \index{hash\_file()} |
|
|
1093 \begin{verbatim} |
|
|
1094 int hash_memory(int hash, const unsigned char *data, |
|
|
1095 unsigned long len, unsigned char *dst, |
|
|
1096 unsigned long *outlen); |
|
|
1097 |
|
|
1098 int hash_file(int hash, const char *fname, |
|
|
1099 unsigned char *dst, |
|
|
1100 unsigned long *outlen); |
|
|
1101 |
|
|
1102 int hash_filehandle(int hash, FILE *in, |
|
|
1103 unsigned char *dst, unsigned long *outlen); |
|
|
1104 \end{verbatim} |
|
|
1105 |
|
|
1106 The ``hash'' parameter is the location in the descriptor table of the hash (\textit{e.g. the return of find\_hash()}). |
|
|
1107 The ``*outlen'' variable is used to keep track of the output size. You |
|
|
1108 must set it to the size of your output buffer before calling the functions. When they complete succesfully they store |
|
|
1109 the length of the message digest back in it. The functions are otherwise straightforward. The ``hash\_filehandle'' |
|
|
1110 function assumes that ``in'' is an file handle opened in binary mode. It will hash to the end of file and not reset |
|
|
1111 the file position when finished. |
|
|
1112 |
|
|
1113 To perform the above hash with md5 the following code could be used: |
|
|
1114 \begin{small} |
|
|
1115 \begin{verbatim} |
|
|
1116 #include <mycrypt.h> |
|
|
1117 int main(void) |
|
|
1118 { |
|
|
1119 int idx, errno; |
|
|
1120 unsigned long len; |
|
|
1121 unsigned char out[MAXBLOCKSIZE]; |
|
|
1122 |
|
|
1123 /* register the hash */ |
|
|
1124 if (register_hash(&md5_desc) == -1) { |
|
|
1125 printf("Error registering MD5.\n"); |
|
|
1126 return -1; |
|
|
1127 } |
|
|
1128 |
|
|
1129 /* get the index of the hash */ |
|
|
1130 idx = find_hash("md5"); |
|
|
1131 |
|
|
1132 /* call the hash */ |
|
|
1133 len = sizeof(out); |
|
|
1134 if ((errno = hash_memory(idx, "hello world", 11, out, &len)) != CRYPT_OK) { |
|
|
1135 printf("Error hashing data: %s\n", error_to_string(errno)); |
|
|
1136 return -1; |
|
|
1137 } |
|
|
1138 return 0; |
|
|
1139 } |
|
|
1140 \end{verbatim} |
|
|
1141 \end{small} |
|
|
1142 |
|
|
1143 The following hashes are provided as of this release: |
|
|
1144 \begin{center} |
|
|
1145 \begin{tabular}{|c|c|c|} |
|
|
1146 \hline Name & Descriptor Name & Size of Message Digest (bytes) \\ |
|
|
1147 \hline WHIRLPOOL & whirlpool\_desc & 64 \\ |
|
|
1148 \hline SHA-512 & sha512\_desc & 64 \\ |
|
|
1149 \hline SHA-384 & sha384\_desc & 48 \\ |
|
|
1150 \hline SHA-256 & sha256\_desc & 32 \\ |
|
|
1151 \hline SHA-224 & sha224\_desc & 28 \\ |
|
|
1152 \hline TIGER-192 & tiger\_desc & 24 \\ |
|
|
1153 \hline SHA-1 & sha1\_desc & 20 \\ |
|
|
1154 \hline RIPEMD-160 & rmd160\_desc & 20 \\ |
|
|
1155 \hline RIPEMD-128 & rmd128\_desc & 16 \\ |
|
|
1156 \hline MD5 & md5\_desc & 16 \\ |
|
|
1157 \hline MD4 & md4\_desc & 16 \\ |
|
|
1158 \hline MD2 & md2\_desc & 16 \\ |
|
|
1159 \hline |
|
|
1160 \end{tabular} |
|
|
1161 \end{center} |
|
|
1162 |
|
|
1163 Similar to the cipher descriptor table you must register your hash algorithms before you can use them. These functions |
|
|
1164 work exactly like those of the cipher registration code. The functions are: |
|
|
1165 \begin{verbatim} |
|
|
1166 int register_hash(const struct _hash_descriptor *hash); |
|
|
1167 int unregister_hash(const struct _hash_descriptor *hash); |
|
|
1168 \end{verbatim} |
|
|
1169 |
|
|
1170 \subsection{Notice} |
|
|
1171 It is highly recommended that you \textbf{not} use the MD4 or MD5 hashes for the purposes of digital signatures or authentication codes. |
|
|
1172 These hashes are provided for completeness and they still can be used for the purposes of password hashing or one-way accumulators |
|
|
1173 (e.g. Yarrow). |
|
|
1174 |
|
|
1175 The other hashes such as the SHA-1, SHA-2 (that includes SHA-512, SHA-384 and SHA-256) and TIGER-192 are still considered secure |
|
|
1176 for all purposes you would normally use a hash for. |
|
|
1177 |
|
|
1178 \chapter{Message Authentication Codes} |
|
|
1179 \section{HMAC Protocol} |
|
|
1180 Thanks to Dobes Vandermeer the library now includes support for hash based message authenication codes or HMAC for short. An HMAC |
|
|
1181 of a message is a keyed authenication code that only the owner of a private symmetric key will be able to verify. The purpose is |
|
|
1182 to allow an owner of a private symmetric key to produce an HMAC on a message then later verify if it is correct. Any impostor or |
|
|
1183 eavesdropper will not be able to verify the authenticity of a message. |
|
|
1184 |
|
|
1185 The HMAC support works much like the normal hash functions except that the initialization routine requires you to pass a key |
|
|
1186 and its length. The key is much like a key you would pass to a cipher. That is, it is simply an array of octets stored in |
|
|
1187 chars. The initialization routine is: |
|
|
1188 \begin{verbatim} |
|
|
1189 int hmac_init(hmac_state *hmac, int hash, |
|
|
1190 const unsigned char *key, unsigned long keylen); |
|
|
1191 \end{verbatim} |
|
|
1192 The ``hmac'' parameter is the state for the HMAC code. ``hash'' is the index into the descriptor table of the hash you want |
|
|
1193 to use to authenticate the message. ``key'' is the pointer to the array of chars that make up the key. ``keylen'' is the |
|
|
1194 length (in octets) of the key you want to use to authenticate the message. To send octets of a message through the HMAC system you must use the following function: |
|
|
1195 \begin{verbatim} |
|
|
1196 int hmac_process(hmac_state *hmac, const unsigned char *buf, |
|
|
1197 unsigned long len); |
|
|
1198 \end{verbatim} |
|
|
1199 ``hmac'' is the HMAC state you are working with. ``buf'' is the array of octets to send into the HMAC process. ``len'' is the |
|
|
1200 number of octets to process. Like the hash process routines you can send the data in arbitrarly sized chunks. When you |
|
|
1201 are finished with the HMAC process you must call the following function to get the HMAC code: |
|
|
1202 \begin{verbatim} |
|
|
1203 int hmac_done(hmac_state *hmac, unsigned char *hashOut, |
|
|
1204 unsigned long *outlen); |
|
|
1205 \end{verbatim} |
|
|
1206 ``hmac'' is the HMAC state you are working with. ``hashOut'' is the array of octets where the HMAC code should be stored. You must |
|
|
1207 set ``outlen'' to the size of the destination buffer before calling this function. It is updated with the length of the HMAC code |
|
|
1208 produced (depending on which hash was picked). If ``outlen'' is less than the size of the message digest (and ultimately |
|
|
1209 the HMAC code) then the HMAC code is truncated as per FIPS-198 specifications (e.g. take the first ``outlen'' bytes). |
|
|
1210 |
|
|
1211 There are two utility functions provided to make using HMACs easier todo. They accept the key and information about the |
|
|
1212 message (file pointer, address in memory) and produce the HMAC result in one shot. These are useful if you want to avoid |
|
|
1213 calling the three step process yourself. |
|
|
1214 |
|
|
1215 \begin{verbatim} |
|
|
1216 int hmac_memory(int hash, const unsigned char *key, unsigned long keylen, |
|
|
1217 const unsigned char *data, unsigned long len, |
|
|
1218 unsigned char *dst, unsigned long *dstlen); |
|
|
1219 \end{verbatim} |
|
|
1220 This will produce an HMAC code for the array of octets in ``data'' of length ``len''. The index into the hash descriptor |
|
|
1221 table must be provided in ``hash''. It uses the key from ``key'' with a key length of ``keylen''. |
|
|
1222 The result is stored in the array of octets ``dst'' and the length in ``dstlen''. The value of ``dstlen'' must be set |
|
|
1223 to the size of the destination buffer before calling this function. Similarly for files there is the following function: |
|
|
1224 \begin{verbatim} |
|
|
1225 int hmac_file(int hash, const char *fname, const unsigned char *key, |
|
|
1226 unsigned long keylen, |
|
|
1227 unsigned char *dst, unsigned long *dstlen); |
|
|
1228 \end{verbatim} |
|
|
1229 ``hash'' is the index into the hash descriptor table of the hash you want to use. ``fname'' is the filename to process. |
|
|
1230 ``key'' is the array of octets to use as the key of length ``keylen''. ``dst'' is the array of octets where the |
|
|
1231 result should be stored. |
|
|
1232 |
|
|
1233 To test if the HMAC code is working there is the following function: |
|
|
1234 \begin{verbatim} |
|
|
1235 int hmac_test(void); |
|
|
1236 \end{verbatim} |
|
|
1237 Which returns {\bf CRYPT\_OK} if the code passes otherwise it returns an error code. Some example code for using the |
|
|
1238 HMAC system is given below. |
|
|
1239 |
|
|
1240 \begin{small} |
|
|
1241 \begin{verbatim} |
|
|
1242 #include <mycrypt.h> |
|
|
1243 int main(void) |
|
|
1244 { |
|
|
1245 int idx, errno; |
|
|
1246 hmac_state hmac; |
|
|
1247 unsigned char key[16], dst[MAXBLOCKSIZE]; |
|
|
1248 unsigned long dstlen; |
|
|
1249 |
|
|
1250 /* register SHA-1 */ |
|
|
1251 if (register_hash(&sha1_desc) == -1) { |
|
|
1252 printf("Error registering SHA1\n"); |
|
|
1253 return -1; |
|
|
1254 } |
|
|
1255 |
|
|
1256 /* get index of SHA1 in hash descriptor table */ |
|
|
1257 idx = find_hash("sha1"); |
|
|
1258 |
|
|
1259 /* we would make up our symmetric key in "key[]" here */ |
|
|
1260 |
|
|
1261 /* start the HMAC */ |
|
|
1262 if ((errno = hmac_init(&hmac, idx, key, 16)) != CRYPT_OK) { |
|
|
1263 printf("Error setting up hmac: %s\n", error_to_string(errno)); |
|
|
1264 return -1; |
|
|
1265 } |
|
|
1266 |
|
|
1267 /* process a few octets */ |
|
|
1268 if((errno = hmac_process(&hmac, "hello", 5) != CRYPT_OK) { |
|
|
1269 printf("Error processing hmac: %s\n", error_to_string(errno)); |
|
|
1270 return -1; |
|
|
1271 } |
|
|
1272 |
|
|
1273 /* get result (presumably to use it somehow...) */ |
|
|
1274 dstlen = sizeof(dst); |
|
|
1275 if ((errno = hmac_done(&hmac, dst, &dstlen)) != CRYPT_OK) { |
|
|
1276 printf("Error finishing hmac: %s\n", error_to_string(errno)); |
|
|
1277 return -1; |
|
|
1278 } |
|
|
1279 printf("The hmac is %lu bytes long\n", dstlen); |
|
|
1280 |
|
|
1281 /* return */ |
|
|
1282 return 0; |
|
|
1283 } |
|
|
1284 \end{verbatim} |
|
|
1285 \end{small} |
|
|
1286 |
|
|
1287 \section{OMAC Support} |
|
|
1288 OMAC\footnote{\url{http://crypt.cis.ibaraki.ac.jp/omac/omac.html}}, which stands for \textit{One-Key CBC MAC} is an |
|
|
1289 algorithm which produces a Message Authentication Code (MAC) using only a block cipher such as AES. From an API |
|
|
1290 standpoint the OMAC routines work much like the HMAC routines do. Instead in this case a cipher is used instead of a hash. |
|
|
1291 |
|
|
1292 To start an OMAC state you call |
|
|
1293 |
|
|
1294 \begin{verbatim} |
|
|
1295 int omac_init(omac_state *omac, int cipher, |
|
|
1296 const unsigned char *key, unsigned long keylen); |
|
|
1297 \end{verbatim} |
|
|
1298 The ``omac'' variable is the state for the OMAC algorithm. ``cipher'' is the index into the cipher\_descriptor table |
|
|
1299 of the cipher\footnote{The cipher must have a 64 or 128 bit block size. Such as CAST5, Blowfish, DES, AES, Twofish, etc.} you |
|
|
1300 wish to use. ``key'' and ``keylen'' are the keys used to authenticate the data. |
|
|
1301 |
|
|
1302 To send data through the algorithm call |
|
|
1303 \begin{verbatim} |
|
|
1304 int omac_process(omac_state *state, |
|
|
1305 const unsigned char *buf, unsigned long len); |
|
|
1306 \end{verbatim} |
|
|
1307 This will send ``len'' bytes from ``buf'' through the active OMAC state ``state''. Returns \textbf{CRYPT\_OK} if the |
|
|
1308 function succeeds. The function is not sensitive to the granularity of the data. For example, |
|
|
1309 |
|
|
1310 \begin{verbatim} |
|
|
1311 omac_process(&mystate, "hello", 5); |
|
|
1312 omac_process(&mystate, " world", 6); |
|
|
1313 \end{verbatim} |
|
|
1314 |
|
|
1315 Would produce the same result as, |
|
|
1316 |
|
|
1317 \begin{verbatim} |
|
|
1318 omac_process(&mystate, "hello world", 11); |
|
|
1319 \end{verbatim} |
|
|
1320 |
|
|
1321 When you are done processing the message you can call the following to compute the message tag. |
|
|
1322 |
|
|
1323 \begin{verbatim} |
|
|
1324 int omac_done(omac_state *state, |
|
|
1325 unsigned char *out, unsigned long *outlen); |
|
|
1326 \end{verbatim} |
|
|
1327 Which will terminate the OMAC and output the \textit{tag} (MAC) to ``out''. Note that unlike the HMAC and other code |
|
|
1328 ``outlen'' can be smaller than the default MAC size (for instance AES would make a 16-byte tag). Part of the OMAC |
|
|
1329 specification states that the output may be truncated. So if you pass in $outlen = 5$ and use AES as your cipher than |
|
|
1330 the output MAC code will only be five bytes long. If ``outlen'' is larger than the default size it is set to the default |
|
|
1331 size to show how many bytes were actually used. |
|
|
1332 |
|
|
1333 Similar to the HMAC code the file and memory functions are also provided. To OMAC a buffer of memory in one shot use the |
|
|
1334 following function. |
|
|
1335 |
|
|
1336 \begin{verbatim} |
|
|
1337 int omac_memory(int cipher, |
|
|
1338 const unsigned char *key, unsigned long keylen, |
|
|
1339 const unsigned char *msg, unsigned long msglen, |
|
|
1340 unsigned char *out, unsigned long *outlen); |
|
|
1341 \end{verbatim} |
|
|
1342 This will compute the OMAC of ``msglen'' bytes of ``msg'' using the key ``key'' of length ``keylen'' bytes and the cipher |
|
|
1343 specified by the ``cipher'''th entry in the cipher\_descriptor table. It will store the MAC in ``out'' with the same |
|
|
1344 rules as omac\_done. |
|
|
1345 |
|
|
1346 To OMAC a file use |
|
|
1347 \begin{verbatim} |
|
|
1348 int omac_file(int cipher, |
|
|
1349 const unsigned char *key, unsigned long keylen, |
|
|
1350 const char *filename, |
|
|
1351 unsigned char *out, unsigned long *outlen); |
|
|
1352 \end{verbatim} |
|
|
1353 |
|
|
1354 Which will OMAC the entire contents of the file specified by ``filename'' using the key ``key'' of length ``keylen'' bytes |
|
|
1355 and the cipher specified by the ``cipher'''th entry in the cipher\_descriptor table. It will store the MAC in ``out'' with |
|
|
1356 the same rules as omac\_done. |
|
|
1357 |
|
|
1358 To test if the OMAC code is working there is the following function: |
|
|
1359 \begin{verbatim} |
|
|
1360 int omac_test(void); |
|
|
1361 \end{verbatim} |
|
|
1362 Which returns {\bf CRYPT\_OK} if the code passes otherwise it returns an error code. Some example code for using the |
|
|
1363 OMAC system is given below. |
|
|
1364 |
|
|
1365 \begin{small} |
|
|
1366 \begin{verbatim} |
|
|
1367 #include <mycrypt.h> |
|
|
1368 int main(void) |
|
|
1369 { |
|
|
1370 int idx, err; |
|
|
1371 omac_state omac; |
|
|
1372 unsigned char key[16], dst[MAXBLOCKSIZE]; |
|
|
1373 unsigned long dstlen; |
|
|
1374 |
|
|
1375 /* register Rijndael */ |
|
|
1376 if (register_cipher(&rijndael_desc) == -1) { |
|
|
1377 printf("Error registering Rijndael\n"); |
|
|
1378 return -1; |
|
|
1379 } |
|
|
1380 |
|
|
1381 /* get index of Rijndael in cipher descriptor table */ |
|
|
1382 idx = find_cipher("rijndael"); |
|
|
1383 |
|
|
1384 /* we would make up our symmetric key in "key[]" here */ |
|
|
1385 |
|
|
1386 /* start the OMAC */ |
|
|
1387 if ((err = omac_init(&omac, idx, key, 16)) != CRYPT_OK) { |
|
|
1388 printf("Error setting up omac: %s\n", error_to_string(err)); |
|
|
1389 return -1; |
|
|
1390 } |
|
|
1391 |
|
|
1392 /* process a few octets */ |
|
|
1393 if((err = omac_process(&omac, "hello", 5) != CRYPT_OK) { |
|
|
1394 printf("Error processing omac: %s\n", error_to_string(err)); |
|
|
1395 return -1; |
|
|
1396 } |
|
|
1397 |
|
|
1398 /* get result (presumably to use it somehow...) */ |
|
|
1399 dstlen = sizeof(dst); |
|
|
1400 if ((err = omac_done(&omac, dst, &dstlen)) != CRYPT_OK) { |
|
|
1401 printf("Error finishing omac: %s\n", error_to_string(err)); |
|
|
1402 return -1; |
|
|
1403 } |
|
|
1404 printf("The omac is %lu bytes long\n", dstlen); |
|
|
1405 |
|
|
1406 /* return */ |
|
|
1407 return 0; |
|
|
1408 } |
|
|
1409 \end{verbatim} |
|
|
1410 \end{small} |
|
|
1411 |
|
|
1412 \section{PMAC Support} |
|
|
1413 The PMAC\footnote{J.Black, P.Rogaway, ``A Block--Cipher Mode of Operation for Parallelizable Message Authentication''} |
|
|
1414 protocol is another MAC algorithm that relies solely on a symmetric-key block cipher. It uses essentially the same |
|
|
1415 API as the provided OMAC code. |
|
|
1416 |
|
|
1417 A PMAC state is initialized with the following. |
|
|
1418 |
|
|
1419 \begin{verbatim} |
|
|
1420 int pmac_init(pmac_state *pmac, int cipher, |
|
|
1421 const unsigned char *key, unsigned long keylen); |
|
|
1422 \end{verbatim} |
|
|
1423 Which initializes the ``pmac'' state with the given ``cipher'' and ``key'' of length ``keylen'' bytes. The chosen cipher |
|
|
1424 must have a 64 or 128 bit block size (e.x. AES). |
|
|
1425 |
|
|
1426 To MAC data simply send it through the process function. |
|
|
1427 |
|
|
1428 \begin{verbatim} |
|
|
1429 int pmac_process(pmac_state *state, |
|
|
1430 const unsigned char *buf, unsigned long len); |
|
|
1431 \end{verbatim} |
|
|
1432 This will process ``len'' bytes of ``buf'' in the given ``state''. The function is not sensitive to the granularity of the |
|
|
1433 data. For example, |
|
|
1434 |
|
|
1435 \begin{verbatim} |
|
|
1436 pmac_process(&mystate, "hello", 5); |
|
|
1437 pmac_process(&mystate, " world", 6); |
|
|
1438 \end{verbatim} |
|
|
1439 |
|
|
1440 Would produce the same result as, |
|
|
1441 |
|
|
1442 \begin{verbatim} |
|
|
1443 pmac_process(&mystate, "hello world", 11); |
|
|
1444 \end{verbatim} |
|
|
1445 |
|
|
1446 When a complete message has been processed the following function can be called to compute the message tag. |
|
|
1447 |
|
|
1448 \begin{verbatim} |
|
|
1449 int pmac_done(pmac_state *state, |
|
|
1450 unsigned char *out, unsigned long *outlen); |
|
|
1451 \end{verbatim} |
|
|
1452 This will store upto ``outlen'' bytes of the tag for the given ``state'' into ``out''. Note that if ``outlen'' is larger |
|
|
1453 than the size of the tag it is set to the amount of bytes stored in ``out''. |
|
|
1454 |
|
|
1455 Similar to the PMAC code the file and memory functions are also provided. To PMAC a buffer of memory in one shot use the |
|
|
1456 following function. |
|
|
1457 |
|
|
1458 \begin{verbatim} |
|
|
1459 int pmac_memory(int cipher, |
|
|
1460 const unsigned char *key, unsigned long keylen, |
|
|
1461 const unsigned char *msg, unsigned long msglen, |
|
|
1462 unsigned char *out, unsigned long *outlen); |
|
|
1463 \end{verbatim} |
|
|
1464 This will compute the PMAC of ``msglen'' bytes of ``msg'' using the key ``key'' of length ``keylen'' bytes and the cipher |
|
|
1465 specified by the ``cipher'''th entry in the cipher\_descriptor table. It will store the MAC in ``out'' with the same |
|
|
1466 rules as omac\_done. |
|
|
1467 |
|
|
1468 To PMAC a file use |
|
|
1469 \begin{verbatim} |
|
|
1470 int pmac_file(int cipher, |
|
|
1471 const unsigned char *key, unsigned long keylen, |
|
|
1472 const char *filename, |
|
|
1473 unsigned char *out, unsigned long *outlen); |
|
|
1474 \end{verbatim} |
|
|
1475 |
|
|
1476 Which will PMAC the entire contents of the file specified by ``filename'' using the key ``key'' of length ``keylen'' bytes |
|
|
1477 and the cipher specified by the ``cipher'''th entry in the cipher\_descriptor table. It will store the MAC in ``out'' with |
|
|
1478 the same rules as omac\_done. |
|
|
1479 |
|
|
1480 To test if the PMAC code is working there is the following function: |
|
|
1481 \begin{verbatim} |
|
|
1482 int pmac_test(void); |
|
|
1483 \end{verbatim} |
|
|
1484 Which returns {\bf CRYPT\_OK} if the code passes otherwise it returns an error code. |
|
|
1485 |
|
|
1486 |
|
|
1487 \chapter{Pseudo-Random Number Generators} |
|
|
1488 \section{Core Functions} |
|
|
1489 |
|
|
1490 The library provides an array of core functions for Pseudo-Random Number Generators (PRNGs) as well. A cryptographic PRNG is |
|
|
1491 used to expand a shorter bit string into a longer bit string. PRNGs are used wherever random data is required such as Public Key (PK) |
|
|
1492 key generation. There is a universal structure called ``prng\_state''. To initialize a PRNG call: |
|
|
1493 \begin{verbatim} |
|
|
1494 int XXX_start(prng_state *prng); |
|
|
1495 \end{verbatim} |
|
|
1496 |
|
|
1497 This will setup the PRNG for future use and not seed it. In order |
|
|
1498 for the PRNG to be cryptographically useful you must give it entropy. Ideally you'd have some OS level source to tap |
|
|
1499 like in UNIX (see section 5.3). To add entropy to the PRNG call: |
|
|
1500 \begin{verbatim} |
|
|
1501 int XXX_add_entropy(const unsigned char *in, unsigned long len, |
|
|
1502 prng_state *prng); |
|
|
1503 \end{verbatim} |
|
|
1504 |
|
|
1505 Which returns {\bf CRYPTO\_OK} if the entropy was accepted. Once you think you have enough entropy you call another |
|
|
1506 function to put the entropy into action. |
|
|
1507 \begin{verbatim} |
|
|
1508 int XXX_ready(prng_state *prng); |
|
|
1509 \end{verbatim} |
|
|
1510 |
|
|
1511 Which returns {\bf CRYPTO\_OK} if it is ready. Finally to actually read bytes call: |
|
|
1512 \begin{verbatim} |
|
|
1513 unsigned long XXX_read(unsigned char *out, unsigned long len, |
|
|
1514 prng_state *prng); |
|
|
1515 \end{verbatim} |
|
|
1516 |
|
|
1517 Which returns the number of bytes read from the PRNG. |
|
|
1518 |
|
|
1519 \subsection{Remarks} |
|
|
1520 |
|
|
1521 It is possible to be adding entropy and reading from a PRNG at the same time. For example, if you first seed the PRNG |
|
|
1522 and call ready() you can now read from it. You can also keep adding new entropy to it. The new entropy will not be used |
|
|
1523 in the PRNG until ready() is called again. This allows the PRNG to be used and re-seeded at the same time. No real error |
|
|
1524 checking is guaranteed to see if the entropy is sufficient or if the PRNG is even in a ready state before reading. |
|
|
1525 |
|
|
1526 \subsection{Example} |
|
|
1527 |
|
|
1528 Below is a simple snippet to read 10 bytes from yarrow. Its important to note that this snippet is {\bf NOT} secure since |
|
|
1529 the entropy added is not random. |
|
|
1530 |
|
|
1531 \begin{verbatim} |
|
|
1532 #include <mycrypt.h> |
|
|
1533 int main(void) |
|
|
1534 { |
|
|
1535 prng_state prng; |
|
|
1536 unsigned char buf[10]; |
|
|
1537 int err; |
|
|
1538 |
|
|
1539 /* start it */ |
|
|
1540 if ((err = yarrow_start(&prng)) != CRYPT_OK) { |
|
|
1541 printf("Start error: %s\n", error_to_string(err)); |
|
|
1542 } |
|
|
1543 /* add entropy */ |
|
|
1544 if ((err = yarrow_add_entropy("hello world", 11, &prng)) != CRYPT_OK) { |
|
|
1545 printf("Add_entropy error: %s\n", error_to_string(err)); |
|
|
1546 } |
|
|
1547 /* ready and read */ |
|
|
1548 if ((err = yarrow_ready(&prng)) != CRYPT_OK) { |
|
|
1549 printf("Ready error: %s\n", error_to_string(err)); |
|
|
1550 } |
|
|
1551 printf("Read %lu bytes from yarrow\n", yarrow_read(buf, 10, &prng)); |
|
|
1552 return 0; |
|
|
1553 } |
|
|
1554 \end{verbatim} |
|
|
1555 |
|
|
1556 \section{PRNG Descriptors} |
|
|
1557 \index{PRNG Descriptor} |
|
|
1558 PRNGs have descriptors too (surprised?). Stored in the structure ``prng\_descriptor''. The format of an element is: |
|
|
1559 \begin{verbatim} |
|
|
1560 struct _prng_descriptor { |
|
|
1561 char *name; |
|
|
1562 int (*start) (prng_state *); |
|
|
1563 int (*add_entropy)(const unsigned char *, unsigned long, prng_state *); |
|
|
1564 int (*ready) (prng_state *); |
|
|
1565 unsigned long (*read)(unsigned char *, unsigned long len, prng_state *); |
|
|
1566 }; |
|
|
1567 \end{verbatim} |
|
|
1568 |
|
|
1569 There is a ``int find\_prng(char *name)'' function as well. Returns -1 if the PRNG is not found, otherwise it returns |
|
|
1570 the position in the prng\_descriptor array. |
|
|
1571 |
|
|
1572 Just like the ciphers and hashes you must register your prng before you can use it. The two functions provided work |
|
|
1573 exactly as those for the cipher registry functions. They are: |
|
|
1574 \begin{verbatim} |
|
|
1575 int register_prng(const struct _prng_descriptor *prng); |
|
|
1576 int unregister_prng(const struct _prng_descriptor *prng); |
|
|
1577 \end{verbatim} |
|
|
1578 |
|
|
1579 \subsubsection{PRNGs Provided} |
|
|
1580 Currently Yarrow (yarrow\_desc), RC4 (rc4\_desc) and the secure RNG (sprng\_desc) are provided as PRNGs within the |
|
|
1581 library. |
|
|
1582 |
|
|
1583 RC4 is provided with a PRNG interface because it is a stream cipher and not well suited for the symmetric block cipher |
|
|
1584 interface. You provide the key for RC4 via the rc4\_add\_entropy() function. By calling rc4\_ready() the key will be used |
|
|
1585 to setup the RC4 state for encryption or decryption. The rc4\_read() function has been modified from RC4 since it will |
|
|
1586 XOR the output of the RC4 keystream generator against the input buffer you provide. The following snippet will demonstrate |
|
|
1587 how to encrypt a buffer with RC4: |
|
|
1588 |
|
|
1589 \begin{small} |
|
|
1590 \begin{verbatim} |
|
|
1591 #include <mycrypt.h> |
|
|
1592 int main(void) |
|
|
1593 { |
|
|
1594 prng_state prng; |
|
|
1595 unsigned char buf[32]; |
|
|
1596 int err; |
|
|
1597 |
|
|
1598 if ((err = rc4_start(&prng)) != CRYPT_OK) { |
|
|
1599 printf("RC4 init error: %s\n", error_to_string(err)); |
|
|
1600 exit(-1); |
|
|
1601 } |
|
|
1602 |
|
|
1603 /* use ``key'' as the key */ |
|
|
1604 if ((err = rc4_add_entropy("key", 3, &prng)) != CRYPT_OK) { |
|
|
1605 printf("RC4 add entropy error: %s\n", error_to_string(err)); |
|
|
1606 exit(-1); |
|
|
1607 } |
|
|
1608 |
|
|
1609 /* setup RC4 for use */ |
|
|
1610 if ((err = rc4_ready(&prng)) != CRYPT_OK) { |
|
|
1611 printf("RC4 ready error: %s\n", error_to_string(err)); |
|
|
1612 exit(-1); |
|
|
1613 } |
|
|
1614 |
|
|
1615 /* encrypt buffer */ |
|
|
1616 strcpy(buf,"hello world"); |
|
|
1617 if (rc4_read(buf, 11, &prng) != 11) { |
|
|
1618 printf("RC4 read error\n"); |
|
|
1619 exit(-1); |
|
|
1620 } |
|
|
1621 return 0; |
|
|
1622 } |
|
|
1623 \end{verbatim} |
|
|
1624 \end{small} |
|
|
1625 To decrypt you have to do the exact same steps. |
|
|
1626 |
|
|
1627 \section{The Secure RNG} |
|
|
1628 \index{Secure RNG} |
|
|
1629 An RNG is related to a PRNG except that it doesn't expand a smaller seed to get the data. They generate their random bits |
|
|
1630 by performing some computation on fresh input bits. Possibly the hardest thing to get correctly in a cryptosystem is the |
|
|
1631 PRNG. Computers are deterministic beasts that try hard not to stray from pre-determined paths. That makes gathering |
|
|
1632 entropy needed to seed the PRNG a hard task. |
|
|
1633 |
|
|
1634 There is one small function that may help on certain platforms: |
|
|
1635 \index{rng\_get\_bytes()} |
|
|
1636 \begin{verbatim} |
|
|
1637 unsigned long rng_get_bytes(unsigned char *buf, unsigned long len, |
|
|
1638 void (*callback)(void)); |
|
|
1639 \end{verbatim} |
|
|
1640 |
|
|
1641 Which will try one of three methods of getting random data. The first is to open the popular ``/dev/random'' device which |
|
|
1642 on most *NIX platforms provides cryptographic random bits\footnote{This device is available in Windows through the Cygwin compiler suite. It emulates ``/dev/random'' via the Microsoft CSP.}. |
|
|
1643 The second method is to try the Microsoft Cryptographic Service Provider and read the RNG. The third method is an ANSI C |
|
|
1644 clock drift method that is also somewhat popular but gives bits of lower entropy. The ``callback'' parameter is a pointer to a function that returns void. Its used when the slower ANSI C RNG must be |
|
|
1645 used so the calling application can still work. This is useful since the ANSI C RNG has a throughput of three |
|
|
1646 bytes a second. The callback pointer may be set to {\bf NULL} to avoid using it if you don't want to. The function |
|
|
1647 returns the number of bytes actually read from any RNG source. There is a function to help setup a PRNG as well: |
|
|
1648 \index{rng\_make\_prng()} |
|
|
1649 \begin{verbatim} |
|
|
1650 int rng_make_prng(int bits, int wprng, prng_state *prng, |
|
|
1651 void (*callback)(void)); |
|
|
1652 \end{verbatim} |
|
|
1653 This will try to setup the prng with a state of at least ``bits'' of entropy. The ``callback'' parameter works much like |
|
|
1654 the callback in ``rng\_get\_bytes()''. It is highly recommended that you use this function to setup your PRNGs unless you have a |
|
|
1655 platform where the RNG doesn't work well. Example usage of this function is given below. |
|
|
1656 |
|
|
1657 \begin{small} |
|
|
1658 \begin{verbatim} |
|
|
1659 #include <mycrypt.h> |
|
|
1660 int main(void) |
|
|
1661 { |
|
|
1662 ecc_key mykey; |
|
|
1663 prng_state prng; |
|
|
1664 int err; |
|
|
1665 |
|
|
1666 /* register yarrow */ |
|
|
1667 if (register_prng(&yarrow_desc) == -1) { |
|
|
1668 printf("Error registering Yarrow\n"); |
|
|
1669 return -1; |
|
|
1670 } |
|
|
1671 |
|
|
1672 /* setup the PRNG */ |
|
|
1673 if ((err = rng_make_prng(128, find_prng("yarrow"), &prng, NULL)) != CRYPT_OK) { |
|
|
1674 printf("Error setting up PRNG, %s\n", error_to_string(err)); |
|
|
1675 return -1; |
|
|
1676 } |
|
|
1677 |
|
|
1678 /* make a 192-bit ECC key */ |
|
|
1679 if ((err = ecc_make_key(&prng, find_prng("yarrow"), 24, &mykey)) != CRYPT_OK) { |
|
|
1680 printf("Error making key: %s\n", error_to_string(err)); |
|
|
1681 return -1; |
|
|
1682 } |
|
|
1683 return 0; |
|
|
1684 } |
|
|
1685 \end{verbatim} |
|
|
1686 \end{small} |
|
|
1687 |
|
|
1688 \subsection{The Secure PRNG Interface} |
|
|
1689 It is possible to access the secure RNG through the PRNG interface and in turn use it within dependent functions such |
|
|
1690 as the PK API. This simplifies the cryptosystem on platforms where the secure RNG is fast. The secure PRNG never |
|
|
1691 requires to be started, that is you need not call the start, add\_entropy or ready functions. For example, consider |
|
|
1692 the previous example using this PRNG. |
|
|
1693 |
|
|
1694 \begin{small} |
|
|
1695 \begin{verbatim} |
|
|
1696 #include <mycrypt.h> |
|
|
1697 int main(void) |
|
|
1698 { |
|
|
1699 ecc_key mykey; |
|
|
1700 int err; |
|
|
1701 |
|
|
1702 /* register SPRNG */ |
|
|
1703 if (register_prng(&sprng_desc) == -1) { |
|
|
1704 printf("Error registering SPRNG\n"); |
|
|
1705 return -1; |
|
|
1706 } |
|
|
1707 |
|
|
1708 /* make a 192-bit ECC key */ |
|
|
1709 if ((err = ecc_make_key(NULL, find_prng("sprng"), 24, &mykey)) != CRYPT_OK) { |
|
|
1710 printf("Error making key: %s\n", error_to_string(err)); |
|
|
1711 return -1; |
|
|
1712 } |
|
|
1713 return 0; |
|
|
1714 } |
|
|
1715 \end{verbatim} |
|
|
1716 \end{small} |
|
|
1717 |
|
|
1718 \chapter{RSA Public Key Cryptography} |
|
|
1719 \textbf{Note: } \textit{This chapter on PKCS \#1 RSA will replace the older chapter on RSA (The current chapter nine) in subsequent |
|
|
1720 releases of the library. Users are encouraged to stop using the LibTomCrypt style padding functions.} |
|
|
1721 |
|
|
1722 \section{PKCS \#1 Encryption} |
|
|
1723 |
|
|
1724 PKCS \#1 RSA Encryption amounts to OAEP padding of the input message followed by the modular exponentiation. As far as this portion of |
|
|
1725 the library is concerned we are only dealing with th OAEP padding of the message. |
|
|
1726 |
|
|
1727 \subsection{OAEP Encoding} |
|
|
1728 |
|
|
1729 \begin{alltt} |
|
|
1730 int pkcs_1_oaep_encode(const unsigned char *msg, unsigned long msglen, |
|
|
1731 const unsigned char *lparam, unsigned long lparamlen, |
|
|
1732 unsigned long modulus_bitlen, int hash_idx, |
|
|
1733 int prng_idx, prng_state *prng, |
|
|
1734 unsigned char *out, unsigned long *outlen); |
|
|
1735 \end{alltt} |
|
|
1736 |
|
|
1737 This accepts ``msg'' as input of length ``msglen'' which will be OAEP padded. The ``lparam'' variable is an additional system specific |
|
|
1738 tag that can be applied to the encoding. This is useful to identify which system encoded the message. If no variance is desired then |
|
|
1739 ``lparam'' can be set to \textbf{NULL}. |
|
|
1740 |
|
|
1741 OAEP encoding requires the length of the modulus in bits in order to calculate the size of the output. This is passed as the parameter |
|
|
1742 ``modulus\_bitlen''. ``hash\_idx'' is the index into the hash descriptor table of the hash desired. PKCS \#1 allows any hash to be |
|
|
1743 used but both the encoder and decoder must use the same hash in order for this to succeed. The size of hash output affects the maximum |
|
|
1744 sized input message. ``prng\_idx'' and ``prng'' are the random number generator arguments required to randomize the padding process. |
|
|
1745 The padded message is stored in ``out'' along with the length in ``outlen''. |
|
|
1746 |
|
|
1747 If $h$ is the length of the hash and $m$ the length of the modulus (both in octets) then the maximum payload for ``msg'' is |
|
|
1748 $m - 2h - 2$. For example, with a $1024$--bit RSA key and SHA--1 as the hash the maximum payload is $86$ bytes. |
|
|
1749 |
|
|
1750 Note that when the message is padded it still has not been RSA encrypted. You must pass the output of this function to |
|
|
1751 rsa\_exptmod() to encrypt it. |
|
|
1752 |
|
|
1753 \subsection{OAEP Decoding} |
|
|
1754 |
|
|
1755 \begin{alltt} |
|
|
1756 int pkcs_1_oaep_decode(const unsigned char *msg, unsigned long msglen, |
|
|
1757 const unsigned char *lparam, unsigned long lparamlen, |
|
|
1758 unsigned long modulus_bitlen, int hash_idx, |
|
|
1759 unsigned char *out, unsigned long *outlen); |
|
|
1760 \end{alltt} |
|
|
1761 |
|
|
1762 This function decodes an OAEP encoded message and outputs the original message that was passed to the OAEP encoder. ``msg'' is the |
|
|
1763 output of pkcs\_1\_oaep\_encode() of length ``msglen''. ``lparam'' is the same system variable passed to the OAEP encoder. If it does not |
|
|
1764 match what was used during encoding this function will not decode the packet. ``modulus\_bitlen'' is the size of the RSA modulus in bits |
|
|
1765 and must match what was used during encoding. Similarly the ``hash\_idx'' index into the hash descriptor table must match what was used |
|
|
1766 during encoding. |
|
|
1767 |
|
|
1768 If the function succeeds it decodes the OAEP encoded message into ``out'' of length ``outlen''. |
|
|
1769 |
|
|
1770 \section{PKCS \#1 Digital Signatures} |
|
|
1771 |
|
|
1772 \subsection{PSS Encoding} |
|
|
1773 PSS encoding is the second half of the PKCS \#1 standard which is padding to be applied to messages that are signed. |
|
|
1774 |
|
|
1775 \begin{alltt} |
|
|
1776 int pkcs_1_pss_encode(const unsigned char *msghash, unsigned long msghashlen, |
|
|
1777 unsigned long saltlen, int hash_idx, |
|
|
1778 int prng_idx, prng_state *prng, |
|
|
1779 unsigned long modulus_bitlen, |
|
|
1780 unsigned char *out, unsigned long *outlen); |
|
|
1781 \end{alltt} |
|
|
1782 |
|
|
1783 This function assumes the message to be PSS encoded has previously been hashed. The input hash ``msghash'' is of length |
|
|
1784 ``msghashlen''. PSS allows a variable length random salt (it can be zero length) to be introduced in the signature process. |
|
|
1785 ``hash\_idx'' is the index into the hash descriptor table of the hash to use. ``prng\_idx'' and ``prng'' are the random |
|
|
1786 number generator information required for the salt. |
|
|
1787 |
|
|
1788 Similar to OAEP encoding ``modulus\_bitlen'' is the size of the RSA modulus. It limits the size of the salt. If $m$ is the length |
|
|
1789 of the modulus $h$ the length of the hash output (in octets) then there can be $m - h - 2$ bytes of salt. |
|
|
1790 |
|
|
1791 This function does not actually sign the data it merely pads the hash of a message so that it can be processed by rsa\_exptmod(). |
|
|
1792 |
|
|
1793 \subsection{PSS Decoding} |
|
|
1794 |
|
|
1795 To decode a PSS encoded signature block you have to use the following. |
|
|
1796 |
|
|
1797 \begin{alltt} |
|
|
1798 int pkcs_1_pss_decode(const unsigned char *msghash, unsigned long msghashlen, |
|
|
1799 const unsigned char *sig, unsigned long siglen, |
|
|
1800 unsigned long saltlen, int hash_idx, |
|
|
1801 unsigned long modulus_bitlen, int *res); |
|
|
1802 \end{alltt} |
|
|
1803 This will decode the PSS encoded message in ``sig'' of length ``siglen'' and compare it to values in ``msghash'' of length |
|
|
1804 ``msghashlen''. If the block is a valid PSS block and the decoded hash equals the hash supplied ``res'' is set to non--zero. Otherwise, |
|
|
1805 it is set to zero. The rest of the parameters are as in the PSS encode call. |
|
|
1806 |
|
|
1807 It's important to use the same ``saltlen'' and hash for both encoding and decoding as otherwise the procedure will not work. |
|
|
1808 |
|
|
1809 \chapter{Password Based Cryptography} |
|
|
1810 \section{PKCS \#5} |
|
|
1811 In order to securely handle user passwords for the purposes of creating session keys and chaining IVs the PKCS \#5 was drafted. PKCS \#5 |
|
|
1812 is made up of two algorithms, Algorithm One and Algorithm Two. Algorithm One is the older fairly limited algorithm which has been implemented |
|
|
1813 for completeness. Algorithm Two is a bit more modern and more flexible to work with. |
|
|
1814 |
|
|
1815 \section{Algorithm One} |
|
|
1816 Algorithm One accepts as input a password, an 8--byte salt and an iteration counter. The iteration counter is meant to act as delay for |
|
|
1817 people trying to brute force guess the password. The higher the iteration counter the longer the delay. This algorithm also requires a hash |
|
|
1818 algorithm and produces an output no longer than the output of the hash. |
|
|
1819 |
|
|
1820 \begin{alltt} |
|
|
1821 int pkcs_5_alg1(const unsigned char *password, unsigned long password_len, |
|
|
1822 const unsigned char *salt, |
|
|
1823 int iteration_count, int hash_idx, |
|
|
1824 unsigned char *out, unsigned long *outlen) |
|
|
1825 \end{alltt} |
|
|
1826 Where ``password'' is the users password. Since the algorithm allows binary passwords you must also specify the length in ``password\_len''. |
|
|
1827 The ``salt'' is a fixed size 8--byte array which should be random for each user and session. The ``iteration\_count'' is the delay desired |
|
|
1828 on the password. The ``hash\_idx'' is the index of the hash you wish to use in the descriptor table. |
|
|
1829 |
|
|
1830 The output of length upto ``outlen'' is stored in ``out''. If ``outlen'' is initially larger than the size of the hash functions output |
|
|
1831 it is set to the number of bytes stored. If it is smaller than not all of the hash output is stored in ``out''. |
|
|
1832 |
|
|
1833 \section{Algorithm Two} |
|
|
1834 |
|
|
1835 Algorithm Two is the recommended algorithm for this task. It allows variable length salts and can produce outputs larger than the |
|
|
1836 hash functions output. As such it can easily be used to derive session keys for ciphers and MACs as well initial vectors as required |
|
|
1837 from a single password and invokation of this algorithm. |
|
|
1838 |
|
|
1839 \begin{alltt} |
|
|
1840 int pkcs_5_alg2(const unsigned char *password, unsigned long password_len, |
|
|
1841 const unsigned char *salt, unsigned long salt_len, |
|
|
1842 int iteration_count, int hash_idx, |
|
|
1843 unsigned char *out, unsigned long *outlen) |
|
|
1844 \end{alltt} |
|
|
1845 Where ``password'' is the users password. Since the algorithm allows binary passwords you must also specify the length in ``password\_len''. |
|
|
1846 The ``salt'' is an array of size ``salt\_len''. It should be random for each user and session. The ``iteration\_count'' is the delay desired |
|
|
1847 on the password. The ``hash\_idx'' is the index of the hash you wish to use in the descriptor table. The output of length upto |
|
|
1848 ``outlen'' is stored in ``out''. |
|
|
1849 |
|
|
1850 \begin{alltt} |
|
|
1851 /* demo to show how to make session state material from a password */ |
|
|
1852 #include <mycrypt.h> |
|
|
1853 int main(void) |
|
|
1854 \{ |
|
|
1855 unsigned char password[100], salt[100], |
|
|
1856 cipher_key[16], cipher_iv[16], |
|
|
1857 mac_key[16], outbuf[48]; |
|
|
1858 int err, hash_idx; |
|
|
1859 unsigned long outlen, password_len, salt_len; |
|
|
1860 |
|
|
1861 /* register hash and get it's idx .... */ |
|
|
1862 |
|
|
1863 /* get users password and make up a salt ... */ |
|
|
1864 |
|
|
1865 /* create the material (100 iterations in algorithm) */ |
|
|
1866 outlen = sizeof(outbuf); |
|
|
1867 if ((err = pkcs_5_alg2(password, password_len, salt, salt_len, |
|
|
1868 100, hash_idx, outbuf, &outlen)) != CRYPT_OK) \{ |
|
|
1869 /* error handle */ |
|
|
1870 \} |
|
|
1871 |
|
|
1872 /* now extract it */ |
|
|
1873 memcpy(cipher_key, outbuf, 16); |
|
|
1874 memcpy(cipher_iv, outbuf+16, 16); |
|
|
1875 memcpy(mac_key, outbuf+32, 16); |
|
|
1876 |
|
|
1877 /* use material (recall to store the salt in the output) */ |
|
|
1878 \} |
|
|
1879 \end{alltt} |
|
|
1880 |
|
|
1881 \chapter{RSA Routines} |
|
|
1882 |
|
|
1883 \textbf{Note: } \textit{This chapter has been marked for removal. In particular any function that uses the LibTomCrypt style |
|
|
1884 RSA padding (e.g. rsa\_pad() rsa\_signpad()) will be removed in the v0.96 release cycle. The functions like rsa\_make\_key() and |
|
|
1885 rsa\_exptmod() will stay but may be slightly modified. } |
|
|
1886 |
|
|
1887 \section{Background} |
|
|
1888 |
|
|
1889 RSA is a public key algorithm that is based on the inability to find the ``e-th'' root modulo a composite of unknown |
|
|
1890 factorization. Normally the difficulty of breaking RSA is associated with the integer factoring problem but they are |
|
|
1891 not strictly equivalent. |
|
|
1892 |
|
|
1893 The system begins with with two primes $p$ and $q$ and their product $N = pq$. The order or ``Euler totient'' of the |
|
|
1894 multiplicative sub-group formed modulo $N$ is given as $\phi(N) = (p - 1)(q - 1)$ which can be reduced to |
|
|
1895 $\mbox{lcm}(p - 1, q - 1)$. The public key consists of the composite $N$ and some integer $e$ such that |
|
|
1896 $\mbox{gcd}(e, \phi(N)) = 1$. The private key consists of the composite $N$ and the inverse of $e$ modulo $\phi(N)$ |
|
|
1897 often simply denoted as $de \equiv 1\mbox{ }(\mbox{mod }\phi(N))$. |
|
|
1898 |
|
|
1899 A person who wants to encrypt with your public key simply forms an integer (the plaintext) $M$ such that |
|
|
1900 $1 < M < N-2$ and computes the ciphertext $C = M^e\mbox{ }(\mbox{mod }N)$. Since finding the inverse exponent $d$ |
|
|
1901 given only $N$ and $e$ appears to be intractable only the owner of the private key can decrypt the ciphertext and compute |
|
|
1902 $C^d \equiv \left (M^e \right)^d \equiv M^1 \equiv M\mbox{ }(\mbox{mod }N)$. Similarly the owner of the private key |
|
|
1903 can sign a message by ``decrypting'' it. Others can verify it by ``encrypting'' it. |
|
|
1904 |
|
|
1905 Currently RSA is a difficult system to cryptanalyze provided that both primes are large and not close to each other. |
|
|
1906 Ideally $e$ should be larger than $100$ to prevent direct analysis. For example, if $e$ is three and you do not pad |
|
|
1907 the plaintext to be encrypted than it is possible that $M^3 < N$ in which case finding the cube-root would be trivial. |
|
|
1908 The most often suggested value for $e$ is $65537$ since it is large enough to make such attacks impossible and also well |
|
|
1909 designed for fast exponentiation (requires 16 squarings and one multiplication). |
|
|
1910 |
|
|
1911 It is important to pad the input to RSA since it has particular mathematical structure. For instance |
|
|
1912 $M_1^dM_2^d = (M_1M_2)^d$ which can be used to forge a signature. Suppose $M_3 = M_1M_2$ is a message you want |
|
|
1913 to have a forged signature for. Simply get the signatures for $M_1$ and $M_2$ on their own and multiply the result |
|
|
1914 together. Similar tricks can be used to deduce plaintexts from ciphertexts. It is important not only to sign |
|
|
1915 the hash of documents only but also to pad the inputs with data to remove such structure. |
|
|
1916 |
|
|
1917 \section{Core Functions} |
|
|
1918 |
|
|
1919 For RSA routines a single ``rsa\_key'' structure is used. To make a new RSA key call: |
|
|
1920 \index{rsa\_make\_key()} |
|
|
1921 \begin{verbatim} |
|
|
1922 int rsa_make_key(prng_state *prng, |
|
|
1923 int wprng, int size, |
|
|
1924 long e, rsa_key *key); |
|
|
1925 \end{verbatim} |
|
|
1926 |
|
|
1927 Where ``wprng'' is the index into the PRNG descriptor array. ``size'' is the size in bytes of the RSA modulus desired. |
|
|
1928 ``e'' is the encryption exponent desired, typical values are 3, 17, 257 and 65537. I suggest you stick with 65537 since its big |
|
|
1929 enough to prevent trivial math attacks and not super slow. ``key'' is where the key is placed. All keys must be at |
|
|
1930 least 128 bytes and no more than 512 bytes in size (\textit{that is from 1024 to 4096 bits}). |
|
|
1931 |
|
|
1932 Note that the ``rsa\_make\_key()'' function allocates memory at runtime when you make the key. Make sure to call |
|
|
1933 ``rsa\_free()'' (see below) when you are finished with the key. If ``rsa\_make\_key()'' fails it will automatically |
|
|
1934 free the ram allocated itself. |
|
|
1935 |
|
|
1936 There are three types of RSA keys. The types are {\bf PK\_PRIVATE\_OPTIMIZED}, {\bf PK\_PRIVATE} and {\bf PK\_PUBLIC}. The first |
|
|
1937 two are private keys where the ``optimized'' type uses the Chinese Remainder Theorem to speed up decryption/signatures. By |
|
|
1938 default all new keys are of the ``optimized'' type. The non-optimized private type is provided for backwards compatibility |
|
|
1939 as well as to save space since the optimized key requires about four times as much memory. |
|
|
1940 |
|
|
1941 To do raw work with the RSA function call: |
|
|
1942 \index{rsa\_exptmod()} |
|
|
1943 \begin{verbatim} |
|
|
1944 int rsa_exptmod(const unsigned char *in, unsigned long inlen, |
|
|
1945 unsigned char *out, unsigned long *outlen, |
|
|
1946 int which, rsa_key *key); |
|
|
1947 \end{verbatim} |
|
|
1948 This loads the bignum from ``in'' as a big endian word in the format PKCS specifies, raises it to either ``e'' or ``d'' and stores the result |
|
|
1949 in ``out'' and the size of the result in ``outlen''. ``which'' is set to {\bf PK\_PUBLIC} to use ``e'' |
|
|
1950 (i.e. for encryption/verifying) and set to {\bf PK\_PRIVATE} to use ``d'' as the exponent (i.e. for decrypting/signing). |
|
|
1951 |
|
|
1952 Note that this function does not perform padding on the input (as per PKCS). So if you send in ``0000001'' you will |
|
|
1953 get ``01'' back (when you do the opposite operation). Make sure you pad properly which usually involves setting the msb to |
|
|
1954 a non-zero value. |
|
|
1955 |
|
|
1956 \section{Packet Routines} |
|
|
1957 To encrypt or decrypt a symmetric key using RSA the following functions are provided. The idea is that you make up |
|
|
1958 a random symmetric key and use that to encode your message. By RSA encrypting the symmetric key you can send it to a |
|
|
1959 recipient who can RSA decrypt it and symmetrically decrypt the message. |
|
|
1960 \begin{verbatim} |
|
|
1961 int rsa_encrypt_key(const unsigned char *inkey, unsigned long inlen, |
|
|
1962 unsigned char *outkey, unsigned long *outlen, |
|
|
1963 prng_state *prng, int wprng, rsa_key *key); |
|
|
1964 \end{verbatim} |
|
|
1965 This function is used to RSA encrypt a symmetric to share with another user. The symmetric key and its length are |
|
|
1966 passed as ``inkey'' and ``inlen'' respectively. The symmetric key is limited to a range of 8 to 32 bytes |
|
|
1967 (\textit{64 to 256 bits}). The RSA encrypted packet is stored in ``outkey'' and will be of length ``outlen'' bytes. The |
|
|
1968 value of ``outlen'' must be originally set to the size of the output buffer. |
|
|
1969 |
|
|
1970 \begin{verbatim} |
|
|
1971 int rsa_decrypt_key(const unsigned char *in, unsigned long inlen, |
|
|
1972 unsigned char *outkey, unsigned long *keylen, |
|
|
1973 rsa_key *key); |
|
|
1974 \end{verbatim} |
|
|
1975 |
|
|
1976 This function will decrypt an RSA packet to retrieve the original symmetric key encrypted with rsa\_encrypt\_key(). |
|
|
1977 Similarly to sign or verify a hash of a message the following two messages are provided. The idea is to hash your message |
|
|
1978 then use these functions to RSA sign the hash. |
|
|
1979 \begin{verbatim} |
|
|
1980 int rsa_sign_hash(const unsigned char *in, unsigned long inlen, |
|
|
1981 unsigned char *out, unsigned long *outlen, |
|
|
1982 rsa_key *key); |
|
|
1983 |
|
|
1984 int rsa_verify_hash(const unsigned char *sig, unsigned long siglen, |
|
|
1985 const unsigned char *hash, int *stat, rsa_key *key); |
|
|
1986 \end{verbatim} |
|
|
1987 For ``rsa\_sign\_hash'' the input is intended to be the hash of a message the user wants to sign. The output is the |
|
|
1988 RSA signed packet which ``rsa\_verify\_hash'' can verify. For the verification function ``sig'' is the RSA signature |
|
|
1989 and ``hash'' is the hash of the message. The integer ``stat'' is set to non-zero if the signature is valid or zero |
|
|
1990 otherwise. |
|
|
1991 |
|
|
1992 To import/export RSA keys as a memory buffer (e.g. to store them to disk) call: |
|
|
1993 \begin{verbatim} |
|
|
1994 int rsa_export(unsigned char *out, unsigned long *outlen, |
|
|
1995 int type, rsa_key *key); |
|
|
1996 |
|
|
1997 int rsa_import(const unsigned char *in, unsigned long inlen, rsa_key *key); |
|
|
1998 \end{verbatim} |
|
|
1999 |
|
|
2000 The ``type'' parameter is {\bf PK\_PUBLIC}, {\bf PK\_PRIVATE} or {\bf PK\_PRIVATE\_OPTIMIZED} to export either a public or |
|
|
2001 private key. The latter type will export a key with the optimized parameters. To free the memory used by an RSA key call: |
|
|
2002 \index{rsa\_free()} |
|
|
2003 \begin{verbatim} |
|
|
2004 void rsa_free(rsa_key *key); |
|
|
2005 \end{verbatim} |
|
|
2006 |
|
|
2007 Note that if the key fails to ``rsa\_import()'' you do not have to free the memory allocated for it. |
|
|
2008 |
|
|
2009 \section{Remarks} |
|
|
2010 It is important that you match your RSA key size with the function you are performing. The internal padding for both |
|
|
2011 signatures and encryption triple the size of the plaintext. This means to encrypt or sign |
|
|
2012 a message of N bytes you must have a modulus of 1+3N bytes. Note that this doesn't affect the length of the plaintext |
|
|
2013 you pass into functions like rsa\_encrypt(). This restriction applies only to data that is passed through the |
|
|
2014 internal RSA routines directly directly. |
|
|
2015 |
|
|
2016 The following table gives the size requirements for various hashes. |
|
|
2017 \begin{center} |
|
|
2018 \begin{tabular}{|c|c|c|} |
|
|
2019 \hline Name & Size of Message Digest (bytes) & RSA Key Size (bits)\\ |
|
|
2020 \hline SHA-512 & 64 & 1544\\ |
|
|
2021 \hline SHA-384 & 48 & 1160 \\ |
|
|
2022 \hline SHA-256 & 32 & 776\\ |
|
|
2023 \hline TIGER-192 & 24 & 584\\ |
|
|
2024 \hline SHA-1 & 20 & 488\\ |
|
|
2025 \hline MD5 & 16 & 392\\ |
|
|
2026 \hline MD4 & 16 & 392\\ |
|
|
2027 \hline |
|
|
2028 \end{tabular} |
|
|
2029 \end{center} |
|
|
2030 |
|
|
2031 The symmetric ciphers will use at a maximum a 256-bit key which means at the least a 776-bit RSA key is |
|
|
2032 required to use all of the symmetric ciphers with the RSA routines. If you want to use any of the large size |
|
|
2033 message digests (SHA-512 or SHA-384) you will have to use a larger key. Or to be simple just make 2048-bit or larger |
|
|
2034 keys. None of the hashes will have problems with such key sizes. |
|
|
2035 |
|
|
2036 \chapter{Diffie-Hellman Key Exchange} |
|
|
2037 |
|
|
2038 \section{Background} |
|
|
2039 |
|
|
2040 Diffie-Hellman was the original public key system proposed. The system is based upon the group structure |
|
|
2041 of finite fields. For Diffie-Hellman a prime $p$ is chosen and a ``base'' $b$ such that $b^x\mbox{ }(\mbox{mod }p)$ |
|
|
2042 generates a large sub-group of prime order (for unique values of $x$). |
|
|
2043 |
|
|
2044 A secret key is an exponent $x$ and a public key is the value of $y \equiv g^x\mbox{ }(\mbox{mod }p)$. The term |
|
|
2045 ``discrete logarithm'' denotes the action of finding $x$ given only $y$, $g$ and $p$. The key exchange part of |
|
|
2046 Diffie-Hellman arises from the fact that two users A and B with keys $(A_x, A_y)$ and $(B_x, B_y)$ can exchange |
|
|
2047 a shared key $K \equiv B_y^{A_x} \equiv A_y^{B_x} \equiv g^{A_xB_x}\mbox{ }(\mbox{mod }p)$. |
|
|
2048 |
|
|
2049 From this public encryption and signatures can be developed. The trivial way to encrypt (for example) using a public key |
|
|
2050 $y$ is to perform the key exchange offline. The sender invents a key $k$ and its public copy |
|
|
2051 $k' \equiv g^k\mbox{ }(\mbox{mod }p)$ and uses $K \equiv k'^{A_x}\mbox{ }(\mbox{mod }p)$ as a key to encrypt |
|
|
2052 the message with. Typically $K$ would be sent to a one-way hash and the message digested used as a key in a |
|
|
2053 symmetric cipher. |
|
|
2054 |
|
|
2055 It is important that the order of the sub-group that $g$ generates not only be large but also prime. There are |
|
|
2056 discrete logarithm algorithms that take $\sqrt r$ time given the order $r$. The discrete logarithm can be computed |
|
|
2057 modulo each prime factor of $r$ and the results combined using the Chinese Remainder Theorem. In the cases where |
|
|
2058 $r$ is ``B-Smooth'' (e.g. all small factors or powers of small prime factors) the solution is trivial to find. |
|
|
2059 |
|
|
2060 To thwart such attacks the primes and bases in the library have been designed and fixed. Given a prime $p$ the order of |
|
|
2061 the sub-group generated is a large prime namely ${p - 1} \over 2$. Such primes are known as ``strong primes'' and the |
|
|
2062 smaller prime (e.g. the order of the base) are known as Sophie-Germaine primes. |
|
|
2063 |
|
|
2064 \section{Core Functions} |
|
|
2065 |
|
|
2066 This library also provides core Diffie-Hellman functions so you can negotiate keys over insecure mediums. The routines |
|
|
2067 provided are relatively easy to use and only take two function calls to negotiate a shared key. There is a structure |
|
|
2068 called ``dh\_key'' which stores the Diffie-Hellman key in a format these routines can use. The first routine is to |
|
|
2069 make a Diffie-Hellman private key pair: |
|
|
2070 \index{dh\_make\_key()} |
|
|
2071 \begin{verbatim} |
|
|
2072 int dh_make_key(prng_state *prng, int wprng, |
|
|
2073 int keysize, dh_key *key); |
|
|
2074 \end{verbatim} |
|
|
2075 The ``keysize'' is the size of the modulus you want in bytes. Currently support sizes are 96 to 512 bytes which correspond |
|
|
2076 to key sizes of 768 to 4096 bits. The smaller the key the faster it is to use however it will be less secure. When |
|
|
2077 specifying a size not explicitly supported by the library it will round {\em up} to the next key size. If the size is |
|
|
2078 above 512 it will return an error. So if you pass ``keysize == 32'' it will use a 768 bit key but if you pass |
|
|
2079 ``keysize == 20000'' it will return an error. The primes and generators used are built-into the library and were designed |
|
|
2080 to meet very specific goals. The primes are strong primes which means that if $p$ is the prime then |
|
|
2081 $p-1$ is equal to $2r$ where $r$ is a large prime. The bases are chosen to generate a group of order $r$ to prevent |
|
|
2082 leaking a bit of the key. This means the bases generate a very large prime order group which is good to make cryptanalysis |
|
|
2083 hard. |
|
|
2084 |
|
|
2085 The next two routines are for exporting/importing Diffie-Hellman keys in a binary format. This is useful for transport |
|
|
2086 over communication mediums. |
|
|
2087 |
|
|
2088 \index{dh\_export()} \index{dh\_import()} |
|
|
2089 \begin{verbatim} |
|
|
2090 int dh_export(unsigned char *out, unsigned long *outlen, |
|
|
2091 int type, dh_key *key); |
|
|
2092 |
|
|
2093 int dh_import(const unsigned char *in, unsigned long inlen, dh_key *key); |
|
|
2094 \end{verbatim} |
|
|
2095 |
|
|
2096 These two functions work just like the ``rsa\_export()'' and ``rsa\_import()'' functions except these work with |
|
|
2097 Diffie-Hellman keys. Its important to note you do not have to free the ram for a ``dh\_key'' if an import fails. You can free a |
|
|
2098 ``dh\_key'' using: |
|
|
2099 \begin{verbatim} |
|
|
2100 void dh_free(dh_key *key); |
|
|
2101 \end{verbatim} |
|
|
2102 After you have exported a copy of your public key (using {\bf PK\_PUBLIC} as ``type'') you can now create a shared secret |
|
|
2103 with the other user using: |
|
|
2104 \index{dh\_shared\_secret()} |
|
|
2105 \begin{verbatim} |
|
|
2106 int dh_shared_secret(dh_key *private_key, |
|
|
2107 dh_key *public_key, |
|
|
2108 unsigned char *out, unsigned long *outlen); |
|
|
2109 \end{verbatim} |
|
|
2110 |
|
|
2111 Where ``private\_key'' is the key you made and ``public\_key'' is the copy of the public key the other user sent you. The result goes |
|
|
2112 into ``out'' and the length into ``outlen''. If all went correctly the data in ``out'' should be identical for both parties. It is important to |
|
|
2113 note that the two keys have to be the same size in order for this to work. There is a function to get the size of a |
|
|
2114 key: |
|
|
2115 \index{dh\_get\_size()} |
|
|
2116 \begin{verbatim} |
|
|
2117 int dh_get_size(dh_key *key); |
|
|
2118 \end{verbatim} |
|
|
2119 This returns the size in bytes of the modulus chosen for that key. |
|
|
2120 |
|
|
2121 \subsection{Remarks on Usage} |
|
|
2122 Its important that you hash the shared key before trying to use it as a key for a symmetric cipher or something. An |
|
|
2123 example program that communicates over sockets, using MD5 and 1024-bit DH keys is\footnote{This function is a small example. It is suggested that proper packaging be used. For example, if the public key sent is truncated these routines will not detect that.}: |
|
|
2124 \newpage |
|
|
2125 \begin{small} |
|
|
2126 \begin{verbatim} |
|
|
2127 int establish_secure_socket(int sock, int mode, unsigned char *key, |
|
|
2128 prng_state *prng, int wprng) |
|
|
2129 { |
|
|
2130 unsigned char buf[4096], buf2[4096]; |
|
|
2131 unsigned long x, len; |
|
|
2132 int res, err, inlen; |
|
|
2133 dh_key mykey, theirkey; |
|
|
2134 |
|
|
2135 /* make up our private key */ |
|
|
2136 if ((err = dh_make_key(prng, wprng, 128, &mykey)) != CRYPT_OK) { |
|
|
2137 return err; |
|
|
2138 } |
|
|
2139 |
|
|
2140 /* export our key as public */ |
|
|
2141 x = sizeof(buf); |
|
|
2142 if ((err = dh_export(buf, &x, PK_PUBLIC, &mykey)) != CRYPT_OK) { |
|
|
2143 res = err; |
|
|
2144 goto done2; |
|
|
2145 } |
|
|
2146 |
|
|
2147 if (mode == 0) { |
|
|
2148 /* mode 0 so we send first */ |
|
|
2149 if (send(sock, buf, x, 0) != x) { |
|
|
2150 res = CRYPT_ERROR; |
|
|
2151 goto done2; |
|
|
2152 } |
|
|
2153 |
|
|
2154 /* get their key */ |
|
|
2155 if ((inlen = recv(sock, buf2, sizeof(buf2), 0)) <= 0) { |
|
|
2156 res = CRYPT_ERROR; |
|
|
2157 goto done2; |
|
|
2158 } |
|
|
2159 } else { |
|
|
2160 /* mode >0 so we send second */ |
|
|
2161 if ((inlen = recv(sock, buf2, sizeof(buf2), 0)) <= 0) { |
|
|
2162 res = CRYPT_ERROR; |
|
|
2163 goto done2; |
|
|
2164 } |
|
|
2165 |
|
|
2166 if (send(sock, buf, x, 0) != x) { |
|
|
2167 res = CRYPT_ERROR; |
|
|
2168 goto done2; |
|
|
2169 } |
|
|
2170 } |
|
|
2171 |
|
|
2172 if ((err = dh_import(buf2, inlen, &theirkey)) != CRYPT_OK) { |
|
|
2173 res = err; |
|
|
2174 goto done2; |
|
|
2175 } |
|
|
2176 |
|
|
2177 /* make shared secret */ |
|
|
2178 x = sizeof(buf); |
|
|
2179 if ((err = dh_shared_secret(&mykey, &theirkey, buf, &x)) != CRYPT_OK) { |
|
|
2180 res = err; |
|
|
2181 goto done; |
|
|
2182 } |
|
|
2183 |
|
|
2184 /* hash it */ |
|
|
2185 len = 16; /* default is MD5 so "key" must be at least 16 bytes long */ |
|
|
2186 if ((err = hash_memory(find_hash("md5"), buf, x, key, &len)) != CRYPT_OK) { |
|
|
2187 res = err; |
|
|
2188 goto done; |
|
|
2189 } |
|
|
2190 |
|
|
2191 /* clean up and return */ |
|
|
2192 res = CRYPT_OK; |
|
|
2193 done: |
|
|
2194 dh_free(&theirkey); |
|
|
2195 done2: |
|
|
2196 dh_free(&mykey); |
|
|
2197 zeromem(buf, sizeof(buf)); |
|
|
2198 zeromem(buf2, sizeof(buf2)); |
|
|
2199 return res; |
|
|
2200 } |
|
|
2201 \end{verbatim} |
|
|
2202 \end{small} |
|
|
2203 \newpage |
|
|
2204 \subsection{Remarks on The Snippet} |
|
|
2205 When the above code snippet is done (assuming all went well) their will be a shared 128-bit key in the ``key'' array |
|
|
2206 passed to ``establish\_secure\_socket()''. |
|
|
2207 |
|
|
2208 \section{Other Diffie-Hellman Functions} |
|
|
2209 In order to test the Diffie-Hellman function internal workings (e.g. the primes and bases) their is a test function made |
|
|
2210 available: |
|
|
2211 \index{dh\_test()} |
|
|
2212 \begin{verbatim} |
|
|
2213 int dh_test(void); |
|
|
2214 \end{verbatim} |
|
|
2215 |
|
|
2216 This function returns {\bf CRYPT\_OK} if the bases and primes in the library are correct. There is one last helper |
|
|
2217 function: |
|
|
2218 \index{dh\_sizes()} |
|
|
2219 \begin{verbatim} |
|
|
2220 void dh_sizes(int *low, int *high); |
|
|
2221 \end{verbatim} |
|
|
2222 Which stores the smallest and largest key sizes support into the two variables. |
|
|
2223 |
|
|
2224 \section{DH Packet} |
|
|
2225 Similar to the RSA related functions there are functions to encrypt or decrypt symmetric keys using the DH public key |
|
|
2226 algorithms. |
|
|
2227 \begin{verbatim} |
|
|
2228 int dh_encrypt_key(const unsigned char *inkey, unsigned long keylen, |
|
|
2229 unsigned char *out, unsigned long *len, |
|
|
2230 prng_state *prng, int wprng, int hash, |
|
|
2231 dh_key *key); |
|
|
2232 |
|
|
2233 int dh_decrypt_key(const unsigned char *in, unsigned long inlen, |
|
|
2234 unsigned char *outkey, unsigned long *keylen, |
|
|
2235 dh_key *key); |
|
|
2236 \end{verbatim} |
|
|
2237 Where ``inkey'' is an input symmetric key of no more than 32 bytes. Essentially these routines created a random public key |
|
|
2238 and find the hash of the shared secret. The message digest is than XOR'ed against the symmetric key. All of the |
|
|
2239 required data is placed in ``out'' by ``dh\_encrypt\_key()''. The hash must produce a message digest at least as large |
|
|
2240 as the symmetric key you are trying to share. |
|
|
2241 |
|
|
2242 Similar to the RSA system you can sign and verify a hash of a message. |
|
|
2243 \begin{verbatim} |
|
|
2244 int dh_sign_hash(const unsigned char *in, unsigned long inlen, |
|
|
2245 unsigned char *out, unsigned long *outlen, |
|
|
2246 prng_state *prng, int wprng, dh_key *key); |
|
|
2247 |
|
|
2248 int dh_verify_hash(const unsigned char *sig, unsigned long siglen, |
|
|
2249 const unsigned char *hash, unsigned long hashlen, |
|
|
2250 int *stat, dh_key *key); |
|
|
2251 \end{verbatim} |
|
|
2252 |
|
|
2253 The ``dh\_sign\_hash'' function signs the message hash in ``in'' of length ``inlen'' and forms a DH packet in ``out''. |
|
|
2254 The ``dh\_verify\_hash'' function verifies the DH signature in ``sig'' against the hash in ``hash''. It sets ``stat'' |
|
|
2255 to non-zero if the signature passes or zero if it fails. |
|
|
2256 |
|
|
2257 \chapter{Elliptic Curve Cryptography} |
|
|
2258 |
|
|
2259 \section{Background} |
|
|
2260 The library provides a set of core ECC functions as well that are designed to be the Elliptic Curve analogy of all of the |
|
|
2261 Diffie-Hellman routines in the previous chapter. Elliptic curves (of certain forms) have the benefit that they are harder |
|
|
2262 to attack (no sub-exponential attacks exist unlike normal DH crypto) in fact the fastest attack requires the square root |
|
|
2263 of the order of the base point in time. That means if you use a base point of order $2^{192}$ (which would represent a |
|
|
2264 192-bit key) then the work factor is $2^{96}$ in order to find the secret key. |
|
|
2265 |
|
|
2266 The curves in this library are taken from the following website: |
|
|
2267 \begin{verbatim} |
|
|
2268 http://csrc.nist.gov/cryptval/dss.htm |
|
|
2269 \end{verbatim} |
|
|
2270 |
|
|
2271 They are all curves over the integers modulo a prime. The curves have the basic equation that is: |
|
|
2272 \begin{equation} |
|
|
2273 y^2 = x^3 - 3x + b\mbox{ }(\mbox{mod }p) |
|
|
2274 \end{equation} |
|
|
2275 |
|
|
2276 The variable $b$ is chosen such that the number of points is nearly maximal. In fact the order of the base points $\beta$ |
|
|
2277 provided are very close to $p$ that is $\vert \vert \phi(\beta) \vert \vert \approx \vert \vert p \vert \vert$. The curves |
|
|
2278 range in order from $\approx 2^{192}$ points to $\approx 2^{521}$. According to the source document any key size greater |
|
|
2279 than or equal to 256-bits is sufficient for long term security. |
|
|
2280 |
|
|
2281 \section{Core Functions} |
|
|
2282 |
|
|
2283 Like the DH routines there is a key structure ``ecc\_key'' used by the functions. There is a function to make a key: |
|
|
2284 \index{ecc\_make\_key()} |
|
|
2285 \begin{verbatim} |
|
|
2286 int ecc_make_key(prng_state *prng, int wprng, |
|
|
2287 int keysize, ecc_key *key); |
|
|
2288 \end{verbatim} |
|
|
2289 |
|
|
2290 The ``keysize'' is the size of the modulus in bytes desired. Currently directly supported values are 20, 24, 28, 32, 48 and 65 bytes which |
|
|
2291 correspond to key sizes of 160, 192, 224, 256, 384 and 521 bits respectively. If you pass a key size that is between any key size |
|
|
2292 it will round the keysize up to the next available one. The rest of the parameters work like they do in the ``dh\_make\_key()'' function. |
|
|
2293 To free the ram allocated by a key call: |
|
|
2294 \index{ecc\_free()} |
|
|
2295 \begin{verbatim} |
|
|
2296 void ecc_free(ecc_key *key); |
|
|
2297 \end{verbatim} |
|
|
2298 |
|
|
2299 To import and export a key there are: |
|
|
2300 \index{ecc\_export()} |
|
|
2301 \index{ecc\_import()} |
|
|
2302 \begin{verbatim} |
|
|
2303 int ecc_export(unsigned char *out, unsigned long *outlen, |
|
|
2304 int type, ecc_key *key); |
|
|
2305 |
|
|
2306 int ecc_import(const unsigned char *in, unsigned long inlen, ecc_key *key); |
|
|
2307 \end{verbatim} |
|
|
2308 These two work exactly like there DH counterparts. Finally when you share your public key you can make a shared secret |
|
|
2309 with: |
|
|
2310 \index{ecc\_shared\_secret()} |
|
|
2311 \begin{verbatim} |
|
|
2312 int ecc_shared_secret(ecc_key *private_key, |
|
|
2313 ecc_key *public_key, |
|
|
2314 unsigned char *out, unsigned long *outlen); |
|
|
2315 \end{verbatim} |
|
|
2316 Which works exactly like the DH counterpart, the ``private\_key'' is your own key and ``public\_key'' is the key the other |
|
|
2317 user sent you. Note that this function stores both $x$ and $y$ co-ordinates of the shared |
|
|
2318 elliptic point. You should hash the output to get a shared key in a more compact and useful form (most of the entropy is |
|
|
2319 in $x$ anyways). Both keys have to be the same size for this to work, to help there is a function to get the size in bytes |
|
|
2320 of a key. |
|
|
2321 \index{ecc\_get\_size()} |
|
|
2322 \begin{verbatim} |
|
|
2323 int ecc_get_size(ecc_key *key); |
|
|
2324 \end{verbatim} |
|
|
2325 |
|
|
2326 To test the ECC routines and to get the minimum and maximum key sizes there are these two functions: |
|
|
2327 \index{ecc\_test()} |
|
|
2328 \begin{verbatim} |
|
|
2329 int ecc_test(void); |
|
|
2330 void ecc_sizes(int *low, int *high); |
|
|
2331 \end{verbatim} |
|
|
2332 Which both work like their DH counterparts. |
|
|
2333 |
|
|
2334 \section{ECC Packet} |
|
|
2335 Similar to the RSA API there are two functions which encrypt and decrypt symmetric keys using the ECC public key |
|
|
2336 algorithms. |
|
|
2337 \begin{verbatim} |
|
|
2338 int ecc_encrypt_key(const unsigned char *inkey, unsigned long keylen, |
|
|
2339 unsigned char *out, unsigned long *len, |
|
|
2340 prng_state *prng, int wprng, int hash, |
|
|
2341 ecc_key *key); |
|
|
2342 |
|
|
2343 int ecc_decrypt_key(const unsigned char *in, unsigned long inlen, |
|
|
2344 unsigned char *outkey, unsigned long *keylen, |
|
|
2345 ecc_key *key); |
|
|
2346 \end{verbatim} |
|
|
2347 |
|
|
2348 Where ``inkey'' is an input symmetric key of no more than 32 bytes. Essentially these routines created a random public key |
|
|
2349 and find the hash of the shared secret. The message digest is than XOR'ed against the symmetric key. All of the required |
|
|
2350 data is placed in ``out'' by ``ecc\_encrypt\_key()''. The hash chosen must produce a message digest at least as large |
|
|
2351 as the symmetric key you are trying to share. |
|
|
2352 |
|
|
2353 There are also functions to sign and verify the hash of a message. |
|
|
2354 \begin{verbatim} |
|
|
2355 int ecc_sign_hash(const unsigned char *in, unsigned long inlen, |
|
|
2356 unsigned char *out, unsigned long *outlen, |
|
|
2357 prng_state *prng, int wprng, ecc_key *key); |
|
|
2358 |
|
|
2359 int ecc_verify_hash(const unsigned char *sig, unsigned long siglen, |
|
|
2360 const unsigned char *hash, unsigned long hashlen, |
|
|
2361 int *stat, ecc_key *key); |
|
|
2362 \end{verbatim} |
|
|
2363 |
|
|
2364 The ``ecc\_sign\_hash'' function signs the message hash in ``in'' of length ``inlen'' and forms a ECC packet in ``out''. |
|
|
2365 The ``ecc\_verify\_hash'' function verifies the ECC signature in ``sig'' against the hash in ``hash''. It sets ``stat'' |
|
|
2366 to non-zero if the signature passes or zero if it fails. |
|
|
2367 |
|
|
2368 |
|
|
2369 \section{ECC Keysizes} |
|
|
2370 With ECC if you try and sign a hash that is bigger than your ECC key you can run into problems. The math will still work |
|
|
2371 and in effect the signature will still work. With ECC keys the strength of the signature is limited by the size of |
|
|
2372 the hash or the size of they key, whichever is smaller. For example, if you sign with SHA256 and a ECC-160 key in effect |
|
|
2373 you have 160-bits of security (e.g. as if you signed with SHA-1). |
|
|
2374 |
|
|
2375 The library will not warn you if you make this mistake so it is important to check yourself before using the |
|
|
2376 signatures. |
|
|
2377 |
|
|
2378 \chapter{Digital Signature Algorithm} |
|
|
2379 \section{Introduction} |
|
|
2380 The Digital Signature Algorithm (or DSA) is a variant of the ElGamal Signature scheme which has been modified to |
|
|
2381 reduce the bandwidth of a signature. For example, to have ``80-bits of security'' with ElGamal you need a group of |
|
|
2382 order at least 1024-bits. With DSA you need a group of order at least 160-bits. By comparison the ElGamal signature |
|
|
2383 would require at least 256 bytes where as the DSA signature would require only at least 40 bytes. |
|
|
2384 |
|
|
2385 The API for the DSA is essentially the same as the other PK algorithms. Except in the case of DSA no encryption or |
|
|
2386 decryption routines are provided. |
|
|
2387 |
|
|
2388 \section{Key Generation} |
|
|
2389 To make a DSA key you must call the following function |
|
|
2390 \begin{verbatim} |
|
|
2391 int dsa_make_key(prng_state *prng, int wprng, |
|
|
2392 int group_size, int modulus_size, |
|
|
2393 dsa_key *key); |
|
|
2394 \end{verbatim} |
|
|
2395 The variable ``prng'' is an active PRNG state and ``wprng'' the index to the descriptor. ``group\_size'' and |
|
|
2396 ``modulus\_size'' control the difficulty of forging a signature. Both parameters are in bytes. The larger the |
|
|
2397 ``group\_size'' the more difficult a forgery becomes upto a limit. The value of $group\_size$ is limited by |
|
|
2398 $15 < group\_size < 1024$ and $modulus\_size - group\_size < 512$. Suggested values for the pairs are as follows. |
|
|
2399 |
|
|
2400 \begin{center} |
|
|
2401 \begin{tabular}{|c|c|c|} |
|
|
2402 \hline \textbf{Bits of Security} & \textbf{group\_size} & \textbf{modulus\_size} \\ |
|
|
2403 \hline 80 & 20 & 128 \\ |
|
|
2404 \hline 120 & 30 & 256 \\ |
|
|
2405 \hline 140 & 35 & 384 \\ |
|
|
2406 \hline 160 & 40 & 512 \\ |
|
|
2407 \hline |
|
|
2408 \end{tabular} |
|
|
2409 \end{center} |
|
|
2410 |
|
|
2411 When you are finished with a DSA key you can call the following function to free the memory used. |
|
|
2412 \begin{verbatim} |
|
|
2413 void dsa_free(dsa_key *key); |
|
|
2414 \end{verbatim} |
|
|
2415 |
|
|
2416 \section{Key Verification} |
|
|
2417 Each DSA key is composed of the following variables. |
|
|
2418 |
|
|
2419 \begin{enumerate} |
|
|
2420 \item $q$ a small prime of magnitude $256^{group\_size}$. |
|
|
2421 \item $p = qr + 1$ a large prime of magnitude $256^{modulus\_size}$ where $r$ is a random even integer. |
|
|
2422 \item $g = h^r \mbox{ (mod }p\mbox{)}$ a generator of order $q$ modulo $p$. $h$ can be any non-trivial random |
|
|
2423 value. For this library they start at $h = 2$ and step until $g$ is not $1$. |
|
|
2424 \item $x$ a random secret (the secret key) in the range $1 < x < q$ |
|
|
2425 \item $y = g^x \mbox{ (mod }p\mbox{)}$ the public key. |
|
|
2426 \end{enumerate} |
|
|
2427 |
|
|
2428 A DSA key is considered valid if it passes all of the following tests. |
|
|
2429 |
|
|
2430 \begin{enumerate} |
|
|
2431 \item $q$ must be prime. |
|
|
2432 \item $p$ must be prime. |
|
|
2433 \item $g$ cannot be one of $\lbrace -1, 0, 1 \rbrace$ (modulo $p$). |
|
|
2434 \item $g$ must be less than $p$. |
|
|
2435 \item $(p-1) \equiv 0 \mbox{ (mod }q\mbox{)}$. |
|
|
2436 \item $g^q \equiv 1 \mbox{ (mod }p\mbox{)}$. |
|
|
2437 \item $1 < y < p - 1$ |
|
|
2438 \item $y^q \equiv 1 \mbox{ (mod }p\mbox{)}$. |
|
|
2439 \end{enumerate} |
|
|
2440 |
|
|
2441 Tests one and two ensure that the values will at least form a field which is required for the signatures to |
|
|
2442 function. Tests three and four ensure that the generator $g$ is not set to a trivial value which would make signature |
|
|
2443 forgery easier. Test five ensures that $q$ divides the order of multiplicative sub-group of $\Z/p\Z$. Test six |
|
|
2444 ensures that the generator actually generates a prime order group. Tests seven and eight ensure that the public key |
|
|
2445 is within range and belongs to a group of prime order. Note that test eight does not prove that $g$ generated $y$ only |
|
|
2446 that $y$ belongs to a multiplicative sub-group of order $q$. |
|
|
2447 |
|
|
2448 The following function will perform these tests. |
|
|
2449 |
|
|
2450 \begin{verbatim} |
|
|
2451 int dsa_verify_key(dsa_key *key, int *stat); |
|
|
2452 \end{verbatim} |
|
|
2453 |
|
|
2454 This will test ``key'' and store the result in ``stat''. If the result is $stat = 0$ the DSA key failed one of the tests |
|
|
2455 and should not be used at all. If the result is $stat = 1$ the DSA key is valid (as far as valid mathematics are concerned). |
|
|
2456 |
|
|
2457 |
|
|
2458 |
|
|
2459 \section{Signatures} |
|
|
2460 To generate a DSA signature call the following function |
|
|
2461 |
|
|
2462 \begin{verbatim} |
|
|
2463 int dsa_sign_hash(const unsigned char *in, unsigned long inlen, |
|
|
2464 unsigned char *out, unsigned long *outlen, |
|
|
2465 prng_state *prng, int wprng, dsa_key *key); |
|
|
2466 \end{verbatim} |
|
|
2467 |
|
|
2468 Which will sign the data in ``in'' of length ``inlen'' bytes. The signature is stored in ``out'' and the size |
|
|
2469 of the signature in ``outlen''. If the signature is longer than the size you initially specify in ``outlen'' nothing |
|
|
2470 is stored and the function returns an error code. The DSA ``key'' must be of the \textbf{PK\_PRIVATE} persuasion. |
|
|
2471 |
|
|
2472 To verify a hash created with that function use the following function |
|
|
2473 |
|
|
2474 \begin{verbatim} |
|
|
2475 int dsa_verify_hash(const unsigned char *sig, unsigned long siglen, |
|
|
2476 const unsigned char *hash, unsigned long inlen, |
|
|
2477 int *stat, dsa_key *key); |
|
|
2478 \end{verbatim} |
|
|
2479 Which will verify the data in ``hash'' of length ``inlen'' against the signature stored in ``sig'' of length ``siglen''. |
|
|
2480 It will set ``stat'' to $1$ if the signature is valid, otherwise it sets ``stat'' to $0$. |
|
|
2481 |
|
|
2482 \section{Import and Export} |
|
|
2483 |
|
|
2484 To export a DSA key so that it can be transported use the following function |
|
|
2485 \begin{verbatim} |
|
|
2486 int dsa_export(unsigned char *out, unsigned long *outlen, |
|
|
2487 int type, |
|
|
2488 dsa_key *key); |
|
|
2489 \end{verbatim} |
|
|
2490 This will export the DSA ``key'' to the buffer ``out'' and set the length in ``outlen'' (which must have been previously |
|
|
2491 initialized to the maximum buffer size). The ``type`` variable may be either \textbf{PK\_PRIVATE} or \textbf{PK\_PUBLIC} |
|
|
2492 depending on whether you want to export a private or public copy of the DSA key. |
|
|
2493 |
|
|
2494 To import an exported DSA key use the following function |
|
|
2495 |
|
|
2496 \begin{verbatim} |
|
|
2497 int dsa_import(const unsigned char *in, unsigned long inlen, |
|
|
2498 dsa_key *key); |
|
|
2499 \end{verbatim} |
|
|
2500 |
|
|
2501 This will import the DSA key from the buffer ``in'' of length ``inlen'' to the ``key''. If the process fails the function |
|
|
2502 will automatically free all of the heap allocated in the process (you don't have to call dsa\_free()). |
|
|
2503 |
|
|
2504 \chapter{Public Keyrings} |
|
|
2505 \section{Introduction} |
|
|
2506 In order to simplify the usage of the public key algorithms a set of keyring routines have been developed. They let the |
|
|
2507 developer manage asymmetric keys by providing load, save, export, import routines as well as encrypt, decrypt, sign, verify |
|
|
2508 routines in a unified API. That is all three types of PK systems can be used within the same keyring with the same API. |
|
|
2509 |
|
|
2510 To define types of keys there are four enumerations used globaly: |
|
|
2511 \begin{verbatim} |
|
|
2512 enum { |
|
|
2513 NON_KEY=0, |
|
|
2514 RSA_KEY, |
|
|
2515 DH_KEY, |
|
|
2516 ECC_KEY |
|
|
2517 }; |
|
|
2518 \end{verbatim} |
|
|
2519 |
|
|
2520 To make use of the system the developer has to know how link-lists work. The main structure that the keyring routines use |
|
|
2521 is the ``pk\_key'' defined as: |
|
|
2522 \begin{small} |
|
|
2523 \begin{verbatim} |
|
|
2524 typedef struct Pk_key { |
|
|
2525 int key_type, /* PUBLIC, PRIVATE, PRIVATE_OPTIMIZED */ |
|
|
2526 system; /* RSA, ECC or DH ? */ |
|
|
2527 |
|
|
2528 char name[MAXLEN], /* various info's about this key */ |
|
|
2529 email[MAXLEN], |
|
|
2530 description[MAXLEN]; |
|
|
2531 |
|
|
2532 unsigned long ID; /* CRC32 of the name/email/description together */ |
|
|
2533 |
|
|
2534 _pk_key key; |
|
|
2535 |
|
|
2536 struct Pk_key *next; /* linked list chain */ |
|
|
2537 } pk_key; |
|
|
2538 \end{verbatim} |
|
|
2539 \end{small} |
|
|
2540 |
|
|
2541 The list is chained via the ``next'' member and terminated with the node of the list that has ``system'' equal to |
|
|
2542 {\bf NON\_KEY}. |
|
|
2543 |
|
|
2544 \section{The Keyring API} |
|
|
2545 To initialize a blank keyring the function ``kr\_init()'' is used. |
|
|
2546 \begin{verbatim} |
|
|
2547 int kr_init(pk_key **pk); |
|
|
2548 \end{verbatim} |
|
|
2549 You pass it a pointer to a pointer of type ``pk\_key'' where it will allocate ram for one node of the keyring and sets the |
|
|
2550 pointer. |
|
|
2551 |
|
|
2552 Now instead of calling the PK specific ``make\_key'' functions there is one function that can make all three types of keys. |
|
|
2553 \begin{verbatim} |
|
|
2554 int kr_make_key(pk_key *pk, prng_state *prng, int wprng, |
|
|
2555 int system, int keysize, const char *name, |
|
|
2556 const char *email, const char *description); |
|
|
2557 \end{verbatim} |
|
|
2558 The ``name'', ``email'' and ``description'' parameters are simply little pieces of information that you can tag along with a |
|
|
2559 key. They can each be either blank or any string less than 256 bytes. ``system'' is one of the enumeration elements, that |
|
|
2560 is {\bf RSA\_KEY}, {\bf DH\_KEY} or {\bf ECC\_KEY}. ``keysize'' is the size of the key you desire which is regulated by |
|
|
2561 the individual systems, for example, RSA keys are limited in keysize from 128 to 512 bytes. |
|
|
2562 |
|
|
2563 To find keys along a keyring there are two functions provided: |
|
|
2564 \begin{verbatim} |
|
|
2565 pk_key *kr_find(pk_key *pk, unsigned long ID); |
|
|
2566 |
|
|
2567 pk_key *kr_find_name(pk_key *pk, const char *name); |
|
|
2568 \end{verbatim} |
|
|
2569 The first searches by the 32-bit ID provided and the latter checks the name against the keyring. They both return a pointer |
|
|
2570 to the node in the ring of a match or {\bf NULL} if no match is found. |
|
|
2571 |
|
|
2572 To export or import a single node of a keyring the two functions are provided: |
|
|
2573 \begin{verbatim} |
|
|
2574 int kr_export(pk_key *pk, unsigned long ID, int key_type, |
|
|
2575 unsigned char *out, unsigned long *outlen); |
|
|
2576 |
|
|
2577 int kr_import(pk_key *pk, const unsigned char *in); |
|
|
2578 \end{verbatim} |
|
|
2579 The export function exports the key with an ID provided and of a specific type much like the normal PK export routines. The |
|
|
2580 ``key\_type'' is one of {\bf PK\_PUBLIC} or {\bf PK\_PRIVATE}. In this function with RSA keys the type |
|
|
2581 {\bf PK\_PRIVATE\_OPTIMIZED} is the same as the {\bf PK\_PRIVATE} type. The import function will read in a packet and |
|
|
2582 add it to the keyring. |
|
|
2583 |
|
|
2584 To load and save whole keyrings from disk: |
|
|
2585 \begin{verbatim} |
|
|
2586 int kr_load(pk_key **pk, FILE *in, symmetric_CTR *ctr); |
|
|
2587 |
|
|
2588 int kr_save(pk_key *pk, FILE *out, symmetric_CTR *ctr); |
|
|
2589 \end{verbatim} |
|
|
2590 Both take file pointers to allow the user to pre-append data to the stream. The ``ctr'' parameter should be setup with |
|
|
2591 ``ctr\_start'' or set to NULL. This parameter lets the user encrypt the keyring as its written to disk, if it is set |
|
|
2592 to NULL the data is written without being encrypted. The load function assumes the list has not been initialized yet |
|
|
2593 and will reset the pointer given to it. |
|
|
2594 |
|
|
2595 There are the four encrypt, decrypt, sign and verify functions as well |
|
|
2596 \begin{verbatim} |
|
|
2597 int kr_encrypt_key(pk_key *pk, unsigned long ID, |
|
|
2598 const unsigned char *in, unsigned long inlen, |
|
|
2599 unsigned char *out, unsigned long *outlen, |
|
|
2600 prng_state *prng, int wprng, int hash); |
|
|
2601 |
|
|
2602 int kr_decrypt_key(pk_key *pk, const unsigned char *in, |
|
|
2603 unsigned char *out, unsigned long *outlen); |
|
|
2604 \end{verbatim} |
|
|
2605 |
|
|
2606 The kr\_encrypt\_key() routine is designed to encrypt a symmetric key with a specified users public key. The symmetric |
|
|
2607 key is then used with a block cipher to encode the message. The recipient can call kr\_decrypt\_key() to get the original |
|
|
2608 symmetric key back and decode the message. The hash specified must produce a message digest longer than symmetric key |
|
|
2609 provided. |
|
|
2610 |
|
|
2611 \begin{verbatim} |
|
|
2612 int kr_sign_hash(pk_key *pk, unsigned long ID, |
|
|
2613 const unsigned char *in, unsigned long inlen, |
|
|
2614 unsigned char *out, unsigned long *outlen, |
|
|
2615 prng_state *prng, int wprng); |
|
|
2616 |
|
|
2617 int kr_verify_hash(pk_key *pk, const unsigned char *in, |
|
|
2618 const unsigned char *hash, unsigned long hashlen, |
|
|
2619 int *stat); |
|
|
2620 \end{verbatim} |
|
|
2621 |
|
|
2622 Similar to the two previous these are used to sign a message digest or verify one. This requires hashing the message |
|
|
2623 first then passing the output in. |
|
|
2624 |
|
|
2625 To delete keys and clear rings there are: |
|
|
2626 \begin{verbatim} |
|
|
2627 int kr_del(pk_key **_pk, unsigned long ID); |
|
|
2628 int kr_clear(pk_key **pk); |
|
|
2629 \end{verbatim} |
|
|
2630 ``kr\_del'' will try to remove a key with a given ID from the ring and ``kr\_clear'' will completely empty a list and free |
|
|
2631 the memory associated with it. Below is small example using the keyring API: |
|
|
2632 |
|
|
2633 \begin{small} |
|
|
2634 \begin{verbatim} |
|
|
2635 #include <mycrypt.h> |
|
|
2636 int main(void) |
|
|
2637 { |
|
|
2638 pk_key *kr; |
|
|
2639 unsigned char buf[4096], buf2[4096]; |
|
|
2640 unsigned long len; |
|
|
2641 int err; |
|
|
2642 |
|
|
2643 /* make a new list */ |
|
|
2644 if ((err = kr_init(&kr)) != CRYPT_OK) { |
|
|
2645 printf("kr_init: %s\n", error_to_string(err)); |
|
|
2646 exit(-1); |
|
|
2647 } |
|
|
2648 |
|
|
2649 /* add a key to it */ |
|
|
2650 register_prng(&sprng_desc); |
|
|
2651 if ((err = kr_make_key(kr, NULL, find_prng("sprng"), RSA_KEY, 128, |
|
|
2652 "TomBot", "[email protected]", "test key")) == CRYPT_OK) { |
|
|
2653 printf("kr_make_key: %s\n", error_to_string(err)); |
|
|
2654 exit(-1); |
|
|
2655 } |
|
|
2656 |
|
|
2657 /* export the first key */ |
|
|
2658 len = sizeof(buf); |
|
|
2659 if ((err = kr_export(kr, kr->ID, PK_PRIVATE, buf, &len)) != CRYPT_OK) { |
|
|
2660 printf("kr_export: %s\n", error_to_string(err)); |
|
|
2661 exit(-1); |
|
|
2662 } |
|
|
2663 |
|
|
2664 /* ... */ |
|
|
2665 } |
|
|
2666 \end{verbatim} |
|
|
2667 \end{small} |
|
|
2668 |
|
|
2669 \chapter{$GF(2^w)$ Math Routines} |
|
|
2670 |
|
|
2671 The library provides a set of polynomial-basis $GF(2^w)$ routines to help facilitate algorithms such as ECC over such |
|
|
2672 fields. Note that the current implementation of ECC in the library is strictly over the integers only. The routines |
|
|
2673 are simple enough to use for other purposes outside of ECC. |
|
|
2674 |
|
|
2675 At the heart of all of the GF routines is the data type ``gf\_int'. It is simply a type definition for an array of |
|
|
2676 $L$ 32-bit words. You can configure the maximum size $L$ of the ``gf\_int'' type by opening the file ``mycrypt.h'' and |
|
|
2677 changing ``LSIZE''. Note that if you set it to $n$ then you can only multiply upto two $n \over 2$ bit polynomials without |
|
|
2678 an overflow. The type ``gf\_intp'' is associated with a pointer to an ``unsigned long'' as required in the algorithms. |
|
|
2679 |
|
|
2680 There are no initialization routines for ``gf\_int'' variables and you can simply use them after declaration. There are five |
|
|
2681 low level functions: |
|
|
2682 \index{gf\_copy()} \index{gf\_zero()} \index{gf\_iszero()} \index{gf\_isone()} |
|
|
2683 \index{gf\_deg()} |
|
|
2684 \begin{verbatim} |
|
|
2685 void gf_copy(gf_intp a, gf_intp b); |
|
|
2686 void gf_zero(gf_intp a); |
|
|
2687 int gf_iszero(gf_intp a); |
|
|
2688 int gf_isone(gf_intp a); |
|
|
2689 int gf_deg(gf_intp a); |
|
|
2690 \end{verbatim} |
|
|
2691 There are all fairly self-explanatory. ``gf\_copy(a, b)'' copies the contents of ``a'' into ``b''. ``gf\_zero()'' simply |
|
|
2692 zeroes the entire polynomial. ``gf\_iszero()'' tests to see if the polynomial is all zero and ``gf\_isone()'' tests to see |
|
|
2693 if the polynomial is equal to the multiplicative identity. ``gf\_deg()'' returns the degree of the polynomial or $-1$ if its |
|
|
2694 a zero polynomial. |
|
|
2695 |
|
|
2696 There are five core math routines as well: |
|
|
2697 \index{gf\_shl()} \index{gf\_shr()} \index{gf\_add()} \index{gf\_mul()} \index{gf\_div()} |
|
|
2698 \begin{verbatim} |
|
|
2699 void gf_shl(gf_intp a, gf_intp b); |
|
|
2700 void gf_shr(gf_intp a, gf_intp b); |
|
|
2701 void gf_add(gf_intp a, gf_intp b, gf_intp c); |
|
|
2702 void gf_mul(gf_intp a, gf_intp b, gf_intp c); |
|
|
2703 void gf_div(gf_intp a, gf_intp b, gf_intp q, gf_intp r); |
|
|
2704 \end{verbatim} |
|
|
2705 |
|
|
2706 Which are all fairly obvious. ``gf\_shl(a,b)'' multiplies the polynomial ``a'' by $x$ and stores it in ``b''. |
|
|
2707 ``gf\_shl(a,b)'' divides the polynomial ``a'' by $x$ and stores it in ``b''. ``gf\_add(a,b,c)'' adds the polynomial |
|
|
2708 ``a'' to ``b'' and stores the sum in ``c''. Similarly for ``gf\_mul(a,b,c)''. The ``gf\_div(a,b,q,r)'' function divides |
|
|
2709 ``a'' by ``b'' and stores the quotient in ``q'' and the remainder in ``r''. |
|
|
2710 |
|
|
2711 There are six number theoretic functions as well: |
|
|
2712 \index{gf\_mod()} \index{gf\_mulmod()} \index{gf\_invmod()} \index{gf\_gcd()} \index{gf\_is\_prime()} |
|
|
2713 \index{gf\_sqrt()} |
|
|
2714 \begin{verbatim} |
|
|
2715 void gf_mod(gf_intp a, gf_intp m, gf_intp b); |
|
|
2716 void gf_mulmod(gf_intp a, gf_intp b, gf_intp m, gf_intp c); |
|
|
2717 void gf_invmod(gf_intp A, gf_intp M, gf_intp B); |
|
|
2718 void gf_sqrt(gf_intp a, gf_intp m, gf_intp b); |
|
|
2719 void gf_gcd(gf_intp A, gf_intp B, gf_intp c); |
|
|
2720 int gf_is_prime(gf_intp a); |
|
|
2721 \end{verbatim} |
|
|
2722 |
|
|
2723 Which all work similarly except for ``gf\_mulmod(a,b,m,c)'' which computes $c = ab\mbox{ }(\mbox{mod }m)$. The |
|
|
2724 ``gf\_is\_prime()'' function returns one if the polynomial is primitive, otherwise it returns zero. |
|
|
2725 |
|
|
2726 Finally to read/store a ``gf\_int'' in a binary string use: |
|
|
2727 \index{gf\_size()} \index{gf\_toraw()} \index{gf\_readraw()} |
|
|
2728 \begin{verbatim} |
|
|
2729 int gf_size(gf_intp a); |
|
|
2730 void gf_toraw(gf_intp a, unsigned char *dst); |
|
|
2731 void gf_readraw(gf_intp a, unsigned char *str, int len); |
|
|
2732 \end{verbatim} |
|
|
2733 Where ``gf\_size()'' returns the size in bytes required for the data. ``gf\_toraw(a,b)'' stores the polynomial in ``b'' |
|
|
2734 in binary format (endian neutral). ``gf\_readraw(a,b,c)'' reads the binary string in ``b'' back. Note that the length |
|
|
2735 you pass it must be the same as returned by ``gf\_size()'' or it will not load correctly. |
|
|
2736 |
|
|
2737 \chapter{Miscellaneous} |
|
|
2738 \section{Base64 Encoding and Decoding} |
|
|
2739 The library provides functions to encode and decode a RFC1521 base64 coding scheme. This means that it can decode what it |
|
|
2740 encodes but the format used does not comply to any known standard. The characters used in the mappings are: |
|
|
2741 \begin{verbatim} |
|
|
2742 ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/ |
|
|
2743 \end{verbatim} |
|
|
2744 Those characters should are supported in virtually any 7-bit ASCII system which means they can be used for transport over |
|
|
2745 common e-mail, usenet and HTTP mediums. The format of an encoded stream is just a literal sequence of ASCII characters |
|
|
2746 where a group of four represent 24-bits of input. The first four chars of the encoders output is the length of the |
|
|
2747 original input. After the first four characters is the rest of the message. |
|
|
2748 |
|
|
2749 Often it is desirable to line wrap the output to fit nicely in an e-mail or usenet posting. The decoder allows you to |
|
|
2750 put any character (that is not in the above sequence) in between any character of the encoders output. You may not however, |
|
|
2751 break up the first four characters. |
|
|
2752 |
|
|
2753 To encode a binary string in base64 call: |
|
|
2754 \index{base64\_encode()} \index{base64\_decode()} |
|
|
2755 \begin{verbatim} |
|
|
2756 int base64_encode(const unsigned char *in, unsigned long len, |
|
|
2757 unsigned char *out, unsigned long *outlen); |
|
|
2758 \end{verbatim} |
|
|
2759 Where ``in'' is the binary string and ``out'' is where the ASCII output is placed. You must set the value of ``outlen'' prior |
|
|
2760 to calling this function and it sets the length of the base64 output in ``outlen'' when it is done. To decode a base64 |
|
|
2761 string call: |
|
|
2762 \begin{verbatim} |
|
|
2763 int base64_decode(const unsigned char *in, unsigned long len, |
|
|
2764 unsigned char *out, unsigned long *outlen); |
|
|
2765 \end{verbatim} |
|
|
2766 |
|
|
2767 \section{The Multiple Precision Integer Library (MPI)} |
|
|
2768 The library comes with a copy of LibTomMath which is a multiple precision integer library written by the |
|
|
2769 author of LibTomCrypt. LibTomMath is a trivial to use ANSI C compatible large integer library which is free |
|
|
2770 for all uses and is distributed freely. |
|
|
2771 |
|
|
2772 At the heart of all the functions is the data type ``mp\_int'' (defined in tommath.h). This data type is what |
|
|
2773 will hold all large integers. In order to use an mp\_int one must initialize it first, for example: |
|
|
2774 \begin{verbatim} |
|
|
2775 #include <mycrypt.h> /* mycrypt.h includes mpi.h automatically */ |
|
|
2776 int main(void) |
|
|
2777 { |
|
|
2778 mp_int bignum; |
|
|
2779 |
|
|
2780 /* initialize it */ |
|
|
2781 mp_init(&bignum); |
|
|
2782 |
|
|
2783 return 0; |
|
|
2784 } |
|
|
2785 \end{verbatim} |
|
|
2786 If you are unfamiliar with the syntax of C the \& symbol is used to pass the address of ``bignum'' to the function. All |
|
|
2787 LibTomMath functions require the address of the parameters. To free the memory of a mp\_int use (for example): |
|
|
2788 \begin{verbatim} |
|
|
2789 mp_clear(&bignum); |
|
|
2790 \end{verbatim} |
|
|
2791 |
|
|
2792 The functions also have the basic form of one of the following: |
|
|
2793 \begin{verbatim} |
|
|
2794 mp_XXX(mp_int *a); |
|
|
2795 mp_XXX(mp_int *a, mp_int *b, mp_int *c); |
|
|
2796 mp_XXX(mp_int *a, mp_int *b, mp_int *c, mp_int *d); |
|
|
2797 \end{verbatim} |
|
|
2798 |
|
|
2799 Where they perform some operation and store the result in the mp\_int variable passed on the far right. |
|
|
2800 For example, to compute $c = a + b \mbox{ }(\mbox{mod }m)$ you would call: |
|
|
2801 \begin{verbatim} |
|
|
2802 mp_addmod(&a, &b, &m, &c); |
|
|
2803 \end{verbatim} |
|
|
2804 |
|
|
2805 \subsection{Binary Forms of ``mp\_int'' Variables} |
|
|
2806 |
|
|
2807 Often it is required to store a ``mp\_int'' in binary form for transport (e.g. exporting a key, packet |
|
|
2808 encryption, etc.). LibTomMath includes two functions to help when exporting numbers: |
|
|
2809 \begin{verbatim} |
|
|
2810 int mp_raw_size(mp_int *num); |
|
|
2811 mp_toraw(&num, buf); |
|
|
2812 \end{verbatim} |
|
|
2813 |
|
|
2814 The former function gives the size in bytes of the raw format and the latter function actually stores the raw data. All |
|
|
2815 ``mp\_int'' numbers are stored in big endian form (like PKCS demands) with the first byte being the sign of the number. The |
|
|
2816 ``rsa\_exptmod()'' function differs slightly since it will take the input in the form exactly as PKCS demands (without the |
|
|
2817 leading sign byte). All other functions include the sign byte (since its much simpler just to include it). The sign byte |
|
|
2818 must be zero for positive numbers and non-zero for negative numbers. For example, |
|
|
2819 the sequence: |
|
|
2820 \begin{verbatim} |
|
|
2821 00 FF 30 04 |
|
|
2822 \end{verbatim} |
|
|
2823 Represents the integer $255 \cdot 256^2 + 48 \cdot 256^1 + 4 \cdot 256^0$ or 16,723,972. |
|
|
2824 |
|
|
2825 To read a binary string back into a ``mp\_int'' call: |
|
|
2826 \begin{verbatim} |
|
|
2827 mp_read_raw(mp_int *num, unsigned char *str, int len); |
|
|
2828 \end{verbatim} |
|
|
2829 Where ``num'' is where to store it, ``str'' is the binary string (including the leading sign byte) and ``len'' is the |
|
|
2830 length of the binary string. |
|
|
2831 |
|
|
2832 \subsection{Primality Testing} |
|
|
2833 \index{Primality Testing} |
|
|
2834 The library includes primality testing and random prime functions as well. The primality tester will perform the test in |
|
|
2835 two phases. First it will perform trial division by the first few primes. Second it will perform eight rounds of the |
|
|
2836 Rabin-Miller primality testing algorithm. If the candidate passes both phases it is declared prime otherwise it is declared |
|
|
2837 composite. No prime number will fail the two phases but composites can. Each round of the Rabin-Miller algorithm reduces |
|
|
2838 the probability of a pseudo-prime by $1 \over 4$ therefore after sixteen rounds the probability is no more than |
|
|
2839 $\left ( { 1 \over 4 } \right )^{8} = 2^{-16}$. In practice the probability of error is in fact much lower than that. |
|
|
2840 |
|
|
2841 When making random primes the trial division step is in fact an optimized implementation of ``Implementation of Fast RSA Key Generation on Smart Cards''\footnote{Chenghuai Lu, Andre L. M. dos Santos and Francisco R. Pimentel}. |
|
|
2842 In essence a table of machine-word sized residues are kept of a candidate modulo a set of primes. When the candiate |
|
|
2843 is rejected and ultimately incremented to test the next number the residues are updated without using multi-word precision |
|
|
2844 math operations. As a result the routine can scan ahead to the next number required for testing with very little work |
|
|
2845 involved. |
|
|
2846 |
|
|
2847 In the event that a composite did make it through it would most likely cause the the algorithm trying to use it to fail. For |
|
|
2848 instance, in RSA two primes $p$ and $q$ are required. The order of the multiplicative sub-group (modulo $pq$) is given |
|
|
2849 as $\phi(pq)$ or $(p - 1)(q - 1)$. The decryption exponent $d$ is found as $de \equiv 1\mbox{ }(\mbox{mod } \phi(pq))$. If either $p$ or $q$ is composite the value of $d$ will be incorrect and the user |
|
|
2850 will not be able to sign or decrypt messages at all. Suppose $p$ was prime and $q$ was composite this is just a variation of |
|
|
2851 the multi-prime RSA. Suppose $q = rs$ for two primes $r$ and $s$ then $\phi(pq) = (p - 1)(r - 1)(s - 1)$ which clearly is |
|
|
2852 not equal to $(p - 1)(rs - 1)$. |
|
|
2853 |
|
|
2854 These are not technically part of the LibTomMath library but this is the best place to document them. |
|
|
2855 To test if a ``mp\_int'' is prime call: |
|
|
2856 \begin{verbatim} |
|
|
2857 int is_prime(mp_int *N, int *result); |
|
|
2858 \end{verbatim} |
|
|
2859 This puts a one in ``result'' if the number is probably prime, otherwise it places a zero in it. It is assumed that if |
|
|
2860 it returns an error that the value in ``result'' is undefined. To make |
|
|
2861 a random prime call: |
|
|
2862 \begin{verbatim} |
|
|
2863 int rand_prime(mp_int *N, unsigned long len, prng_state *prng, int wprng); |
|
|
2864 \end{verbatim} |
|
|
2865 Where ``len'' is the size of the prime in bytes ($2 \le len \le 256$). You can set ``len'' to the negative size you want |
|
|
2866 to get a prime of the form $p \equiv 3\mbox{ }(\mbox{mod } 4)$. So if you want a 1024-bit prime of this sort pass |
|
|
2867 ``len = -128'' to the function. Upon success it will return {\bf CRYPT\_OK} and ``N'' will contain an integer which |
|
|
2868 is very likely prime. |
|
|
2869 |
|
|
2870 \chapter{Programming Guidelines} |
|
|
2871 |
|
|
2872 \section{Secure Pseudo Random Number Generators} |
|
|
2873 Probably the singal most vulnerable point of any cryptosystem is the PRNG. Without one generating and protecting secrets |
|
|
2874 would be impossible. The requirement that one be setup correctly is vitally important and to address this point the library |
|
|
2875 does provide two RNG sources that will address the largest amount of end users as possible. The ``sprng'' PRNG provided |
|
|
2876 provides and easy to access source of entropy for any application on a *NIX or Windows computer. |
|
|
2877 |
|
|
2878 However, when the end user is not on one of these platforms the application developer must address the issue of finding |
|
|
2879 entropy. This manual is not designed to be a text on cryptography. I would just like to highlight that when you design |
|
|
2880 a cryptosystem make sure the first problem you solve is getting a fresh source of entropy. |
|
|
2881 |
|
|
2882 \section{Preventing Trivial Errors} |
|
|
2883 Two simple ways to prevent trivial errors is to prevent overflows and to check the return values. All of the functions |
|
|
2884 which output variable length strings will require you to pass the length of the destination. If the size of your output |
|
|
2885 buffer is smaller than the output it will report an error. Therefore, make sure the size you pass is correct! |
|
|
2886 |
|
|
2887 Also virtually all of the functions return an error code or {\bf CRYPT\_OK}. You should detect all errors as simple |
|
|
2888 typos or such can cause algorithms to fail to work as desired. |
|
|
2889 |
|
|
2890 \section{Registering Your Algorithms} |
|
|
2891 To avoid linking and other runtime errors it is important to register the ciphers, hashes and PRNGs you intend to use |
|
|
2892 before you try to use them. This includes any function which would use an algorithm indirectly through a descriptor table. |
|
|
2893 |
|
|
2894 A neat bonus to the registry system is that you can add external algorithms that are not part of the library without |
|
|
2895 having to hack the library. For example, suppose you have a hardware specific PRNG on your system. You could easily |
|
|
2896 write the few functions required plus a descriptor. After registering your PRNG all of the library functions that |
|
|
2897 need a PRNG can instantly take advantage of it. |
|
|
2898 |
|
|
2899 \section{Key Sizes} |
|
|
2900 |
|
|
2901 \subsection{Symmetric Ciphers} |
|
|
2902 For symmetric ciphers use as large as of a key as possible. For the most part ``bits are cheap'' so using a 256-bit key |
|
|
2903 is not a hard thing todo. |
|
|
2904 |
|
|
2905 \subsection{Assymetric Ciphers} |
|
|
2906 The following chart gives the work factor for solving a DH/RSA public key using the NFS. The work factor for a key of order |
|
|
2907 $n$ is estimated to be |
|
|
2908 \begin{equation} |
|
|
2909 e^{1.923 \cdot ln(n)^{1 \over 3} \cdot ln(ln(n))^{2 \over 3}} |
|
|
2910 \end{equation} |
|
|
2911 |
|
|
2912 Note that $n$ is not the bit-length but the magnitude. For example, for a 1024-bit key $n = 2^{1024}$. The work required |
|
|
2913 is: |
|
|
2914 \begin{center} |
|
|
2915 \begin{tabular}{|c|c|} |
|
|
2916 \hline RSA/DH Key Size (bits) & Work Factor ($log_2$) \\ |
|
|
2917 \hline 512 & 63.92 \\ |
|
|
2918 \hline 768 & 76.50 \\ |
|
|
2919 \hline 1024 & 86.76 \\ |
|
|
2920 \hline 1536 & 103.37 \\ |
|
|
2921 \hline 2048 & 116.88 \\ |
|
|
2922 \hline 2560 & 128.47 \\ |
|
|
2923 \hline 3072 & 138.73 \\ |
|
|
2924 \hline 4096 & 156.49 \\ |
|
|
2925 \hline |
|
|
2926 \end{tabular} |
|
|
2927 \end{center} |
|
|
2928 |
|
|
2929 The work factor for ECC keys is much higher since the best attack is still fully exponentional. Given a key of magnitude |
|
|
2930 $n$ it requires $\sqrt n$ work. The following table sumarizes the work required: |
|
|
2931 \begin{center} |
|
|
2932 \begin{tabular}{|c|c|} |
|
|
2933 \hline ECC Key Size (bits) & Work Factor ($log_2$) \\ |
|
|
2934 \hline 160 & 80 \\ |
|
|
2935 \hline 192 & 96 \\ |
|
|
2936 \hline 224 & 112 \\ |
|
|
2937 \hline 256 & 128 \\ |
|
|
2938 \hline 384 & 192 \\ |
|
|
2939 \hline 521 & 260.5 \\ |
|
|
2940 \hline |
|
|
2941 \end{tabular} |
|
|
2942 \end{center} |
|
|
2943 |
|
|
2944 Using the above tables the following suggestions for key sizes seems appropriate: |
|
|
2945 \begin{center} |
|
|
2946 \begin{tabular}{|c|c|c|} |
|
|
2947 \hline Security Goal & RSA/DH Key Size (bits) & ECC Key Size (bits) \\ |
|
|
2948 \hline Short term (less than a year) & 1024 & 160 \\ |
|
|
2949 \hline Short term (less than five years) & 1536 & 192 \\ |
|
|
2950 \hline Long Term (less than ten years) & 2560 & 256 \\ |
|
|
2951 \hline |
|
|
2952 \end{tabular} |
|
|
2953 \end{center} |
|
|
2954 |
|
|
2955 \section{Thread Safety} |
|
|
2956 The library is not thread safe but several simple precautions can be taken to avoid any problems. The registry functions |
|
|
2957 such as register\_cipher() are not thread safe no matter what you do. Its best to call them from your programs initializtion |
|
|
2958 code before threads are initiated. |
|
|
2959 |
|
|
2960 The rest of the code uses state variables you must pass it such as hash\_state, hmac\_state, etc. This means that if each |
|
|
2961 thread has its own state variables then they will not affect each other. This is fairly simple with symmetric ciphers |
|
|
2962 and hashes. However, the keyring and PRNG support is something the threads will want to share. The simplest workaround |
|
|
2963 is create semaphores or mutexes around calls to those functions. |
|
|
2964 |
|
|
2965 Since C does not have standard semaphores this support is not native to Libtomcrypt. Even a C based semaphore is not entire |
|
|
2966 possible as some compilers may ignore the ``volatile'' keyword or have multiple processors. Provide your host application |
|
|
2967 is modular enough putting the locks in the right place should not bloat the code significantly and will solve all thread |
|
|
2968 safety issues within the library. |
|
|
2969 |
|
|
2970 \chapter{Configuring the Library} |
|
|
2971 \section{Introduction} |
|
|
2972 The library is fairly flexible about how it can be built, used and generally distributed. Additions are being made with |
|
|
2973 each new release that will make the library even more flexible. Most options are placed in the makefile and others |
|
|
2974 are in ``mycrypt\_cfg.h''. All are used when the library is built from scratch. |
|
|
2975 |
|
|
2976 For GCC platforms the file ``makefile'' is the makefile to be used. On MSVC platforms ``makefile.vc'' and on PS2 platforms |
|
|
2977 ``makefile.ps2''. |
|
|
2978 |
|
|
2979 \section{mycrypt\_cfg.h} |
|
|
2980 The file ``mycrypt\_cfg.h'' is what lets you control what functionality you want to remove from the library. By default, |
|
|
2981 everything the library has to offer it built. |
|
|
2982 |
|
|
2983 \subsubsection{ARGTYPE} |
|
|
2984 This lets you control how the \_ARGCHK macro will behave. The macro is used to check pointers inside the functions against |
|
|
2985 NULL. There are three settings for ARGTYPE. When set to 0 it will have the default behaviour of printing a message to |
|
|
2986 stderr and raising a SIGABRT signal. This is provided so all platforms that use libtomcrypt can have an error that functions |
|
|
2987 similarly. When set to 1 it will simply pass on to the assert() macro. When set to 2 it will resolve to a empty macro |
|
|
2988 and no error checking will be performed. |
|
|
2989 |
|
|
2990 \subsubsection{Endianess} |
|
|
2991 There are five macros related to endianess issues. For little endian platforms define, ENDIAN\_LITTLE. For big endian |
|
|
2992 platforms define ENDIAN\_BIG. Similarly when the default word size of an ``unsigned long'' is 32-bits define ENDIAN\_32BITWORD |
|
|
2993 or define ENDIAN\_64BITWORD when its 64-bits. If you do not define any of them the library will automatically use ENDIAN\_NEUTRAL |
|
|
2994 which will work on all platforms. Currently the system will automatically detect GCC or MSVC on a windows platform as well |
|
|
2995 as GCC on a PS2 platform. |
|
|
2996 |
|
|
2997 \section{The Configure Script} |
|
|
2998 There are also options you can specify from the configure script or ``mycrypt\_config.h''. |
|
|
2999 |
|
|
3000 \subsubsection{X memory routines} |
|
|
3001 The makefiles must define three macros denoted as XMALLOC, XCALLOC and XFREE which resolve to the name of the respective |
|
|
3002 functions. This lets you substitute in your own memory routines. If you substitute in your own functions they must behave |
|
|
3003 like the standard C library functions in terms of what they expect as input and output. By default the library uses the |
|
|
3004 standard C routines. |
|
|
3005 |
|
|
3006 \subsubsection{X clock routines} |
|
|
3007 The rng\_get\_bytes() function can call a function that requires the clock() function. These macros let you override |
|
|
3008 the default clock() used with a replacement. By default the standard C library clock() function is used. |
|
|
3009 |
|
|
3010 \subsubsection{NO\_FILE} |
|
|
3011 During the build if NO\_FILE is defined then any function in the library that uses file I/O will not call the file I/O |
|
|
3012 functions and instead simply return CRYPT\_ERROR. This should help resolve any linker errors stemming from a lack of |
|
|
3013 file I/O on embedded platforms. |
|
|
3014 |
|
|
3015 \subsubsection{CLEAN\_STACK} |
|
|
3016 When this functions is defined the functions that store key material on the stack will clean up afterwards. Assumes that |
|
|
3017 you have no memory paging with the stack. |
|
|
3018 |
|
|
3019 \subsubsection{Symmetric Ciphers, One-way Hashes, PRNGS and Public Key Functions} |
|
|
3020 There are a plethora of macros for the ciphers, hashes, PRNGs and public key functions which are fairly self-explanatory. |
|
|
3021 When they are defined the functionality is included otherwise it is not. There are some dependency issues which are |
|
|
3022 noted in the file. For instance, Yarrow requires CTR chaining mode, a block cipher and a hash function. |
|
|
3023 |
|
|
3024 \subsubsection{TWOFISH\_SMALL and TWOFISH\_TABLES} |
|
|
3025 Twofish is a 128-bit symmetric block cipher that is provided within the library. The cipher itself is flexible enough |
|
|
3026 to allow some tradeoffs in the implementation. When TWOFISH\_SMALL is defined the scheduled symmetric key for Twofish |
|
|
3027 requires only 200 bytes of memory. This is achieved by not pre-computing the substitution boxes. Having this |
|
|
3028 defined will also greatly slow down the cipher. When this macro is not defined Twofish will pre-compute the |
|
|
3029 tables at a cost of 4KB of memory. The cipher will be much faster as a result. |
|
|
3030 |
|
|
3031 When TWOFISH\_TABLES is defined the cipher will use pre-computed (and fixed in code) tables required to work. This is |
|
|
3032 useful when TWOFISH\_SMALL is defined as the table values are computed on the fly. When this is defined the code size |
|
|
3033 will increase by approximately 500 bytes. If this is defined but TWOFISH\_SMALL is not the cipher will still work but |
|
|
3034 it will not speed up the encryption or decryption functions. |
|
|
3035 |
|
|
3036 \subsubsection{SMALL\_CODE} |
|
|
3037 When this is defined some of the code such as the Rijndael and SAFER+ ciphers are replaced with smaller code variants. |
|
|
3038 These variants are slower but can save quite a bit of code space. |
|
|
3039 |
|
|
3040 \end{document} |
