AN OPTIMAL BINARY MESSAGE PROTOCOL FOR STREAMING BITS
Author: Thotheolh ([email protected]).
Date: 11th November 2014.
The ideas within this paper are stated here independently with no awareness of any such protocols or ideas
existing which may have already existed. The usage of the ideas here in a production environment would be
at one's own risk.
A stream-based cryptographic protocol (One Time Pad or Stream Cipher) uses a bitstream of internal states
or a keystream to encrypt a bitstream of plaintext message. The security of the message depends on the size
of the bitstream of the internal state or keystream used as every bit of plaintext would be encrypted with
a corresponding bit from a keystream or internal state. In the event that the message is small in size
(weak message), the keystream or internal state would also be weak. Cryptanalysis via the message length
would be plausible and the application of bruteforce attacks would not be too far fetched for a weak message.
The successful bruteforcing and revelation of possible message, keys or cipher states used to encrypt the
message may allow other attacks to propagate and further reducing security of the message stream. In this
paper, I would like to define the security of a stream-based encrypted message with the formula of 2^N where
the N represents the bit length of the message. Using the concept of how a block cipher encrypts data in blocks,
messages can be made stronger to discourage bruteforce on a stream-based message.
The definition of the formula of 2^N as the security measurement for a stream-based cryptographic message is
used to determine the overall keystream or internal state bit size being used to encrypt a stream of message
assuming that the message is sent over a communication medium in short burst (message session). A further
extension of the formula under possible influence of a birthday attack would set the formula to an estimate of
An example of the application of this formula would be to predict the security measurement for a stream-based
encrypted message of the text "hello" in an 8 bit ASCII format which would be a 40 bit message that would yield
under 2^N formula a 2^40 bit security and after the application of a possible birthday attack, it would only
have about a 2^20 bit security. NIST guidelines under the SP800-57 and SP800-131 have proposed guidelines
for key length of at least 80 bits and the 40 bit security for the "hello" message using 40 bits of keystream or
internal state would not be adequate and under a birthday attack influence would reduce it to about a 20 bit
keystream or internal state.
The proposed method to increase the security of a stream-based cryptographic protocol is to extend the amount of
message bit length so that the message used would result in the use of keystream or internal state of an acceptable
length to discourage the use of bruteforce attacks. A recommended basic N size of 96 bits would give be more than
sufficient compared to an 80 bit security recommended by NIST and would theoretically be slightly slower than the
use of an 80 bit key but still fast enough for implementations that require fast encryption with small key sizes.
A recommended N size for standard messages that are not constrained or bound by the device or algorithm would be
using a 128 bit N size and for higher levels of security, a N size of 256 bits or more would be recommended.
Messages of suitable N sizes would be pack into blocks and sent off in block streams but encrypted as bit streams
which will be padded to fill the selected N size for each block. If the N size is selected with a strong size that
discourages bruteforce attacks via traffic analysis of the message length, the keystream bits or state used would
also be strong under the assumption that at least N size of keystream bits or state is used during cryptographic
The additional benefits of splitting messages into multiple blocks would also allow the control of message being sent
out to defeat traffic analysis and an attacker would not end up with the precise size of a message. An example would
be sending a N size of 129 bits message which uses a 129 bit keystream or state and that would mean the use of 2
message blocks with message bits that cannot fit into the first message block spilling into the second message block
with the rest of the message bits in the second block filled with padding bits. The total bits used would be a size of
256 bits which would give a higher N size making the cryptanalysis via bruteforce much more difficult and the actual
size of the message hidden from plain sight.
The proposed message protocol would utilize the N size formula in a practical sense to allow the implementation of
padding of random bits to hide the true size of the message. A defined number of bits would be placed in front of the
protocol to define the actual message size followed by the actual message bits and then followed by a random string of
filler padding bits. A 128 bit message would therefore not be able to fit a 128 bit N size block due to the header that
contains the message size bit indicator. The bit indicator size varies between different N size message blocks and will
be recommended later in this section.
The ASCII skeleton diagram of the protocol is shown below.
Message with N=128: [<---8 bits message size---><---message content---><---padding bits--->]
A program parser parsing such a message protocol would have to discern the message size of N to know how much of header
bits it would read in to find out the actual location and actual message positions within the block. For a 128 bit size
of N, an 8 bit message header that indicates the message content size would be used and the message content size would be
in integer format and then converted to bitstring appended as the header of the message. An example is a message of
29 bits which the header will represent as 00011101 in binary. Padding bits maybe randomly generated and appended behind
the message content or can be a predetermined value as long as the header bits are valid. A randomly generated padding
bitstring may provide an element of surprise and randomness for attackers.
Below is a list of recommended header size:
N <= 256 will use 8 bits header.
N <= 512 will use 9 bits header.
N <= 1024 will use 10 bits header.
N <= 2048 will use 11 bits header.
N <= 4096 will use 12 bits header.
N <= 8192 will use 13 bits header.
N <= 16284 will use 14 bits header.
It is also recommended to use uniform N sizes throughout a cryptographic communication session using stream-based
cryptography to repel possible attempts at traffic analysis of unequal message sizes.
With the use of wrapping messages into fixed size blocks, traffic analysis and bruteforce attacks against vulnerable message
with weak N sizes becomes much harder as the overall N size of the block makes up adequately following the 2^N and 2^(N/2)
formula to calculate the weak message sizes of a stream-based message sent out in sessions.
 Elaine Baker., Allen Roginsky. Transitions: Recommendation for Transitioning the Use of Cryptographic Algorithms and Key
Lengths, 2011, National Institute of Standards and Technology, Gaithersburg MD, 20899,
http://csrc.nist.gov/publications/nistpubs/800-131A/sp800-131A.pdf, (retrieved November 2014).
 Elaine Barker., William Barker., William Burr., William Polk., Miles Smid. Recommendation for Key Management – Part 1:
General (Revision 3), 2012, National Institute of Standards and Technology, Gaithersburg MD, 20899,
http://csrc.nist.gov/publications/nistpubs/800-57/sp800-57_part1_rev3_general.pdf, (retrieved November 2014).