src/libstd/sha1.rs

   1 // Copyright 2012 The Rust Project Developers. See the COPYRIGHT
   2 // file at the top-level directory of this distribution and at
   3 // http://rust-lang.org/COPYRIGHT.
   4 //
   5 // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
   6 // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
   7 // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
   8 // option. This file may not be copied, modified, or distributed
   9 // except according to those terms.
  10
  11 /*!
  12  * An implementation of the SHA-1 cryptographic hash.
  13  *
  14  * First create a `sha1` object using the `sha1` constructor, then
  15  * feed it input using the `input` or `input_str` methods, which may be
  16  * called any number of times.
  17  *
  18  * After the entire input has been fed to the hash read the result using
  19  * the `result` or `result_str` methods.
  20  *
  21  * The `sha1` object may be reused to create multiple hashes by calling
  22  * the `reset` method.
  23  */
  24
  25 use core::str;
  26 use core::uint;
  27 use core::vec;
  28
  29 /*
  30  * A SHA-1 implementation derived from Paul E. Jones's reference
  31  * implementation, which is written for clarity, not speed. At some
  32  * point this will want to be rewritten.
  33  */
  34
  35 /// The SHA-1 interface
  36 trait Sha1 {
  37     /// Provide message input as bytes
  38     fn input(&mut self, &const [u8]);
  39     /// Provide message input as string
  40     fn input_str(&mut self, &str);
  41     /**
  42      * Read the digest as a vector of 20 bytes. After calling this no further
  43      * input may be provided until reset is called.
  44      */
  45     fn result(&mut self) -> ~[u8];
  46     /**
  47      * Read the digest as a hex string. After calling this no further
  48      * input may be provided until reset is called.
  49      */
  50     fn result_str(&mut self) -> ~str;
  51     /// Reset the SHA-1 state for reuse
  52     fn reset(&mut self);
  53 }
  54
  55 // Some unexported constants
  56 static digest_buf_len: uint = 5u;
  57 static msg_block_len: uint = 64u;
  58 static work_buf_len: uint = 80u;
  59 static k0: u32 = 0x5A827999u32;
  60 static k1: u32 = 0x6ED9EBA1u32;
  61 static k2: u32 = 0x8F1BBCDCu32;
  62 static k3: u32 = 0xCA62C1D6u32;
  63
  64
  65 /// Construct a `sha` object
  66 pub fn sha1() -> @Sha1 {
  67     struct Sha1State
  68         { h: ~[u32],
  69           len_low: u32,
  70           len_high: u32,
  71           msg_block: ~[u8],
  72           msg_block_idx: uint,
  73           computed: bool,
  74           work_buf: @mut ~[u32]};
  75
  76     fn add_input(st: &mut Sha1State, msg: &const [u8]) {
  77         assert!((!st.computed));
  78         for vec::each_const(msg) |element| {
  79             st.msg_block[st.msg_block_idx] = *element;
  80             st.msg_block_idx += 1u;
  81             st.len_low += 8u32;
  82             if st.len_low == 0u32 {
  83                 st.len_high += 1u32;
  84                 if st.len_high == 0u32 {
  85                     // FIXME: Need better failure mode (#2346)
  86                     fail!();
  87                 }
  88             }
  89             if st.msg_block_idx == msg_block_len { process_msg_block(st); }
  90         }
  91     }
  92     fn process_msg_block(st: &mut Sha1State) {
  93         assert!((vec::len(st.h) == digest_buf_len));
  94         assert!((vec::uniq_len(st.work_buf) == work_buf_len));
  95         let mut t: int; // Loop counter
  96         let w = st.work_buf;
  97
  98         // Initialize the first 16 words of the vector w
  99         t = 0;
 100         while t < 16 {
 101             let mut tmp;
 102             tmp = (st.msg_block[t * 4] as u32) << 24u32;
 103             tmp = tmp | (st.msg_block[t * 4 + 1] as u32) << 16u32;
 104             tmp = tmp | (st.msg_block[t * 4 + 2] as u32) << 8u32;
 105             tmp = tmp | (st.msg_block[t * 4 + 3] as u32);
 106             w[t] = tmp;
 107             t += 1;
 108         }
 109
 110         // Initialize the rest of vector w
 111         while t < 80 {
 112             let val = w[t - 3] ^ w[t - 8] ^ w[t - 14] ^ w[t - 16];
 113             w[t] = circular_shift(1u32, val);
 114             t += 1;
 115         }
 116         let mut a = st.h[0];
 117         let mut b = st.h[1];
 118         let mut c = st.h[2];
 119         let mut d = st.h[3];
 120         let mut e = st.h[4];
 121         let mut temp: u32;
 122         t = 0;
 123         while t < 20 {
 124             temp = circular_shift(5u32, a) + (b & c | !b & d) + e + w[t] + k0;
 125             e = d;
 126             d = c;
 127             c = circular_shift(30u32, b);
 128             b = a;
 129             a = temp;
 130             t += 1;
 131         }
 132         while t < 40 {
 133             temp = circular_shift(5u32, a) + (b ^ c ^ d) + e + w[t] + k1;
 134             e = d;
 135             d = c;
 136             c = circular_shift(30u32, b);
 137             b = a;
 138             a = temp;
 139             t += 1;
 140         }
 141         while t < 60 {
 142             temp =
 143                 circular_shift(5u32, a) + (b & c | b & d | c & d) + e + w[t] +
 144                     k2;
 145             e = d;
 146             d = c;
 147             c = circular_shift(30u32, b);
 148             b = a;
 149             a = temp;
 150             t += 1;
 151         }
 152         while t < 80 {
 153             temp = circular_shift(5u32, a) + (b ^ c ^ d) + e + w[t] + k3;
 154             e = d;
 155             d = c;
 156             c = circular_shift(30u32, b);
 157             b = a;
 158             a = temp;
 159             t += 1;
 160         }
 161         st.h[0] = st.h[0] + a;
 162         st.h[1] = st.h[1] + b;
 163         st.h[2] = st.h[2] + c;
 164         st.h[3] = st.h[3] + d;
 165         st.h[4] = st.h[4] + e;
 166         st.msg_block_idx = 0u;
 167     }
 168     fn circular_shift(bits: u32, word: u32) -> u32 {
 169         return word << bits | word >> 32u32 - bits;
 170     }
 171     fn mk_result(st: &mut Sha1State) -> ~[u8] {
 172         if !(*st).computed { pad_msg(st); (*st).computed = true; }
 173         let mut rs: ~[u8] = ~[];
 174         for vec::each_mut((*st).h) |ptr_hpart| {
 175             let hpart = *ptr_hpart;
 176             let a = (hpart >> 24u32 & 0xFFu32) as u8;
 177             let b = (hpart >> 16u32 & 0xFFu32) as u8;
 178             let c = (hpart >> 8u32 & 0xFFu32) as u8;
 179             let d = (hpart & 0xFFu32) as u8;
 180             rs = vec::append(rs, ~[a, b, c, d]);
 181         }
 182         return rs;
 183     }
 184
 185     /*
 186      * According to the standard, the message must be padded to an even
 187      * 512 bits.  The first padding bit must be a '1'.  The last 64 bits
 188      * represent the length of the original message.  All bits in between
 189      * should be 0.  This function will pad the message according to those
 190      * rules by filling the msg_block vector accordingly.  It will also
 191      * call process_msg_block() appropriately.  When it returns, it
 192      * can be assumed that the message digest has been computed.
 193      */
 194     fn pad_msg(st: &mut Sha1State) {
 195         assert!((vec::len((*st).msg_block) == msg_block_len));
 196
 197         /*
 198          * Check to see if the current message block is too small to hold
 199          * the initial padding bits and length.  If so, we will pad the
 200          * block, process it, and then continue padding into a second block.
 201          */
 202         if (*st).msg_block_idx > 55u {
 203             (*st).msg_block[(*st).msg_block_idx] = 0x80u8;
 204             (*st).msg_block_idx += 1u;
 205             while (*st).msg_block_idx < msg_block_len {
 206                 (*st).msg_block[(*st).msg_block_idx] = 0u8;
 207                 (*st).msg_block_idx += 1u;
 208             }
 209             process_msg_block(st);
 210         } else {
 211             (*st).msg_block[(*st).msg_block_idx] = 0x80u8;
 212             (*st).msg_block_idx += 1u;
 213         }
 214         while (*st).msg_block_idx < 56u {
 215             (*st).msg_block[(*st).msg_block_idx] = 0u8;
 216             (*st).msg_block_idx += 1u;
 217         }
 218
 219         // Store the message length as the last 8 octets
 220         (*st).msg_block[56] = ((*st).len_high >> 24u32 & 0xFFu32) as u8;
 221         (*st).msg_block[57] = ((*st).len_high >> 16u32 & 0xFFu32) as u8;
 222         (*st).msg_block[58] = ((*st).len_high >> 8u32 & 0xFFu32) as u8;
 223         (*st).msg_block[59] = ((*st).len_high & 0xFFu32) as u8;
 224         (*st).msg_block[60] = ((*st).len_low >> 24u32 & 0xFFu32) as u8;
 225         (*st).msg_block[61] = ((*st).len_low >> 16u32 & 0xFFu32) as u8;
 226         (*st).msg_block[62] = ((*st).len_low >> 8u32 & 0xFFu32) as u8;
 227         (*st).msg_block[63] = ((*st).len_low & 0xFFu32) as u8;
 228         process_msg_block(st);
 229     }
 230
 231     impl Sha1 for Sha1State {
 232         fn reset(&mut self) {
 233             assert!((vec::len(self.h) == digest_buf_len));
 234             self.len_low = 0u32;
 235             self.len_high = 0u32;
 236             self.msg_block_idx = 0u;
 237             self.h[0] = 0x67452301u32;
 238             self.h[1] = 0xEFCDAB89u32;
 239             self.h[2] = 0x98BADCFEu32;
 240             self.h[3] = 0x10325476u32;
 241             self.h[4] = 0xC3D2E1F0u32;
 242             self.computed = false;
 243         }
 244         fn input(&mut self, msg: &const [u8]) { add_input(self, msg); }
 245         fn input_str(&mut self, msg: &str) {
 246             let bs = str::to_bytes(msg);
 247             add_input(self, bs);
 248         }
 249         fn result(&mut self) -> ~[u8] { return mk_result(self); }
 250         fn result_str(&mut self) -> ~str {
 251             let rr = mk_result(self);
 252             let mut s = ~"";
 253             for vec::each(rr) |b| {
 254                 let hex = uint::to_str_radix(*b as uint, 16u);
 255                 if hex.len() == 1 {
 256                     s += "0";
 257                 }
 258                 s += hex;
 259             }
 260             return s;
 261         }
 262     }
 263     let st = Sha1State {
 264          h: vec::from_elem(digest_buf_len, 0u32),
 265          len_low: 0u32,
 266          len_high: 0u32,
 267          msg_block: vec::from_elem(msg_block_len, 0u8),
 268          msg_block_idx: 0u,
 269          computed: false,
 270          work_buf: @mut vec::from_elem(work_buf_len, 0u32)
 271     };
 272     let mut sh = @st as @Sha1;
 273     sh.reset();
 274     return sh;
 275 }
 276
 277 #[cfg(test)]
 278 mod tests {
 279     use sha1;
 280
 281     use core::str;
 282     use core::vec;
 283
 284     #[test]
 285     fn test() {
 286         struct Test {
 287             input: ~str,
 288             output: ~[u8],
 289             output_str: ~str,
 290         }
 291
 292         fn a_million_letter_a() -> ~str {
 293             let mut i = 0;
 294             let mut rs = ~"";
 295             while i < 100000 {
 296                 str::push_str(&mut rs, ~"aaaaaaaaaa");
 297                 i += 1;
 298             }
 299             return rs;
 300         }
 301         // Test messages from FIPS 180-1
 302
 303         let fips_180_1_tests = ~[
 304             Test {
 305                 input: ~"abc",
 306                 output: ~[
 307                     0xA9u8, 0x99u8, 0x3Eu8, 0x36u8,
 308                     0x47u8, 0x06u8, 0x81u8, 0x6Au8,
 309                     0xBAu8, 0x3Eu8, 0x25u8, 0x71u8,
 310                     0x78u8, 0x50u8, 0xC2u8, 0x6Cu8,
 311                     0x9Cu8, 0xD0u8, 0xD8u8, 0x9Du8,
 312                 ],
 313                 output_str: ~"a9993e364706816aba3e25717850c26c9cd0d89d"
 314             },
 315             Test {
 316                 input:
 317                      ~"abcdbcdecdefdefgefghfghighij" +
 318                      ~"hijkijkljklmklmnlmnomnopnopq",
 319                 output: ~[
 320                     0x84u8, 0x98u8, 0x3Eu8, 0x44u8,
 321                     0x1Cu8, 0x3Bu8, 0xD2u8, 0x6Eu8,
 322                     0xBAu8, 0xAEu8, 0x4Au8, 0xA1u8,
 323                     0xF9u8, 0x51u8, 0x29u8, 0xE5u8,
 324                     0xE5u8, 0x46u8, 0x70u8, 0xF1u8,
 325                 ],
 326                 output_str: ~"84983e441c3bd26ebaae4aa1f95129e5e54670f1"
 327             },
 328             Test {
 329                 input: a_million_letter_a(),
 330                 output: ~[
 331                     0x34u8, 0xAAu8, 0x97u8, 0x3Cu8,
 332                     0xD4u8, 0xC4u8, 0xDAu8, 0xA4u8,
 333                     0xF6u8, 0x1Eu8, 0xEBu8, 0x2Bu8,
 334                     0xDBu8, 0xADu8, 0x27u8, 0x31u8,
 335                     0x65u8, 0x34u8, 0x01u8, 0x6Fu8,
 336                 ],
 337                 output_str: ~"34aa973cd4c4daa4f61eeb2bdbad27316534016f"
 338             },
 339         ];
 340         // Examples from wikipedia
 341
 342         let wikipedia_tests = ~[
 343             Test {
 344                 input: ~"The quick brown fox jumps over the lazy dog",
 345                 output: ~[
 346                     0x2fu8, 0xd4u8, 0xe1u8, 0xc6u8,
 347                     0x7au8, 0x2du8, 0x28u8, 0xfcu8,
 348                     0xedu8, 0x84u8, 0x9eu8, 0xe1u8,
 349                     0xbbu8, 0x76u8, 0xe7u8, 0x39u8,
 350                     0x1bu8, 0x93u8, 0xebu8, 0x12u8,
 351                 ],
 352                 output_str: ~"2fd4e1c67a2d28fced849ee1bb76e7391b93eb12",
 353             },
 354             Test {
 355                 input: ~"The quick brown fox jumps over the lazy cog",
 356                 output: ~[
 357                     0xdeu8, 0x9fu8, 0x2cu8, 0x7fu8,
 358                     0xd2u8, 0x5eu8, 0x1bu8, 0x3au8,
 359                     0xfau8, 0xd3u8, 0xe8u8, 0x5au8,
 360                     0x0bu8, 0xd1u8, 0x7du8, 0x9bu8,
 361                     0x10u8, 0x0du8, 0xb4u8, 0xb3u8,
 362                 ],
 363                 output_str: ~"de9f2c7fd25e1b3afad3e85a0bd17d9b100db4b3",
 364             },
 365         ];
 366         let tests = fips_180_1_tests + wikipedia_tests;
 367         fn check_vec_eq(v0: ~[u8], v1: ~[u8]) {
 368             assert!((vec::len::<u8>(v0) == vec::len::<u8>(v1)));
 369             let len = vec::len::<u8>(v0);
 370             let mut i = 0u;
 371             while i < len {
 372                 let a = v0[i];
 373                 let b = v1[i];
 374                 assert!((a == b));
 375                 i += 1u;
 376             }
 377         }
 378         // Test that it works when accepting the message all at once
 379
 380         let mut sh = sha1::sha1();
 381         for vec::each(tests) |t| {
 382             sh.input_str(t.input);
 383             let out = sh.result();
 384             check_vec_eq(t.output, out);
 385
 386             let out_str = sh.result_str();
 387             assert!((out_str.len() == 40));
 388             assert!((out_str == t.output_str));
 389
 390             sh.reset();
 391         }
 392
 393
 394         // Test that it works when accepting the message in pieces
 395         for vec::each(tests) |t| {
 396             let len = str::len(t.input);
 397             let mut left = len;
 398             while left > 0u {
 399                 let take = (left + 1u) / 2u;
 400                 sh.input_str(str::slice(t.input, len - left,
 401                              take + len - left).to_owned());
 402                 left = left - take;
 403             }
 404             let out = sh.result();
 405             check_vec_eq(t.output, out);
 406
 407             let out_str = sh.result_str();
 408             assert!((out_str.len() == 40));
 409             assert!((out_str == t.output_str));
 410
 411             sh.reset();
 412         }
 413     }
 414 }
 415
 416 // Local Variables:
 417 // mode: rust;
 418 // fill-column: 78;
 419 // indent-tabs-mode: nil
 420 // c-basic-offset: 4
 421 // buffer-file-coding-system: utf-8-unix
 422 // End: