Skip to main content

FC1 Algorithm Ushers In The Era Of Post-Alien Cryptography
draft-fabbrini-algorithm-post-alien-cryptography-00

Document Type Active Internet-Draft (individual)
Author Michele Fabbrini
Last updated 2022-05-22
Stream (None)
Intended RFC status (None)
Formats
Stream Stream state (No stream defined)
Consensus boilerplate Unknown
RFC Editor Note (None)
IESG IESG state I-D Exists
Telechat date (None)
Responsible AD (None)
Send notices to (None)
draft-fabbrini-algorithm-post-alien-cryptography-00
Independent Submission                                       M. Fabbrini
Internet-Draft                                              May 22, 2022        
Intended status: Informational                     
Expires: November 23, 2022
                             

       FC1 Algorithm Ushers In The Era Of Post-Alien Cryptography                               
                                                   
           draft-fabbrini-algorithm-post-alien-cryptography-00    
                  
Abstract

   This memo aims to introduce the concept of "post-alien cryptography",
   presenting a symmetric encryption algorithm which, in our opinion, 
   can be considered the first ever designed to face the challenges 
   posed by contact with an alien civilization. FC1 cipher 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 23, 2022.

Fabbrini                Expires November 23, 2022               [Page 1]
Internet-Draft         FC1 Post-Alien Cryptography              May 2022

Copyright Notice
   
   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.  The Need Of A Post-Alien Cryptography  . . . . . . . . . . . .  3
   3.  Specification  . . . . . . . . . . . . . . . . . . . . . . . .  5
     3.1.  Modular Multiplicative Inverse . . . . . . . . . . . . . .  5
     3.2.  Description  . . . . . . . . . . . . . . . . . . . . . . .  5
        3.2.1.  Encryption  . . . . . . . . . . . . . . . . . . . . .  5
        3.2.2.  Decryption  . . . . . . . . . . . . . . . . . . . . .  7
     3.3.  Recommended Parameters Set . . . . . . . . . . . . . . . .  7          
   4.  Implementation And Tests . . . . . . . . . . . . . . . . . . .  8    
   5.  IANA Considerations  . . . . . . . . . . . . . . . . . . . . .  8  
   6.  Security Considerations  . . . . . . . . . . . . . . . . . . .  8   
   7.  Informative References . . . . . . . . . . . . . . . . . . . .  9
   Author's Address . . . . . . . . . . . . . . . . . . . . . . . . .  9

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 

Fabbrini                Expires November 23, 2022               [Page 2]
Internet-Draft         FC1 Post-Alien Cryptography              May 2022

   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
   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. By "external" 
   scenario we refer to the possibility of an encounter with an alien 
   civilization that could render current encryption schemes 
   ineffective, thus posing serious security risks for the entire human 
   species. FC1 was designed by imagining attackers possessing a 
   computational capacity far superior to that of our present and future
   computers.
 

2.  The Need Of A Post-Alien Cryptography

   Imagine waking up tomorrow and discovering aliens exist, they're here 
   and they're not good guys. Then you decide to join others to organize 
   a resistance. The first thing you realize is that you need a secure 
   communication channel to coordinate with others. The second bad news
   of the day is to understand that the AES-xxx is unable to protect 
   your messages because the aliens use cryptanalytic techniques and 
 
Fabbrini                Expires November 23, 2022               [Page 3]
Internet-Draft         FC1 Post-Alien Cryptography              May 2022

   computing power capable of breaking any deterministic algorithm. 
   But without imagining alien invasion scenarios, let's think about 
   how much the chances of a first contact with aliens will increase 
   thanks to the synergy between the public and private sectors in 
   space trips. 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. 
   We believe that FC1 ushers in the era of "post-alien cryptography" 
   and we hope that the debate we have stimulated will lead to realize 
   we need to have a vision oriented to the design of algorithms that
   can defend human life from any possible threat.   
   
   
3.  Specification

3.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 

Fabbrini                Expires November 23, 2022               [Page 4]
Internet-Draft         FC1 Post-Alien Cryptography              May 2022

   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.

3.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.

   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.

3.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:
  
Fabbrini                Expires November 23, 2022               [Page 5]
Internet-Draft         FC1 Post-Alien Cryptography              May 2022

                              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 
   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

    
Fabbrini                Expires November 23, 2022               [Page 6]
Internet-Draft         FC1 Post-Alien Cryptography              May 2022

                         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].

3.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.

3.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.
   
Fabbrini                Expires November 23, 2022               [Page 7]
Internet-Draft         FC1 Post-Alien Cryptography              May 2022

   Secondary key - It has no upper limit and can even be 0.

4.  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].

5.  IANA Considerations

   This memo includes no request to IANA.

6.  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:

          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.

Fabbrini                Expires November 23, 2022               [Page 8]
Internet-Draft         FC1 Post-Alien Cryptography              May 2022

7.  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 November 23, 2022               [Page 9]
Internet-Draft         FC1 Post-Alien Cryptography              May 2022