Disguise format preserving encryption as OTP encryption

[Stefan Claas]

Hi all,

echo -n 'Merry Christmas and a Happy New Year' | base16 -l 0
4d65727279204368726973746d617320616e642061204861707079204e65772059656172

Now we encrypt this message with fpe, a 256 bit key and a 64 bit nonce:

ca94a7a70929a2eb44faf7a9195541be16a97ab17e0a40cd95c81978f14fcdf6b76892ae

After that we convert the hex string to decimal

393547191367737629111313439284388256222575714261460221423875982235587707334230765245102

and finally group the string into 5 digits groups, to have an OTP
look a like message. :-)

39354 71913 67737 62911 13134 39284 38825 62225 75714 26146
02214 23875 98223 55877 07334 23076 52451 02

This is just for fun, but shows also for what hex2dec and vice versa
converters can be used.

Merry Christmas
Stefan

[Rich]

Post by Stefan Claas
Hi all,
echo -n 'Merry Christmas and a Happy New Year' | base16 -l 0
4d65727279204368726973746d617320616e642061204861707079204e65772059656172
ca94a7a70929a2eb44faf7a9195541be16a97ab17e0a40cd95c81978f14fcdf6b76892ae
After that we convert the hex string to decimal
393547191367737629111313439284388256222575714261460221423875982235587707334230765245102
and finally group the string into 5 digits groups, to have an OTP
look a like message. :-)
39354 71913 67737 62911 13134 39284 38825 62225 75714 26146
02214 23875 98223 55877 07334 23076 52451 02
This is just for fun, but shows also for what hex2dec and vice versa
converters can be used.

Note that conversion to decimal is not required for grouping into
groups of five. The hex message can just as easily be grouped into
five digit groupings:

ca94a 7a709 29a2e b44fa f7a91 95541 be16a 97ab1 7e0a4 0cd95
c8197 8f14f cdf6b 76892 ae

Alternately, using the Ascii85 scheme
(https://en.wikipedia.org/wiki/Ascii85) you can get a smaller
"message":

$ rlwrap tclsh
% set binary [binary decode hex ca94a7a70929a2eb44faf7a9195541be16a97ab17e0a40cd95c81978f14fcdf6b76892ae] ; list
% package require ascii85
1.0
% ascii85::encode -maxlen 0 $binary
b*8g%#q;V77/HYW)-&u:(9)VbIL8?bQ,***@F'[qLr-

Which can itself be "grouped" if one likes:

b*8g% #q;V7 7/HYW )-&u: (9)Vb IL8?b Q,jhf ***@F' [qLr-

Of course, having a coms channel that passes binary data would avoid
needing to 'encode' the mesage as any of the "text/ascii" formats.

[Stefan Claas]

Post by Rich

Post by Stefan Claas
This is just for fun, but shows also for what hex2dec and vice versa
converters can be used.

Note that conversion to decimal is not required for grouping into
groups of five. The hex message can just as easily be grouped into
ca94a 7a709 29a2e b44fa f7a91 95541 be16a 97ab1 7e0a4 0cd95
c8197 8f14f cdf6b 76892 ae

Yes, but in classic OTP messages I have never seen hex usage.

Post by Rich
Alternately, using the Ascii85 scheme
(https://en.wikipedia.org/wiki/Ascii85) you can get a smaller
$ rlwrap tclsh
% set binary [binary decode hex
ca94a7a70929a2eb44faf7a9195541be16a97ab17e0a40cd95c81978f14fcdf6b76892ae]
; list % package require ascii85 1.0
% ascii85::encode -maxlen 0 $binary

Or one uses base91, which is a bit more smaller.

Post by Rich
Of course, having a coms channel that passes binary data would avoid
needing to 'encode' the mesage as any of the "text/ascii" formats.

Yes. Nice tools for that, like croc, magic-wormhole, OnionShare etc.
are available on GitHub, for example.

Regards
Stefan

[Rich]

Post by Stefan Claas

Post by Rich

Post by Stefan Claas
This is just for fun, but shows also for what hex2dec and vice versa
converters can be used.

Note that conversion to decimal is not required for grouping into
groups of five. The hex message can just as easily be grouped into
ca94a 7a709 29a2e b44fa f7a91 95541 be16a 97ab1 7e0a4 0cd95
c8197 8f14f cdf6b 76892 ae

Yes, but in classic OTP messages I have never seen hex usage.

Most likely due to 'classic OTP' being done by hand, using actual paper
pads of random numbers (that's where the "pad" part of the OTP name
derives from, an actual "note pad" style paper device:
(Loading Image...).

If performing the encrypt/decrypt by hand, it is likely easier to have
the pad be all decimal and leverage human base10 numbers vs.
additionally training each and every spy the meaning of hex values (or
other bases).

Post by Stefan Claas

Post by Rich
Alternately, using the Ascii85 scheme
(https://en.wikipedia.org/wiki/Ascii85) you can get a smaller
$ rlwrap tclsh
% set binary [binary decode hex
ca94a7a70929a2eb44faf7a9195541be16a97ab17e0a40cd95c81978f14fcdf6b76892ae]
; list % package require ascii85 1.0
% ascii85::encode -maxlen 0 $binary

Or one uses base91, which is a bit more smaller.

Indeed, I was not aware that someone had one-upped ascii85. Base91 is
approaching about as tight as a scheme can get and still use only the
printable 7-bit ASCII code points.

[Stefan Claas]

Post by Rich

Post by Stefan Claas
Or one uses base91, which is a bit more smaller.

Indeed, I was not aware that someone had one-upped ascii85. Base91
is approaching about as tight as a scheme can get and still use only
the printable 7-bit ASCII code points.

I just figured out that one can use base91 with base26 to encode small
binary blobs for the Diana Cryptosystem. :-)

Regards
Stefan

[Stefan Claas]

Post by Stefan Claas
I just figured out that one can use base91 with base26 to encode small
binary blobs for the Diana Cryptosystem. :-)

And now I have a base26 Encoder/Decoder, which handles Unicode nicely,
according to a small test.

VCGBPEBELEAEGBMEAEXDGBLEVDBEUBVDKEREIEMEGBVDHEFEFENEGEBEMEREGBTD
GBAETDIEIEREGBGEXDPEGBREXDTDKEGBYBWBYBACHB

https://github.com/stefanclaas/base26

Regards
Stefan

[Rich]

Post by Stefan Claas

Post by Rich

Post by Stefan Claas
Or one uses base91, which is a bit more smaller.

Indeed, I was not aware that someone had one-upped ascii85. Base91
is approaching about as tight as a scheme can get and still use only
the printable 7-bit ASCII code points.

I just figured out that one can use base91 with base26 to encode small
binary blobs for the Diana Cryptosystem. :-)

But, why double up. If base26 already encodes binary, there is no
advantage to first base91 encoding it. All you achieve is further
increasing the size.

[Stefan Claas]

Post by Rich

Post by Stefan Claas
I just figured out that one can use base91 with base26 to encode
small binary blobs for the Diana Cryptosystem. :-)

But, why double up. If base26 already encodes binary, there is no
advantage to first base91 encoding it. All you achieve is further
increasing the size.

As understood, base26 is not meant to handle binary and the various
implementations, I have seen, work all differently. But I could be
wrong of course.

Regards
Stefan

[Rich]

Post by Stefan Claas

Post by Rich

Post by Stefan Claas
I just figured out that one can use base91 with base26 to encode
small binary blobs for the Diana Cryptosystem. :-)

But, why double up. If base26 already encodes binary, there is no
advantage to first base91 encoding it. All you achieve is further
increasing the size.

As understood, base26 is not meant to handle binary and the various
implementations, I have seen, work all differently. But I could be
wrong of course.

All the other "baseXX" text encoding schemes are meant for encoding
binary data into a textual form that can pass through non-binary clean
communications methods. It would be unusual if a scheme named "base26"
was somehow different and unable to encode binary data into text. With
that said, a quick search shows that there is no explicit "base26"
encoding scheme, so it may just be that no one defined one yet to fit
with the others.

Although unless one is restricted on only the 26 English letters, using
one of the more compact schemes (base64, base85) reduces bloat. A
'base26' encoding could encode a max of four bits per letter, which
makes it the same 'expansion' factor as hex encoding, just using
letters instead of numerals and letters.

[Stefan Claas]

Post by Rich
Although unless one is restricted on only the 26 English letters,
using one of the more compact schemes (base64, base85) reduces bloat.
A 'base26' encoding could encode a max of four bits per letter,
which makes it the same 'expansion' factor as hex encoding, just
using letters instead of numerals and letters.

The idea behind my base26 Encoder/Decoder was to use it with, for
example, the Diana Cryptosystem, without a Signal Book, or Code Book.

Thus allowing people, speaking foreign languages, to use Diana as well.

It makes the messages much longer, of course, but until I create a
Signal Book, for my city, it will be a good replacement.

Example plain text, in German:

"Treffen heute Abend, um 20:00 Uhr am großen See, zur Sylvester Party."

Clear text for Diana (fiver-groups):

TREFF ENHEU TEABE DUM [Code group for time] AMGRO SSENS EEZUR SYLVE
STERP ARTY

Same message clearcode, base26:

GDKEX DYDYD XDGEG BAEXD NEMEX DGBNC UDXDG EWDSB GBNEF EGBYB
WBGCW BWBGB HDAEK EGBTD FEGBZ DKEHE NHDGX DGEGB FDXDX DSBGB
SENEK EGBFD REEEO EXDLE MEXDK EGBCD TDKEM EREUB

So, with an offline Computer and base26, one can use Diana
with any language.

P.S. same goes for my hex/dec Encoder/Decoder to use any
language with OTPs, consiting of digits.

Regards
Stefan

[Rich]

Post by Stefan Claas

Post by Rich
Although unless one is restricted on only the 26 English letters,
using one of the more compact schemes (base64, base85) reduces bloat.
A 'base26' encoding could encode a max of four bits per letter,
which makes it the same 'expansion' factor as hex encoding, just
using letters instead of numerals and letters.

The idea behind my base26 Encoder/Decoder was to use it with, for
example, the Diana Cryptosystem, without a Signal Book, or Code Book.
Thus allowing people, speaking foreign languages, to use Diana as well.
It makes the messages much longer, of course, but until I create a
Signal Book, for my city, it will be a good replacement.
"Treffen heute Abend, um 20:00 Uhr am großen See, zur Sylvester Party."
TREFF ENHEU TEABE DUM [Code group for time] AMGRO SSENS EEZUR SYLVE
STERP ARTY
GDKEX DYDYD XDGEG BAEXD NEMEX DGBNC UDXDG EWDSB GBNEF EGBYB
WBGCW BWBGB HDAEK EGBTD FEGBZ DKEHE NHDGX DGEGB FDXDX DSBGB
SENEK EGBFD REEEO EXDLE MEXDK EGBCD TDKEM EREUB
So, with an offline Computer and base26, one can use Diana
with any language.

In which case you don't need to baseXX and then base26. Just define
your own base26 that is a binary to text encoder. It is effectively
just a "hex" encoder with each of zero through nine replaced by an
English alphabet letter. So you could just "hex" encode using an
existing hex encoder library (saving yourself the trouble of writing
'bit twiddling' code), and then just character map zero through nine
onto letters. You could do the map in at least two simple ways:

Input: 0123456789ABCDEF
Output: GHIJKLMNOPABCDEF

Input: 0123456789ABCDEF
Output: ABCDEFGHIJKLMNOP

[Stefan Claas]

Post by Stefan Claas
So, with an offline Computer and base26, one can use Diana
with any language.

In which case you don't need to baseXX and then base26. [...]

Correct! Now my base26 Encoder/Decoder handles Unicode.

Regards
Stefan

[Stefan Claas]

Post by Stefan Claas
Correct! Now my base26 Encoder/Decoder handles Unicode.

$ echo -n '祝你新年快乐' | base26 | ug -g
XIJGB GUIHH EGWIU FUGVI DHYGV IJHPG UIDHO F

$ echo -n 'XIJGB GUIHH EGWIU FUGVI DHYGV IJHPG UIDHO F' | ug | base26 -d
祝你新年快乐

Regards
Stefan

[Marcel Logen]

Post by Stefan Claas
echo -n 'Merry Christmas and a Happy New Year' | base16 -l 0
4d65727279204368726973746d617320616e642061204861707079204e65772059656172
ca94a7a70929a2eb44faf7a9195541be16a97ab17e0a40cd95c81978f14fcdf6b76892ae
After that we convert the hex string to decimal
393547191367737629111313439284388256222575714261460221423875982235587707334230765245102

If the FPE ciphertext (accidentally) begins with "00" then there
is a problem to decode the decimal value back to hex, I think:

| ***@o15:/tmp$ BC_LINE_LENGTH=0 bc -q
| ibase=16
| 0094A7A70929A2EB44FAF7A9195541BE16A97AB17E0A40CD95C81978F14FCDF6B76892AE
| 1128075138140356785582134106037437080809532772928038131009875468329041722778648613550

| ***@o15:/tmp$ BC_LINE_LENGTH=0 bc -q
| obase=16
| 1128075138140356785582134106037437080809532772928038131009875468329041722778648613550
| 94A7A70929A2EB44FAF7A9195541BE16A97AB17E0A40CD95C81978F14FCDF6B76892AE

Post by Stefan Claas
Merry Christmas

Thanks. Same to you.

Marcel

[Stefan Claas]

Post by Marcel Logen

Post by Stefan Claas
echo -n 'Merry Christmas and a Happy New Year' | base16 -l 0
4d65727279204368726973746d617320616e642061204861707079204e65772059656172
ca94a7a70929a2eb44faf7a9195541be16a97ab17e0a40cd95c81978f14fcdf6b76892ae
After that we convert the hex string to decimal
393547191367737629111313439284388256222575714261460221423875982235587707334230765245102

If the FPE ciphertext (accidentally) begins with "00" then there
| ibase=16
|
0094A7A70929A2EB44FAF7A9195541BE16A97AB17E0A40CD95C81978F14FCDF6B76892AE
|
1128075138140356785582134106037437080809532772928038131009875468329041722778648613550
| obase=16
|
1128075138140356785582134106037437080809532772928038131009875468329041722778648613550
|
94A7A70929A2EB44FAF7A9195541BE16A97AB17E0A40CD95C81978F14FCDF6B76892AE

Mmmh, if you prepend the zeros to my message, you get the correct
decimal value. Your message is IMHO completely different, because
yours begins with (00)94 and not (00)ca, or am I wrong?

And should this happen, one could choose a new nonce, for the message,
I would say.

Regards
Stefan

[Marcel Logen]

[...]

Post by Stefan Claas

Post by Marcel Logen
If the FPE ciphertext (accidentally) begins with "00" then there

[...]

Post by Stefan Claas
Mmmh, if you prepend the zeros to my message, you get the correct
decimal value. Your message is IMHO completely different, because
yours begins with (00)94 and not (00)ca, or am I wrong?

This was simply a (constructed) example for clarification
of the problem.

Post by Stefan Claas
And should this happen, one could choose a new nonce, for the message,
I would say.

This could be a solution, yes. However, it should be detected
and performed automatically by the FPE encryption routine.

Marcel

[Jakob Bohm]

Post by Marcel Logen
[...]

Post by Stefan Claas

Post by Marcel Logen
If the FPE ciphertext (accidentally) begins with "00" then there

[...]

Post by Stefan Claas
Mmmh, if you prepend the zeros to my message, you get the correct
decimal value. Your message is IMHO completely different, because
yours begins with (00)94 and not (00)ca, or am I wrong?

This was simply a (constructed) example for clarification
of the problem.

Post by Stefan Claas
And should this happen, one could choose a new nonce, for the message,
I would say.

This could be a solution, yes. However, it should be detected
and performed automatically by the FPE encryption routine.

Or just define the scheme to include enough leading zeroes to represent
all messages of the same number of bits, just like paper-based OTP ends
up with 0 as the first digit of about 10% of the messages (because the
secret digits are completely random and unrelated to the message).

With the command line tools this can be done as follows:

1. note the length of the actual hex string

2. Create a test hex string of the same length but all the hexits are F

3. Convert that test hex string to decimal.

4. note the length of the test decimal string

5. Output enough leading zeroes to make the actual decimal string as
long as the test decimal string.

6. To avoid creating side channel attacks, do steps 1 to 4 before
actually encrypting any message, based on how long the encrypted form of
messages would be. This takes a bit of arithmetic skill.


Enjoy

Jakob

[Marcel Logen]

Post by Jakob Bohm

Post by Marcel Logen

Post by Stefan Claas

Post by Marcel Logen
If the FPE ciphertext (accidentally) begins with "00" then there

[...]

Post by Stefan Claas
Mmmh, if you prepend the zeros to my message, you get the correct
decimal value. Your message is IMHO completely different, because
yours begins with (00)94 and not (00)ca, or am I wrong?

This was simply a (constructed) example for clarification
of the problem.

Post by Stefan Claas
And should this happen, one could choose a new nonce, for the message,
I would say.

This could be a solution, yes. However, it should be detected
and performed automatically by the FPE encryption routine.

Or just define the scheme to include enough leading zeroes to represent
all messages of the same number of bits, just like paper-based OTP ends
up with 0 as the first digit of about 10% of the messages (because the
secret digits are completely random and unrelated to the message).
1. note the length of the actual hex string
2. Create a test hex string of the same length but all the hexits are F
3. Convert that test hex string to decimal.
4. note the length of the test decimal string
5. Output enough leading zeroes to make the actual decimal string as
long as the test decimal string.

Does this actually solve the problem (hex string begins with
"0" and this zero has to be restored by converting decimal to
hex)? ... pondering ...

Post by Jakob Bohm
6. To avoid creating side channel attacks, do steps 1 to 4 before
actually encrypting any message, based on how long the encrypted form of
messages would be. This takes a bit of arithmetic skill.

Here my pre-computation of 1. to 4. (with GNU bash and GNU bc):

| ***@o15:/tmp$ cat script.bash
| #!/usr/bin/bash
| for i in {2..100..2}
| do var='' &&
| echo -n "$i " &&
| for j in $(seq "$i")
| do var="$var"'F'
| done &&
| echo "$var" &&
| echo -n "$i " &&
| xar=$( echo "ibase=16; ${var}" | BC_LINE_LENGTH=0 bc ) &&
| echo "$xar" && echo -n "$i " &&
| echo "$(( $( echo $xar | wc -c ) - 1 ))" &&
| echo
| done

| ***@o15:/tmp$ ./script.bash
| 2 FF
| 2 255
| 2 3
|
| 4 FFFF
| 4 65535
| 4 5
|
| 6 FFFFFF
| 6 16777215
| 6 8
|
| 8 FFFFFFFF
| 8 4294967295
| 8 10
|
| 10 FFFFFFFFFF
| 10 1099511627775
| 10 13
|
| 12 FFFFFFFFFFFF
| 12 281474976710655
| 12 15
|
[...]
| 96 FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF
| 96 39402006196394479212279040100143613805079739270465446667948293404245721771497210611414266254884915640806627990306815
| 96 116
|
| 98 FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF
| 98 10086913586276986678343434265636765134100413253239154346994763111486904773503285916522052161250538404046496765518544895
| 98 119
|
| 100 FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF
| 100 2582249878086908589655919172003011874329705792829223512830659356540647622016841194629645353280137831435903171972747493375
| 100 121
|

Marcel