[Cryptography] Shortening block cipher length...

[Phillip Hallam-Baker]

Perhaps some code will make the point clearer. I haven't run this yet, but
this is the sort of thing I was looking for. I will run it later on when I
have a test wrapper round it.

The inputs and outputs are 64 bit unsigned integers. The permutation can be
any number of bits from 1 up to 64. There isn't much point in randomly
permuting very small blocks except to avoid creating a separate code path
for them.

The cipher action is coming from the combination of an integer addition, a
rotate and an XOR. These are all efficiently implemented on modern
machines.

I once managed to break the 'MD5' algorithm from Scheier's Applied Crypto
v1. Just before showing the result to Rivest whose office was 70 ft away
from mine, I looked up the RFC and found that the printer had omitted the
additive constants at the end of each round. They make all the difference
in the world.

You can think of this as an alternative to using a digest or a MAC on a 128
bit identifier to produce a pseudo-unique 256 bit identifier.

I am not particularly bothered about the speed of this because I will be
doing at least one X448 operation every time it is called.

The number of rounds is almost certainly excessive. But I don't have the
time or the specific skills to work out how to safely reduce it.


This is limited to 64 bits. To extend beyond that, I would probably keep
the cipher action focused on just one 64 bit block and expand the rotation
function to work the key across all the blocks.

(I did think about applying cipher text stealing approach but it isn't as
nice as might be expected).


    /// <summary>
    /// Short block permutation.
    /// </summary>
    public class ShortBlockPermute {
        #region // Properties
        ///<summary>The bitmask masking the lower n bits of the data
channel</summary>
        public ulong Mask;

        ///<summary>The number of bits to permute.</summary>
        public int Bits;

        ///<summary>The number of rounds to perform.</summary>
        public int Rounds;

        ///<summary>The key schedule, this is stored for reuse.</summary>
        ulong[] keySchedule;

        int[] rotateSchedule;
        #endregion

        #region // Constructors

        /// <summary>
        /// Constructor, creates a permutation function mapping an input of
        /// length <paramref name="bits"/> to an output of length <paramref
name="bits"/>
        /// according to the value of <paramref name="key"/>.
        /// <para>Once the key schedule is set up, calls to Permute will
always return
        /// a different output if the low order bits <paramref
name="bits"/> are
        /// different and the same otherwise.</para>
        /// </summary>
        /// <param name="key">The key.</param>
        /// <param name="bits">The number of bits to permute.</param>
        /// <param name="rounds">The number of permutation rounds to
perform.</param>
        public ShortBlockPermute(byte[] key, int bits, int rounds=0) {

            (bits <= 64).AssertTrue(NYI.Throw); ; // Block size is 64 bits
or less.
            Bits = bits;

            // If not specified, set the number of rounds to be the number
of bits plus 12
            // This is arbitrary at this point.
            Rounds = rounds > 0 ? rounds : Bits + 12;
            (Rounds <= 255).AssertTrue(NYI.Throw); ; // Number of rounds is
255 or less.

            // Create the bitmask
            Mask = 1;
            for (var i = 1; i < Bits; i++) {
                Mask |= Mask >> 1;
                }

            // Create the key schedule. This is almost certainly more
baroque than needed.
            keySchedule = new ulong[Rounds];
            rotateSchedule = new int[Rounds];
            var kdf = new KeyDeriveHKDF(key, "ShortBlockPermute");
            var info = new byte[1];
            for (var i = 0; i < Rounds; i++) {
                info[0] = (byte)i;
                var bytes = kdf.Derive(info, 8).BigEndianInt(8);
                keySchedule[i] = Mask & bytes ;
                rotateSchedule[i] = (int) bytes % Bits;
                }
            }
        #endregion
        #region // Private methods

        ulong Rotate(ulong input, int bits) =>
                input << bits | (input >> Bits - bits);

        #endregion
        #region // Public methods

        /// <summary>
        /// Permute the lower n bits of <paramref name="input"/> according
to the
        /// schedule established by the constructor.
        /// </summary>
        /// <param name="input"></param>
        /// <returns></returns>
        public ulong Permute(ulong input) {
            var data = input & Mask;

            unchecked {
                // If I did this right, each of the three operations is
reversible and no data is lost.
                // The operations are chosen to provide non-linearity
relative to each other while
                // working the key at each step.
                for (var i = 0; i < Rounds; i++) {
                    data ^= keySchedule[i];
                    data &= Mask;                   // for clarity, can
remove
                    data = Rotate(data, rotateSchedule[i]);
                    data &= Mask;                   // for clarity, can
remove
                    data += keySchedule[i];
                    data &= Mask;                   // This one is
essential.
                    }
                }

            return data;
            }

        /// <summary>
        /// A depermutation function could be implemented but that would
encourage people
        /// to use this for encrypting data.
        /// </summary>
        /// <param name="input">The cipertext.</param>
        /// <returns>The function always returns an exception.</returns>
        public ulong Depermute(ulong input) => throw new Exception();

        #endregion
        }
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://www.metzdowd.com/pipermail/cryptography/attachments/20210330/6b74fa20/attachment.htm>