Internet DRAFT - draft-fabbrini-fc1-a-new-symmetric-key-cipher
draft-fabbrini-fc1-a-new-symmetric-key-cipher
Independent Submission M. Fabbrini
Internet-Draft May 20, 2023
Intended status: Informational
Expires: November 16, 2023
FC1: A Non-Deterministic, Alien-Resistant,
Cipher Where The Modulo Is The Symmetric Key
draft-fabbrini-fc1-a-new-symmetric-key-cipher-02
Abstract
In this paper we describe a symmetric key algorithm that offers an
unprecedented grade of confidentiality. Based on the uniqueness of
the modular multiplicative inverse of a positive integer a modulo n
and on its computability in a polynomial time, this non-deterministic
cipher can easily and quickly handle keys of millions or billions of
bits that an attacker does not even know the length of.
The algorithm's primary key is the modulo, while the ciphertext is
given by the concatenation of the modular inverse of blocks of
plaintext whose length is randomly chosen within a predetermined
range. In addition to the full specification here defined, in a
related work we present an implementation of it in Julia Programming
Language, accompanied by real examples of encryption and decryption.
Status of This Memo
This Internet-Draft is submitted in full conformance with the
provisions of BCP 78 and BCP 79.
Internet-Drafts are working documents of the Internet Engineering
Task Force (IETF). Note that other groups may also distribute
working documents as Internet-Drafts. The list of current Internet-
Drafts is at https://datatracker.ietf.org/drafts/current/.
Internet-Drafts are draft documents valid for a maximum of six months
and may be updated, replaced, or obsoleted by other documents at any
time. It is inappropriate to use Internet-Drafts as reference
material or to cite them other than as "work in progress."
This Internet-Draft will expire on November 22, 2022.
Copyright Notice
Fabbrini Expires November 16, 2023 [Page 1]
Internet-Draft Fabbrini Cipher 1 May 2023
Copyright (c) 2022 IETF Trust and the persons identified as the
document authors. All rights reserved.
This document is subject to BCP 78 and the IETF Trust's Legal
Provisions Relating to IETF Documents
(https://trustee.ietf.org/license-info) in effect on the date of
publication of this document. Please review these documents
carefully, as they describe your rights and restrictions with respect
to this document. Code Components extracted from this document must
include Simplified BSD License text as described in Section 4.e of
the Trust Legal Provisions and are provided without warranty as
described in the Simplified BSD License.
Table of Contents
1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 2
2. Specification . . . . . . . . . . . . . . . . . . . . . . . . 4
2.1. Modular Multiplicative Inverse . . . . . . . . . . . . . . 4
2.2. Description . . . . . . . . . . . . . . . . . . . . . . . 4
2.2.1. Encryption . . . . . . . . . . . . . . . . . . . . . 5
2.2.2. Decryption . . . . . . . . . . . . . . . . . . . . . 7
2.3. Recommended Parameters Set . . . . . . . . . . . . . . . . 7
3. Implementation And Tests . . . . . . . . . . . . . . . . . . . 7
4. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 7
5. Security Considerations . . . . . . . . . . . . . . . . . . . 7
6. Informative References . . . . . . . . . . . . . . . . . . . . 8
Author's Address . . . . . . . . . . . . . . . . . . . . . . . . . 8
1. Introduction
In a symmetric key encryption scheme, a single key is used for both
encryption and decryption. An algorithm can be considered safe if the
only way to guess the key is to explore all the possibilities given
by the different combinations of zeros and ones. This is called a
"brute-force attack" and under certain circumstances it can be very
difficult, if not impossible, to implement. A 256-bit key (the length
used by the current AES encryption standard) is at present considered
"unbreakable" even by the next generation of quantum computers. So it
appears that approved standards can ensure a good level of
confidentiality for many decades to come. Neverthless, if we look at
some structural aspects of them, we can find some relevant weaknesses
that could jeopardize the security of encrypted data in light of some
new challenges that we are likely to face in a near future. But
before going into the technical details of the weaknesses, it is
useful to dwell on the implicit hypothesis that underlies the alleged
security of encryption standards. In fact, they are designed to
Fabbrini Expires November 16, 2023 [Page 2]
Internet-Draft Fabbrini Cipher 1 May 2023
instantly transfer encrypted data between two different points in
space. But if we consider sending data to a different point in time,
then the algorithms used would be perhaps inadequate to protect the
confidentiality of the original text. For example, suppose Alice
wants to transmit an AES-256 encrypted message to Bob who will use
the symmetric key to decrypt it in 50 years. How can Alice be sure
that the technological development of the coming years will not lead
to the ability of testing 2^256 different sequences of 0's and 1's
in a reasonable time, so making the key in Bob's possession useless?
Now let's see the structural aspects that may compromise the safety
of the accepted standards. Current standards have four main aspects
in common. The first two are related to the key: its length is known
and does not exceed 256 bits. The last two relate to the algorithms:
they are deterministic and convert a fixed block of plaintext into a
ciphertext block of the same length. An algorithm is deterministic if
a given plaintext always produces a given ciphertext. These four
points are generally considered irrelevant and do not raise security
concerns. In our opinion, there are however two specific scenarios
that could change the rules of the game. The first one, which we call
the "internal" scenario, relates to the prospect of an upcoming world
war, or at least of a long period of involution in the reciprocal
relations among states. A tragic war is hitting Europe. Again.
Diplomatic relations are cooling down and scientific discoveries
become military secrets. In this context of separation and conflict,
how can one be sure that a certain technological level has not
already been reached by the adversary? So, for example, how can we
be sure that no one in the world is able to test 2^256 different
possibilities in a reasonable time? But if the internal context is
worrying, perhaps the "external" one is even more so. Humanity is
about to become a multiplanetary species and soon our spaceships will
venture into deep space in search of planets to explore and on which
to perpetuate the human race. It is logical to assume that aliens are
technologically more advanced than us and have perhaps another math,
but that they are able to understand ours. It also makes sense to
assume that however advanced their computational abilities are, they
are somehow "bounded". Since a brute-force attack implies in any case
the use of computing power, it may be a good idea "to raise the bar",
thus passing from keys of 256 bits to keys of hundreds of thousands
or millions of bits. Likewise, it can be helpful not to publicly
disclose the key length. But in the face of considerable computing
power, the use of a larger key may not be sufficient. It is necessary
to break the mold and move without delay from deterministic to
non-deterministic algorithms, making the relationship between input
and output more complex and unpredictable. These are the main lines
that have guided the construction of the FC1 algorithm, the first one
we made public in a class of algorithms designed to face the exciting
challenges of our future.
Fabbrini Expires November 16, 2023 [Page 3]
Internet-Draft Fabbrini Cipher 1 May 2023
2. Specification
2.1. Modular Multiplicative Inverse
Definition - For a positive integer n, and a (an element of Z) we say
that a' is a multiplicative inverse modulo n if
a*a' is congruent to 1 mod n
It can be proven [1] that:
1. a has a multiplicative inverse modulo n if and only if a and n
are relatively prime
2. if a' exists, then it is unique
Computation - There are various methods to compute the inverse modulo
n in a polynomial time [2] [3] which, if implemented in languages
like Julia, having built-in support for Arbitrary Precision
Arithmetic, make it possible to calculate a' in a few fractions of a
second even for numbers with hundreds of thousands of digits.
A note on Julia Programming Language - With origins in the Computer
Science and Artificial Intelligence Laboratory (CSAIL) and the Dep.
of Mathematics, Julia is a programming language created in 2009 by
Jeff Bezanson, former MIT Julia Lab researchers Stefan Karpinski, and
Viral B. Shah, and professor of mathematics Alan Edelman. The Julia
programming language is a flexible dynamic language, appropriate for
scientific and numerical computing. Julia provides software support
for Arbitrary Precision Arithmetic, which can handle operations on
numeric values that cannot be represented effectively in native
hardware representations, but at the cost of relatively slower
performance. To allow computations with arbitrary-precision integers
and floating point numbers, Julia wraps the GNU Multiple Precision
Arithmetic Library (GMP) and the GNU MPFR Library, respectively.
In an APA application the size of the integer is limited only by the
available memory.
2.2. Description
Basic concept - FC1 essentially relies on the uniqueness of the
modular multiplicative inverse of a positive integer a modulo n and
on the fact that it can be calculated in a polynomial time. Here the
modulo is the main key which, due to the algorithm's design, can be
any positive integer, while the ciphertext is the modular
multiplicative inverse. The plaintext, once tagged with a hash, is
divided into blocks, the length of which is chosen by a random number
generator, converted into ciphertext and sent over an insecure
channel.
Fabbrini Expires November 16, 2023 [Page 4]
Internet-Draft Fabbrini Cipher 1 May 2023
Keys - Keys to be kept secret and transferred over a secure channel
are primary key (the modulo) and secondary key. The latter represents
the length of a random string that is placed at the beginning of the
ciphertext.
2.2.1 Encryption
Hash - The very first operation that is performed is the computation
of a hash of the plaintext using the SHA-256 function. This tag is
then appended at the end of the text. The purpose is to ensure the
integrity of the data transmitted. We denote the plaintext with the
final tag by 'tplain':
tplain = plaintext || hash
Ciphertext initialization - With the value of the secondary key, a
random string is created which we denote by 'startpad'. This is the
initial ciphertext:
c = startpad
Fencrypt - A main function named 'fencrypt' has the task of
controlling the flow, switching between different sections of the
algorithm in relation to a certain threshold value of the length of
the tagged plaintext that still remains to be encrypted. The
threshold is fixed at 1.5 times the length of the modulo.
Frand - In the first part of the algorithm fencrypt calls a random
number generator in a given range, which we denote by 'frand'. The
generated random integer represents the length of the i-block of
tagged plaintext to be encrypted. We denote by |modulo| the length of
the modulo. The frand function generates a random value between 1 and
|modulo| − 3. From the length of the modulo, 3 bits are subtracted to
define the upper limit of the random function because 2 bits space is
used to append the leading and trailing 1 (see next point 'Fintgen').
Moreover, since we want that the integer, whose modular inverse we
are going to calculate, is less than the modulo, another bit is
dropped:
1 =< frandvalue =< |modulo| - 3
Fintgen - A leading and a trailing '1' are appended at each chunk of
tagged plaintext whose length is randomly selected by frand function.
The leading 1 is meant to make sure that the input of the function
computing the modular inverse is a positive integer since the block
could start with '0'. The trailing '1' serves to prevent the
algorithm from blocking in the case of an even modulo and a tagged
plaintext to be encrypted containing a long row of 0's. We denote by
Fabbrini Expires November 16, 2023 [Page 5]
Internet-Draft Fabbrini Cipher 1 May 2023
tplain_i the i-block of tagged plaintext; then is:
input_i = 1 || tplain_i || 1
Finv - Once the input has been prepared, it is possible to attempt to
compute the modular inverse using the 'finv' function. If the input
and the modulo are not coprime, finv cannot produce a result and it
calls the main function fencrypt which calls frand again in order to
try with a different random integer. Else, if they are coprime, the
modular multiplicative inverse is computed in a polynomial time and
passed to the next step.
Fblockgen - If the modular inverse is computable, a function called
'fblockgen' comes into play comparing the modulo length with that of
the modular inverse generated by finv. If the lengths are the same,
fblockgen does not modify the string:
If |modulo| = |finvvalue|_i
output_i = finvvalue_i
Otherwise, if the modular inverse length is less than modulo length,
fblockgen adds one or more leading zeros so that the lengths match:
If |modulo| > |finvvalue|_i
output_i = 0..0 || finvvalue_i
Final step of the first part - The block created by fblockgen is
concatenated to the existing ciphertext and the main function
fencrypt is called.
Second part: ciphertext finalization - When threshold is crossed, the
finalization functions are called. They have the task of
simultaneously calculating the last and the second-last block of
ciphertext. This design solution is necessary to prevent the case the
modular inverse does not exist for the last portion of tagged
plaintext, with the consequence of blocking the whole encryption
process. The last step involves adding a random final padding whose
length must be less than modulo length. This final padding, that we
call 'endpad', is actually a third key that we can consider inferred
from the other two. It is automatically added by the encryption
algorithm. In the subsequent decryption phase, the algorithm will
recognize it as its length is less than that of the modulo and
finally it will discard it without attempting to decrypt it.
Encryption flowchart - A detailed flowchart of the encryption process
is provided in our related work [4].
Fabbrini Expires November 16, 2023 [Page 6]
Internet-Draft Fabbrini Cipher 1 May 2023
2.2.2 Decryption
We omit a complete description of the decryption algorithm since it
is trivial. Note that, once the whole tagged plaintext has been
decrypted, it is checked, through the hash function, that the final
tag is correct and that therefore the integrity of the data is not
compromised.
2.3 Recommended Parameters Set
Primary key - We recommend a minimum length of 501 bits. At the same
time, we encourage the use of 50.000-100.000 bits keys to fully
exploit the potential offered by the algorithm. To maximize the speed
we suggest the use of a modulo having as factors non-trivial prime
numbers. If, on the other hand, the aim is to create further problems
for a potential attacker, we recommend the inclusion of some trivial
factors such as 3, 5, 11 and so on. Remember that you can safely use
an even modulo without absolutely slowing down the algorithm.
Secondary key - It has no upper limit and can even be 0.
3. Implementation And Tests
We have coded the algorithm in Julia Programming Language and tested
it using keys of different length, from 10.000 bits to over
1.000.000.000 bits. Both the code and some of the tests were recently
published in a paper, available on IACR [4].
4. IANA Considerations
This memo includes no request to IANA.
5. Security Considerations
The minimum recommended primary key length we have seen is 501 bits.
The maximum length is instead not defined because it depends on the
limits of the system on which the algorithm is run. In our tests we
went as far as keys of over one Gigabit, which means a length of over
a billion of bits. Now, if by hypothesis the attacker knew the length
of the key, the startpad was zero and he could have any information
about the content of the first block of plaintext, for a brute-force
attack he would have to try about 2^1.000.000.000 different
combinations. Since the attacker does not normally know the length of
the key, assuming the startpad equals zero, the number of attempts
would be:
Fabbrini Expires November 16, 2023 [Page 7]
Internet-Draft Fabbrini Cipher 1 May 2023
SUM [2^i] from i = 501 - 1, to i = 1.000.000.000 - 1
We denote by |maxmodulo| the longest key that a system can handle in
a 'reasonably short time' and by |minmodulo| the minimum recommended
length of the primary key.
Generalizing and assuming that |tplain| > |maxmodulo| we have:
SUM [2^i] from i = |minmodulo| - 1, to i = |maxmodulo| - 1
FC1 therefore provides an incredible grade of confidentiality,
compared to the standards currently in use, which makes it suitable
for facing the difficult challenges of the next future. As far as
integrity is concerned, it is ensured by adding a tag generated by a
SHA-256 function. In a future work we will discuss in detail other
possible attacks (such as the 'replay attack') and we will show how
FC1 is immune to them.
6. Informative References
[1] Victor Shoup (2009) A Computational Introduction to Number Theory
and Algebra, Cambridge University Press; 2nd ed.
[2] Michele Bufalo, Daniele Bufalo, Giuseppe Orlando (2021) A Note on
the Computation of the Modular Inverse for Cryptography, Axioms
[3] Niels Moeller (2007) On Schoenhage's algorithm and subquadratic
integer GCD computation, MATHEMATICS OF COMPUTATION
[4] Michele Fabbrini (2022) FC1: A Powerful, Non-Deterministic,
Symmetric Key Cipher, Cryptology ePrint Archive, Report 2022/567
https://eprint.iacr.org/2022/567
Author's Address
Michele Fabbrini
Email: fc1_id@fabbrini.org
Fabbrini Expires May 20, 2023 [Page 8]
Internet-Draft Fabbrini Cipher 1 November 2022
