1 /* xts.c
2
3 XEX-based tweaked-codebook mode with ciphertext stealing (XTS)
4
5 Copyright (C) 2018 Red Hat, Inc.
6
7 This file is part of GNU Nettle.
8
9 GNU Nettle is free software: you can redistribute it and/or
10 modify it under the terms of either:
11
12 * the GNU Lesser General Public License as published by the Free
13 Software Foundation; either version 3 of the License, or (at your
14 option) any later version.
15
16 or
17
18 * the GNU General Public License as published by the Free
19 Software Foundation; either version 2 of the License, or (at your
20 option) any later version.
21
22 or both in parallel, as here.
23
24 GNU Nettle is distributed in the hope that it will be useful,
25 but WITHOUT ANY WARRANTY; without even the implied warranty of
26 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
27 General Public License for more details.
28
29 You should have received copies of the GNU General Public License and
30 the GNU Lesser General Public License along with this program. If
31 not, see http://www.gnu.org/licenses/.
32 */
33
34 #if HAVE_CONFIG_H
35 # include "config.h"
36 #endif
37
38 #include <assert.h>
39 #include <stdlib.h>
40 #include <string.h>
41
42 #include "xts.h"
43
44 #include "macros.h"
45 #include "memxor.h"
46 #include "nettle-internal.h"
47
48 /* shift left one and XOR with 0x87 if there is carry. */
49 /* the algorithm reads this as a 128bit Little Endian number */
50 /* src and dest can point to the same buffer for in-place operations */
51 #if WORDS_BIGENDIAN
52 #define BE_SHIFT(x) ((((x) & 0x7f7f7f7f7f7f7f7f) << 1) | \
53 (((x) & 0x8080808080808080) >> 15))
54 static void
xts_shift(union nettle_block16 * dst,const union nettle_block16 * src)55 xts_shift(union nettle_block16 *dst,
56 const union nettle_block16 *src)
57 {
58 uint64_t carry = (src->u64[1] & 0x80) >> 7;
59 dst->u64[1] = BE_SHIFT(src->u64[1]) | ((src->u64[0] & 0x80) << 49);
60 dst->u64[0] = BE_SHIFT(src->u64[0]) ^ (0x8700000000000000 & -carry);
61 }
62 #else /* !WORDS_BIGENDIAN */
63 static void
xts_shift(union nettle_block16 * dst,const union nettle_block16 * src)64 xts_shift(union nettle_block16 *dst,
65 const union nettle_block16 *src)
66 {
67 uint64_t carry = src->u64[1] >> 63;
68 dst->u64[1] = (src->u64[1] << 1) | (src->u64[0] >> 63);
69 dst->u64[0] = (src->u64[0] << 1) ^ (0x87 & -carry);
70 }
71 #endif /* !WORDS_BIGNDIAN */
72
73 static void
check_length(size_t length,uint8_t * dst)74 check_length(size_t length, uint8_t *dst)
75 {
76 assert(length >= XTS_BLOCK_SIZE);
77 /* asserts may be compiled out, try to save the user by zeroing the dst in
78 * case the buffer contains sensitive data (like the clear text for inplace
79 * encryption) */
80 if (length < XTS_BLOCK_SIZE)
81 memset(dst, '\0', length);
82 }
83
84 /* works also for inplace encryption/decryption */
85
86 void
xts_encrypt_message(const void * enc_ctx,const void * twk_ctx,nettle_cipher_func * encf,const uint8_t * tweak,size_t length,uint8_t * dst,const uint8_t * src)87 xts_encrypt_message(const void *enc_ctx, const void *twk_ctx,
88 nettle_cipher_func *encf,
89 const uint8_t *tweak, size_t length,
90 uint8_t *dst, const uint8_t *src)
91 {
92 union nettle_block16 T;
93 union nettle_block16 P;
94
95 check_length(length, dst);
96
97 encf(twk_ctx, XTS_BLOCK_SIZE, T.b, tweak);
98
99 /* the zeroth power of alpha is the initial ciphertext value itself, so we
100 * skip shifting and do it at the end of each block operation instead */
101 for (;length >= 2 * XTS_BLOCK_SIZE || length == XTS_BLOCK_SIZE;
102 length -= XTS_BLOCK_SIZE, src += XTS_BLOCK_SIZE, dst += XTS_BLOCK_SIZE)
103 {
104 memxor3(P.b, src, T.b, XTS_BLOCK_SIZE); /* P -> PP */
105 encf(enc_ctx, XTS_BLOCK_SIZE, dst, P.b); /* CC */
106 memxor(dst, T.b, XTS_BLOCK_SIZE); /* CC -> C */
107
108 /* shift T for next block if any */
109 if (length > XTS_BLOCK_SIZE)
110 xts_shift(&T, &T);
111 }
112
113 /* if the last block is partial, handle via stealing */
114 if (length)
115 {
116 /* S Holds the real C(n-1) (Whole last block to steal from) */
117 union nettle_block16 S;
118
119 memxor3(P.b, src, T.b, XTS_BLOCK_SIZE); /* P -> PP */
120 encf(enc_ctx, XTS_BLOCK_SIZE, S.b, P.b); /* CC */
121 memxor(S.b, T.b, XTS_BLOCK_SIZE); /* CC -> S */
122
123 /* shift T for next block */
124 xts_shift(&T, &T);
125
126 length -= XTS_BLOCK_SIZE;
127 src += XTS_BLOCK_SIZE;
128
129 memxor3(P.b, src, T.b, length); /* P |.. */
130 /* steal ciphertext to complete block */
131 memxor3(P.b + length, S.b + length, T.b + length,
132 XTS_BLOCK_SIZE - length); /* ..| S_2 -> PP */
133
134 encf(enc_ctx, XTS_BLOCK_SIZE, dst, P.b); /* CC */
135 memxor(dst, T.b, XTS_BLOCK_SIZE); /* CC -> C(n-1) */
136
137 /* Do this after we read src so inplace operations do not break */
138 dst += XTS_BLOCK_SIZE;
139 memcpy(dst, S.b, length); /* S_1 -> C(n) */
140 }
141 }
142
143 void
xts_decrypt_message(const void * dec_ctx,const void * twk_ctx,nettle_cipher_func * decf,nettle_cipher_func * encf,const uint8_t * tweak,size_t length,uint8_t * dst,const uint8_t * src)144 xts_decrypt_message(const void *dec_ctx, const void *twk_ctx,
145 nettle_cipher_func *decf, nettle_cipher_func *encf,
146 const uint8_t *tweak, size_t length,
147 uint8_t *dst, const uint8_t *src)
148 {
149 union nettle_block16 T;
150 union nettle_block16 C;
151
152 check_length(length, dst);
153
154 encf(twk_ctx, XTS_BLOCK_SIZE, T.b, tweak);
155
156 for (;length >= 2 * XTS_BLOCK_SIZE || length == XTS_BLOCK_SIZE;
157 length -= XTS_BLOCK_SIZE, src += XTS_BLOCK_SIZE, dst += XTS_BLOCK_SIZE)
158 {
159 memxor3(C.b, src, T.b, XTS_BLOCK_SIZE); /* c -> CC */
160 decf(dec_ctx, XTS_BLOCK_SIZE, dst, C.b); /* PP */
161 memxor(dst, T.b, XTS_BLOCK_SIZE); /* PP -> P */
162
163 /* shift T for next block if any */
164 if (length > XTS_BLOCK_SIZE)
165 xts_shift(&T, &T);
166 }
167
168 /* if the last block is partial, handle via stealing */
169 if (length)
170 {
171 union nettle_block16 T1;
172 /* S Holds the real P(n) (with part of stolen ciphertext) */
173 union nettle_block16 S;
174
175 /* we need the last T(n) and save the T(n-1) for later */
176 xts_shift(&T1, &T);
177
178 memxor3(C.b, src, T1.b, XTS_BLOCK_SIZE); /* C -> CC */
179 decf(dec_ctx, XTS_BLOCK_SIZE, S.b, C.b); /* PP */
180 memxor(S.b, T1.b, XTS_BLOCK_SIZE); /* PP -> S */
181
182 /* process next block (Pn-1) */
183 length -= XTS_BLOCK_SIZE;
184 src += XTS_BLOCK_SIZE;
185
186 /* Prepare C, P holds the real P(n) */
187 memxor3(C.b, src, T.b, length); /* C_1 |.. */
188 memxor3(C.b + length, S.b + length, T.b + length,
189 XTS_BLOCK_SIZE - length); /* ..| S_2 -> CC */
190 decf(dec_ctx, XTS_BLOCK_SIZE, dst, C.b); /* PP */
191 memxor(dst, T.b, XTS_BLOCK_SIZE); /* PP -> P(n-1) */
192
193 /* Do this after we read src so inplace operations do not break */
194 dst += XTS_BLOCK_SIZE;
195 memcpy(dst, S.b, length); /* S_1 -> P(n) */
196 }
197 }
198