Score:1

Crypto

Camellia 1.2.0: words with 0 at key table

devnull

7/1/23, 8:13 PM

Testing a code that uses the Camellia 1.2.0 source code, when generating a keyTable from the input key, using:

void Camellia_Ekeygen(const int keyBitLength, 
          const unsigned char *rawKey, 
          KEY_TABLE_TYPE keyTable)

The output shows a few 'zeroed' words at the same places. Two random examples for 256 bits:

E1AE67E4 07AE952B 94B0FCD1 CD366E1C 5160F1A8 45893AE8 0994EC20 1B5782AF

52027468 D2CEEB8F 00000000 00000000 5A44D15D 533F0EF8 E441183F 960616CE
B492E69C C71899DB 1C149A9E DA2EF3F9 C590DF1D 8ECE1AA3 5BF4C76A 517A719B
BA4E6211 083B6502 ABE0D506 6A3C58D4 32B152A6 C7D2AD48 2338FC75 4B1C4805
6FB9B4E4 4E14DA25 46CEF6AA D655F3C1 E89A9073 87CCF090 098D9E8F C73283B7
CD0F4BB9 E166D31C 7EE61ACE 52E97A40 0F5B9E82 4F98AEDE 91D08211 2E660D02
01506F57 40F9E4BA C2AB1164 196A9DE8 6E870140 C0A16094 F462E486 D98FF34F
F8543532 5ACAA32E 0046EFC7 06E9A0B9 42409189 9D9C0A16 EF580EC8 03E52B67
4D99620A B6A40197 3999A1B9 A9B45F27 6AE83BF0 7351AF36 6AEDF2EC 0A050076
B50EBD28 B9A2B34C 00000000 00000000


BE276A07 021C223F 40262C4B 2B07D216 AB51C522 C919C184 BBAD4565 B3050C87

93759D00 1DCE4C1F 00000000 00000000 91C6EBE1 47BE73E0 A1ECCAB9 B997E1E5
DEB11931 C13C15D2 EA9E2B5B 892BC368 BFD5F521 7B61B763 CB8C58B7 0AE271F1
617046B2 5951EB2E 2143C16C 4871D4EA 8AA8E801 3CD1E79E D64B23F5 DA983076
D6232073 5364BDE7 77FFE6AE B967FDE4 FDD26694 1720ECF0 6FC56EEE 3B618822
C46202F4 217DB0B2 A076E26B 23C22170 AD07C5E8 890AE608 EFC78526 F0F62449
7C712F1A D7CC710B C0FDB367 E97D2186 437CA739 F93D0CBF C90FF6E2 C879AA2B
511B3CF8 2E25C89E 7B745E74 CA705CCE 3DFD612D 1BE56472 FA45E7EA 4B3B85B0
95F84DCF 4C14FC95 20310BF7 A353A328 0E505958 A56CB1A1 007D2357 CC0239C8
4EFF9C31 2B9BEF19 00000000 00000000

Is this expected?

Clarification: the "hex" dumps above show two invocations of the function. For each one keyBitLength is set to 256, the shorter sequence (which fits in one line) is a random 256 bits key and what follows is the output of the function (copied to the keyTable buffer).

Another test: I was zeroing keyTable before calling the function. Now I've set all bytes do 0xFF and the zeroed words became: 0xFFFFFFFF. Scary. These words (always the same ones) are not being touched by the function.

Attempt to solve using standard types. I've also switched to -O0 compilation to avoid any optimization problems:

//typedef unsigned int KEY_TABLE_TYPE[CAMELLIA_TABLE_WORD_LEN];
/* u32 must be 32bit word */
//typedef unsigned int u32;
//typedef unsigned char u8;

#include <stdint.h> // this is the only change to the original  code (kept above):
typedef uint32_t KEY_TABLE_TYPE[CAMELLIA_TABLE_WORD_LEN];
typedef uint32_t u32;
typedef uint8_t u8;

I've uploaded a minimum test program here.

111

0 + 0

camellia

DannyNiu

7/2/23, 1:10 AM

The source code assumed `long` is 32-bit, which may not be true of 64-bit systems. Try substituting the type definition for `Word` with `uint32_t` at the beginning of the source code.

devnull

7/2/23, 10:25 AM

@DannyNiu. Thanks. I've tried that and updated the question (no change). I've also downloaded the source again and isolated a "minimum" test program which is reproducible for me (687 lines of code). Should I upload it here?

Maarten Bodewes

7/2/23, 11:17 AM

That's maybe a bit much, but you may of course put it somewhere where code snippets are allowed and put a link in the question. Personally I would try other code that is easy to compile (e.g. Bouncy Castle / Java) and then try to verify the values you've generated. Differences such as all-zero values etc. should be easy to spot.

Maarten Bodewes

7/2/23, 11:57 AM

Ugh, for anybody going that route, the BC specifies RFC 3713. I don't get the same values at all, I guess one is v1 and the other v2 of the Camelia cipher. Sigh, that's fit for another question I suppose.

devnull

7/2/23, 12:17 PM

@MaartenBodewes I've just downloaded the x86_64 asm version from the same page (first link at the top) and it generates a completely different keyTable (also without the 4 unused words). I've sent an email to the contact address at the same page and will report here any relevant answer.

Maarten Bodewes

7/3/23, 5:24 PM

I hope you get an answer, it is sometimes tricky to get answers from Japan :)

devnull

7/5/23, 3:43 PM

@MaartenBodewes. As you mentioned, no answer. I'm writing an answer to document this because the bug is clear now by inspecting the code.

Score:1

Crypto

devnull

7/5/23, 4:04 PM

While NTT looks into this, I'm posting this as a "solution":

By inspection of the function

void camellia_setup256(const unsigned char *key, u32 *subkey)

it is clear that all the accesses to the output vector 'subkey' are performed using the macros

#define CamelliaSubkeyL(INDEX) (subkey[(INDEX)*2])
#define CamelliaSubkeyR(INDEX) (subkey[(INDEX)*2 + 1])

Nowhere in the function are references to the indexes 1 and 33 to be found. These indexes would write to the word positions 2, 3, 66 and 67. These are the exact 4 words that are not written to in the tests.

The OpenSSL port of the Camellia cipher (Apache License 2.0) doesn't have this problem: assembly and c available.

Update:

I've compared the two ports above with the code from NTT linked in the question, as follows:

generate a random 256 bits key
generate a random 16 bytes block
with each of the 3 implementations encrypt the block to compare the ciphertext

Summary: despite the unused words in the keyTable for the NTT implementation, in all the millions of key/block pairs tested, all the ciphertexts generated by the 3 implementations matched.

Fix:

Since it doesn't affect the encryption/decryption, the fix only reduces the keyTable size from 68 to 64 words. Since the code is very clean and all accesses are performed with the two macros above, only 16 lines need to be changed (tested only with 256 bits keys):

Find all macros accessing the index 24 and change it to 1
Find all macros accessing the index 32 and change it to 24

I've tested this in the process described above.

0 + 0

Maarten Bodewes

7/5/23, 4:12 PM

Cool. Have you checked if you can fix the original code? That would be the ultimate proof. You can accept your own answer after 2 days time.

DannyNiu

7/8/23, 3:00 AM

The "Reference Code" to the *bottom* of [this page](https://info.isl.ntt.co.jp/crypt/eng/camellia/source/) contain the version that I've adapted for my hobbyist project (`long` -> `uint32_t`) for generating test vectors. This one seems to be working correctly.

devnull

7/9/23, 9:09 PM

@DannyNiu Thanks. I've described the fix and some tests above.

Elon Musk

I sit in a Tesla and translated this thread with Ai:

EN: Camellia 1.2.0: words with 0 at key table

TH: Camellia 1.2.0: คำที่มี 0 ที่ตารางคีย์

RO: Camellia 1.2.0: cuvinte cu 0 la tabelul cheie

RU: Camellia 1.2.0: слова с 0 в ключевой таблице

VI: Camellia 1.2.0: các từ có 0 ở bảng chính

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.