1// Copyright 2017 The Chromium Authors. All rights reserved.
2// Copyright (C) 2018 Apple Inc. All rights reserved.
3//
4// Redistribution and use in source and binary forms, with or without
5// modification, are permitted provided that the following conditions are
6// met:
7//
8// * Redistributions of source code must retain the above copyright
9// notice, this list of conditions and the following disclaimer.
10// * Redistributions in binary form must reproduce the above
11// copyright notice, this list of conditions and the following disclaimer
12// in the documentation and/or other materials provided with the
13// distribution.
14// * Neither the name of Google Inc. nor the names of its
15// contributors may be used to endorse or promote products derived from
16// this software without specific prior written permission.
17//
18// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
19// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
20// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
21// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
22// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
23// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
24// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
25// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
26// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
27// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
28// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
29
30#include "config.h"
31#include "CBORReader.h"
32
33#if ENABLE(WEB_AUTHN)
34
35#include "CBORBinary.h"
36#include <limits>
37#include <utility>
38
39namespace cbor {
40
41namespace {
42
43CBORValue::Type getMajorType(uint8_t initialDataByte)
44{
45 return static_cast<CBORValue::Type>((initialDataByte & constants::kMajorTypeMask) >> constants::kMajorTypeBitShift);
46}
47
48uint8_t getAdditionalInfo(uint8_t initialDataByte)
49{
50 return initialDataByte & constants::kAdditionalInformationMask;
51}
52
53// Error messages that correspond to each of the error codes.
54const char kNoError[] = "Successfully deserialized to a CBOR value.";
55const char kUnsupportedMajorType[] = "Unsupported major type.";
56const char kUnknownAdditionalInfo[] = "Unknown additional info format in the first byte.";
57const char kIncompleteCBORData[] = "Prematurely terminated CBOR data byte array.";
58const char kIncorrectMapKeyType[] = "Map keys other than utf-8 encoded strings are not allowed.";
59const char kTooMuchNesting[] = "Too much nesting.";
60const char kInvalidUTF8[] = "String encoding other than utf8 are not allowed.";
61const char kExtraneousData[] = "Trailing data bytes are not allowed.";
62const char kDuplicateKey[] = "Duplicate map keys are not allowed.";
63const char kMapKeyOutOfOrder[] = "Map keys must be sorted by byte length and then by byte-wise lexical order.";
64const char kNonMinimalCBOREncoding[] = "Unsigned integers must be encoded with minimum number of bytes.";
65const char kUnsupportedSimpleValue[] = "Unsupported or unassigned simple value.";
66const char kUnsupportedFloatingPointValue[] = "Floating point numbers are not supported.";
67const char kOutOfRangeIntegerValue[] = "Integer values must be between INT64_MIN and INT64_MAX.";
68
69} // namespace
70
71CBORReader::CBORReader(Bytes::const_iterator it, Bytes::const_iterator end)
72 : m_it(it)
73 , m_end(end)
74 , m_errorCode(DecoderError::CBORNoError)
75{
76}
77
78CBORReader::~CBORReader()
79{
80}
81
82// static
83Optional<CBORValue> CBORReader::read(const Bytes& data, DecoderError* errorCodeOut, int maxNestingLevel)
84{
85 CBORReader reader(data.begin(), data.end());
86 Optional<CBORValue> decodedCbor = reader.decodeCBOR(maxNestingLevel);
87
88 if (decodedCbor)
89 reader.checkExtraneousData();
90 if (errorCodeOut)
91 *errorCodeOut = reader.getErrorCode();
92
93 if (reader.getErrorCode() != DecoderError::CBORNoError)
94 return WTF::nullopt;
95 return decodedCbor;
96}
97
98Optional<CBORValue> CBORReader::decodeCBOR(int maxNestingLevel)
99{
100 if (maxNestingLevel < 0 || maxNestingLevel > kCBORMaxDepth) {
101 m_errorCode = DecoderError::TooMuchNesting;
102 return WTF::nullopt;
103 }
104
105 if (!canConsume(1)) {
106 m_errorCode = DecoderError::IncompleteCBORData;
107 return WTF::nullopt;
108 }
109
110 const uint8_t initialByte = *m_it++;
111 const auto major_type = getMajorType(initialByte);
112 const uint8_t additionalInfo = getAdditionalInfo(initialByte);
113
114 uint64_t value;
115 if (!readVariadicLengthInteger(additionalInfo, &value))
116 return WTF::nullopt;
117
118 switch (major_type) {
119 case CBORValue::Type::Unsigned:
120 return decodeValueToUnsigned(value);
121 case CBORValue::Type::Negative:
122 return decodeValueToNegative(value);
123 case CBORValue::Type::ByteString:
124 return readBytes(value);
125 case CBORValue::Type::String:
126 return readString(value);
127 case CBORValue::Type::Array:
128 return readCBORArray(value, maxNestingLevel);
129 case CBORValue::Type::Map:
130 return readCBORMap(value, maxNestingLevel);
131 case CBORValue::Type::SimpleValue:
132 return readSimpleValue(additionalInfo, value);
133 case CBORValue::Type::None:
134 break;
135 }
136
137 m_errorCode = DecoderError::UnsupportedMajorType;
138 return WTF::nullopt;
139}
140
141bool CBORReader::readVariadicLengthInteger(uint8_t additionalInfo, uint64_t* value)
142{
143 uint8_t additionalBytes = 0;
144 if (additionalInfo < 24) {
145 *value = additionalInfo;
146 return true;
147 }
148
149 if (additionalInfo == 24)
150 additionalBytes = 1;
151 else if (additionalInfo == 25)
152 additionalBytes = 2;
153 else if (additionalInfo == 26)
154 additionalBytes = 4;
155 else if (additionalInfo == 27)
156 additionalBytes = 8;
157 else {
158 m_errorCode = DecoderError::UnknownAdditionalInfo;
159 return false;
160 }
161
162 if (!canConsume(additionalBytes)) {
163 m_errorCode = DecoderError::IncompleteCBORData;
164 return false;
165 }
166
167 uint64_t intData = 0;
168 for (uint8_t i = 0; i < additionalBytes; ++i) {
169 intData <<= 8;
170 intData |= *m_it++;
171 }
172
173 *value = intData;
174 return checkMinimalEncoding(additionalBytes, intData);
175}
176
177Optional<CBORValue> CBORReader::decodeValueToNegative(uint64_t value)
178{
179 if (value > static_cast<uint64_t>(std::numeric_limits<int64_t>::max())) {
180 m_errorCode = DecoderError::OutOfRangeIntegerValue;
181 return WTF::nullopt;
182 }
183 return CBORValue(-static_cast<int64_t>(value) - 1);
184}
185
186Optional<CBORValue> CBORReader::decodeValueToUnsigned(uint64_t value)
187{
188 if (value > static_cast<uint64_t>(std::numeric_limits<int64_t>::max())) {
189 m_errorCode = DecoderError::OutOfRangeIntegerValue;
190 return WTF::nullopt;
191 }
192 return CBORValue(static_cast<int64_t>(value));
193}
194
195Optional<CBORValue> CBORReader::readSimpleValue(uint8_t additionalInfo, uint64_t value)
196{
197 // Floating point numbers are not supported.
198 if (additionalInfo > 24 && additionalInfo < 28) {
199 m_errorCode = DecoderError::UnsupportedFloatingPointValue;
200 return WTF::nullopt;
201 }
202
203 ASSERT(value <= 255u);
204 CBORValue::SimpleValue possiblyUnsupportedSimpleValue = static_cast<CBORValue::SimpleValue>(static_cast<int>(value));
205 switch (possiblyUnsupportedSimpleValue) {
206 case CBORValue::SimpleValue::FalseValue:
207 case CBORValue::SimpleValue::TrueValue:
208 case CBORValue::SimpleValue::NullValue:
209 case CBORValue::SimpleValue::Undefined:
210 return CBORValue(possiblyUnsupportedSimpleValue);
211 }
212
213 m_errorCode = DecoderError::UnsupportedSimpleValue;
214 return WTF::nullopt;
215}
216
217Optional<CBORValue> CBORReader::readString(uint64_t numBytes)
218{
219 if (!canConsume(numBytes)) {
220 m_errorCode = DecoderError::IncompleteCBORData;
221 return WTF::nullopt;
222 }
223
224 ASSERT(numBytes <= std::numeric_limits<size_t>::max());
225 String cborString = String::fromUTF8(m_it, static_cast<size_t>(numBytes));
226 m_it += numBytes;
227
228 // Invalid UTF8 bytes produce an empty WTFString.
229 // Not to confuse it with an actual empty WTFString.
230 if (!numBytes || hasValidUTF8Format(cborString))
231 return CBORValue(WTFMove(cborString));
232 return WTF::nullopt;
233}
234
235Optional<CBORValue> CBORReader::readBytes(uint64_t numBytes)
236{
237 if (!canConsume(numBytes)) {
238 m_errorCode = DecoderError::IncompleteCBORData;
239 return WTF::nullopt;
240 }
241
242 Bytes cborByteString;
243 ASSERT(numBytes <= std::numeric_limits<size_t>::max());
244 cborByteString.append(m_it, static_cast<size_t>(numBytes));
245 m_it += numBytes;
246
247 return CBORValue(WTFMove(cborByteString));
248}
249
250Optional<CBORValue> CBORReader::readCBORArray(uint64_t length, int maxNestingLevel)
251{
252 CBORValue::ArrayValue cborArray;
253 while (length-- > 0) {
254 Optional<CBORValue> cborElement = decodeCBOR(maxNestingLevel - 1);
255 if (!cborElement)
256 return WTF::nullopt;
257 cborArray.append(WTFMove(cborElement.value()));
258 }
259 return CBORValue(WTFMove(cborArray));
260}
261
262Optional<CBORValue> CBORReader::readCBORMap(uint64_t length, int maxNestingLevel)
263{
264 CBORValue::MapValue cborMap;
265 while (length-- > 0) {
266 Optional<CBORValue> key = decodeCBOR(maxNestingLevel - 1);
267 Optional<CBORValue> value = decodeCBOR(maxNestingLevel - 1);
268 if (!key || !value)
269 return WTF::nullopt;
270
271 // Only CBOR maps with integer or string type keys are allowed.
272 if (key.value().type() != CBORValue::Type::String && key.value().type() != CBORValue::Type::Unsigned) {
273 m_errorCode = DecoderError::IncorrectMapKeyType;
274 return WTF::nullopt;
275 }
276 if (!checkDuplicateKey(key.value(), cborMap) || !checkOutOfOrderKey(key.value(), cborMap))
277 return WTF::nullopt;
278
279 cborMap.emplace(std::make_pair(WTFMove(key.value()), WTFMove(value.value())));
280 }
281 return CBORValue(WTFMove(cborMap));
282}
283
284bool CBORReader::canConsume(uint64_t bytes)
285{
286 if (static_cast<uint64_t>(std::distance(m_it, m_end)) >= bytes)
287 return true;
288 m_errorCode = DecoderError::IncompleteCBORData;
289 return false;
290}
291
292bool CBORReader::checkMinimalEncoding(uint8_t additionalBytes, uint64_t uintData)
293{
294 if ((additionalBytes == 1 && uintData < 24) || uintData <= (1ULL << 8 * (additionalBytes >> 1)) - 1) {
295 m_errorCode = DecoderError::NonMinimalCBOREncoding;
296 return false;
297 }
298 return true;
299}
300
301void CBORReader::checkExtraneousData()
302{
303 if (m_it != m_end)
304 m_errorCode = DecoderError::ExtraneousData;
305}
306
307bool CBORReader::checkDuplicateKey(const CBORValue& newKey, const CBORValue::MapValue& map)
308{
309 if (map.find(newKey) != map.end()) {
310 m_errorCode = DecoderError::DuplicateKey;
311 return false;
312 }
313 return true;
314}
315
316bool CBORReader::hasValidUTF8Format(const String& stringData)
317{
318 // Invalid UTF8 bytes produce an empty WTFString.
319 if (stringData.isEmpty()) {
320 m_errorCode = DecoderError::InvalidUTF8;
321 return false;
322 }
323 return true;
324}
325
326bool CBORReader::checkOutOfOrderKey(const CBORValue& newKey, const CBORValue::MapValue& map)
327{
328 auto comparator = map.key_comp();
329 if (!map.empty() && comparator(newKey, map.rbegin()->first)) {
330 m_errorCode = DecoderError::OutOfOrderKey;
331 return false;
332 }
333 return true;
334}
335
336CBORReader::DecoderError CBORReader::getErrorCode()
337{
338 return m_errorCode;
339}
340
341// static
342const char* CBORReader::errorCodeToString(DecoderError error)
343{
344 switch (error) {
345 case DecoderError::CBORNoError:
346 return kNoError;
347 case DecoderError::UnsupportedMajorType:
348 return kUnsupportedMajorType;
349 case DecoderError::UnknownAdditionalInfo:
350 return kUnknownAdditionalInfo;
351 case DecoderError::IncompleteCBORData:
352 return kIncompleteCBORData;
353 case DecoderError::IncorrectMapKeyType:
354 return kIncorrectMapKeyType;
355 case DecoderError::TooMuchNesting:
356 return kTooMuchNesting;
357 case DecoderError::InvalidUTF8:
358 return kInvalidUTF8;
359 case DecoderError::ExtraneousData:
360 return kExtraneousData;
361 case DecoderError::DuplicateKey:
362 return kDuplicateKey;
363 case DecoderError::OutOfOrderKey:
364 return kMapKeyOutOfOrder;
365 case DecoderError::NonMinimalCBOREncoding:
366 return kNonMinimalCBOREncoding;
367 case DecoderError::UnsupportedSimpleValue:
368 return kUnsupportedSimpleValue;
369 case DecoderError::UnsupportedFloatingPointValue:
370 return kUnsupportedFloatingPointValue;
371 case DecoderError::OutOfRangeIntegerValue:
372 return kOutOfRangeIntegerValue;
373 default:
374 ASSERT_NOT_REACHED();
375 return "Unknown error code.";
376 }
377}
378
379} // namespace cbor
380
381#endif // ENABLE(WEB_AUTHN)
382