scrypt.c 5.2 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181
  1. /* ===================================================================
  2. *
  3. * Copyright (c) 2015, Legrandin <helderijs@gmail.com>
  4. * All rights reserved.
  5. *
  6. * Redistribution and use in source and binary forms, with or without
  7. * modification, are permitted provided that the following conditions
  8. * are met:
  9. *
  10. * 1. Redistributions of source code must retain the above copyright
  11. * notice, this list of conditions and the following disclaimer.
  12. * 2. Redistributions in binary form must reproduce the above copyright
  13. * notice, this list of conditions and the following disclaimer in
  14. * the documentation and/or other materials provided with the
  15. * distribution.
  16. *
  17. * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  18. * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  19. * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
  20. * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
  21. * COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
  22. * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
  23. * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
  24. * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
  25. * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  26. * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
  27. * ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
  28. * POSSIBILITY OF SUCH DAMAGE.
  29. * ===================================================================
  30. */
  31. #include "pycrypto_common.h"
  32. FAKE_INIT(scrypt)
  33. static inline int little_endian(void) {
  34. int test = 1;
  35. return *((uint8_t*)&test) == 1;
  36. }
  37. static inline uint32_t load_le_uint32(const uint8_t *in)
  38. {
  39. union {
  40. uint32_t w;
  41. uint8_t b[4];
  42. } x, y;
  43. memcpy(&x, in, 4);
  44. y = x;
  45. if (!little_endian()) {
  46. y.b[0] = x.b[3];
  47. y.b[1] = x.b[2];
  48. y.b[2] = x.b[1];
  49. y.b[3] = x.b[0];
  50. }
  51. return y.w;
  52. }
  53. /** Return 1 if the pointer is aligned to the 64-bit boundary **/
  54. static inline int aligned64(const uint8_t *p)
  55. {
  56. if ((uintptr_t)p % 8 == 0)
  57. return 1;
  58. else
  59. return 0;
  60. }
  61. static inline void strxor_inplace(uint8_t *in_out, const uint8_t *in, size_t data_len)
  62. {
  63. size_t i;
  64. if (!aligned64(in_out) || !aligned64(in) || (data_len%8)!=0) {
  65. for (i=0; i<data_len; i++) {
  66. *in_out++ ^= *in++;
  67. }
  68. } else {
  69. uint64_t *in_out64 = (uint64_t*)in_out;
  70. uint64_t *in64 = (uint64_t*)in;
  71. data_len /= 8;
  72. for (i=0; i<data_len; i++) {
  73. *in_out64++ ^= *in64++;
  74. }
  75. }
  76. }
  77. typedef int (core_t)(const uint8_t [64], const uint8_t [64], uint8_t [64]);
  78. /**
  79. * scrypt BlockMix function
  80. *
  81. * @in: input, a sequence of blocks, each 64 bytes long
  82. * @out: output, a sequence of blocks, each 64 bytes long
  83. * @two_r: the number of 64 bytes blocks in input and output (even)
  84. * @core: the Salsa20 core hashing function (with xor)
  85. *
  86. * @in and @out may not overlap.
  87. */
  88. static void scryptBlockMix(const uint8_t in[][64], uint8_t out[][64], size_t two_r,
  89. core_t *core)
  90. {
  91. unsigned i;
  92. const uint8_t (*x)[64];
  93. size_t r = two_r / 2;
  94. assert(in != out);
  95. x = &in[two_r-1]; /* Last 64 byte block */
  96. for (i=0; i<two_r; i++) {
  97. uint8_t (*y)[64];
  98. y = &out[(i/2) + (i & 1)*r];
  99. (*core)(*x, in[i], *y);
  100. x = y;
  101. }
  102. }
  103. /**
  104. * scrypt ROMix function
  105. *
  106. * @data_in: input
  107. * @data_out: output
  108. * @data_len: Length in bytes of the two buffers `data_in` and `data_out`.
  109. * It is a multiple of 128.
  110. * @N: Memory/CPU cost. It must be a power of 2.
  111. *
  112. * @data_in and @data_out may overlap.
  113. */
  114. EXPORT_SYM int scryptROMix(const uint8_t *data_in, uint8_t *data_out,
  115. size_t data_len, unsigned N, core_t *core)
  116. {
  117. size_t two_r;
  118. uint8_t (*v)[64], (*x)[64];
  119. unsigned i;
  120. if (NULL==data_in || NULL==data_out || NULL==core) {
  121. return ERR_NULL;
  122. }
  123. two_r = data_len / 64;
  124. if ((two_r*64 != data_len) || (two_r & 1)) {
  125. return ERR_BLOCK_SIZE;
  126. }
  127. /** Allocate a possibly gigantic amount of memory **/
  128. /* It takes in total (N+1) * (128r) bytes */
  129. v = calloc(N + 1, data_len);
  130. if (NULL == v) {
  131. return ERR_MEMORY;
  132. }
  133. memmove(&v[0], data_in, data_len);
  134. /** Create the V array **/
  135. /* The size of each element of V is 64 bytes, so
  136. * you need to add `two_r` (not 1) to move forward.
  137. */
  138. x = v;
  139. for (i=0; i<N; i++) {
  140. scryptBlockMix(x, &x[two_r], two_r, core);
  141. x += two_r;
  142. }
  143. /** Mix via a pseudo random sequence **/
  144. x = &v[N * two_r];
  145. for (i=0; i<N; i++) {
  146. uint32_t index;
  147. index = load_le_uint32(&x[two_r - 1][0]) & (N - 1); /* Extract pseudo
  148. random index
  149. from last element
  150. */
  151. strxor_inplace(*x, v[index * two_r], data_len);
  152. scryptBlockMix(x, (uint8_t (*)[64])data_out, two_r, core);
  153. memmove(x, data_out, data_len);
  154. }
  155. /** Outro **/
  156. /** data_out already contains the right value **/
  157. free(v);
  158. return 0;
  159. }