n170401 nfoWorks nfoNote SCE: Stream Cipher Equivocation

nfoWorks>notes> 2017>04> n170401>  0.0.5 2017-06-17 11:31 -0700

Stream Cipher Equivocation (SCE) is an investigation into cryptographic constructions for personal use that offer ideal resistance to cryptanalytic attacks by a resourceful adversary.

Purpose

Identification and characterization of general-use stream ciphers and requirements for their long-term secure protection of private data.
  

Principles

 1. The approach is limited to the collection, storage, transfer, sharing, and dissemination of sensitive but unclassified (SBU) information. 
 2. NIST Federal Information Standards and Special Publications are accepted as guidelines and limitations on scope.

 3. Characterization of relationships between key strength, cipher creation, message equivocation, and adversary difficulty are clear and understandable.
 4. The limitation of cryptographic-quality pseudo-random number generators in creation of an ideal message-privacy envelope is made clear.
 5. Reliable transmission, storage, and access to the cryptogram and reliable operation of encryption/decryption are taken as given. Assurance of message integrity and authenticity is separate although not necessarily independent.
 6. Messages and their cryptograms are of fixed (not necessarily the same) lengths.

 7. The chunking of cryptogram segments is independent of blocking for transmission and storage.
 8. The scheme does not depend on work-factor multipliers that impact recipients and yield to foreseeable advances in technology and computational resources.
 9. The scheme is applicable to long-lived data for which an adversary has indefinite time to attack the protection.
 10. The scheme will not by itself defeat targeted espionage by non-cryptographic means.
  

Priorities

 1. Basic model and its characterization.
 2. Estimation of attack complexity in terms of external knowledge of procedure and message characteristics.

 3. Demonstration of simple approaches that delimit the weakest protection.
 4. Exploration of straightforward forms of "perpetual equivocation" on the basic scheme.
 5. Assessment of further equivocation-extending measures, their costs and their complexity.
 6. Any implemented algorithms.
 7. Statistical analysis of implementations.
 8. Forensic recovery methods.
  

Plans

1. Gather foundational materials from information theory.
2. Express the fundamental stream cipher case, its parameters, and prospective vulnerabilities.
3. Connect the information-theoretic characteristics to the risk of cryptographic discovery of the message.
4. Assess methods, such as perpetual equivocation, as impediments to message discovery.
5. Progress farther based on the identified prospects.
  

People

 1. The explanations and examples are intended for study by developers and those interested in understanding stream cipher (equivocation) concepts.
 2. The findings are offered to experts for their review and skeptical assessments.
 3. The basic analysis work is a solo effort with potential review/contribution on public lists devoted to cryptography and information security.

1. Introduction

Vernam ciphers employ one-time secret keys having the same length as the form of the message being encrypted.  The cipher is sometimes referred to as a One Time Pad (OTP) [cipher] because of historical techniques for sharing the one-time secret keys^[1].  Shannon [1949] demonstrated that Vernam ciphers are perfect in a particular sense.  No other cipher can do better under the same assumptions and conditions.  There is no "more-perfect."  This does not assure that a Vernam-encrypted message cannot be cracked by a determined adversary with sufficient time and resources.  The assumptions and conditions are critical.  These are identified and reviewed for SCE.

Vernam encryption/decryption is straightforward and appealing for digital processing.  The practical limitations arise in producing, exchanging, and protecting the never-duplicated one-time keys.  It is also challenging to produce cryptographic-quality keys that approach satisfaction of Shannon's perfect-cipher conditions.

Practical stream ciphers are not perfect.  Instead, a cryptographically-derived, quasi-perfect cipher is obtained from a reasonable-length one-time secret key that is easier to share between the parties involved.  The question for the design and use of such ciphers is how they can be strong enough to defeat feasible cryptanalysis while falling short of perfection.  The goal is to have a less-than-perfect but ideal cipher that provides effective protection against a resourceful adversary.

Shannon [1948] introduces equivocation as a measure of the degree of uncertainty in discerning a message in the presence of noise.  Shannon [1948] adapts this notion for considering a stream cipher as introduction of noise that can be removed completely if the key is determined.  Equivocation is 0 when there is no uncertainty and 1 when there is complete uncertainty.  Under certain conditions, a cryptogram stream's equivocation decreases until it reaches 0 (the unicity point) given a sufficiently lengthy stream. At the unicity point, the encrypted message is theoretically completely determined.

Equivocation of a stream cipher is a non-increasing function of cryptogram stream length.  A cipher is considered ideal if it can forestall cryptograms reaching the unicity point indefinitely for any finite-length message.  A cipher is strongly ideal if the equivocation does not decrease as cryptogram streams lengthen. 

It is commonplace to express resistance to cryptanalytic attack as being of the same order as the brute-force probability  of guessing a k-bit number.  Since there are 2^k values with that many bits, the ability to guess a given one at random is 1/2^k, usually written 2^-k. 

There are many factors that lead to reduction of k in practice, and equivocation is an important one.  Some efforts to make resistance more difficult by increasing the work required do not change the order of difficulty.  Powerful resistance improvements increase k without corresponding penalty for encryption/decryption while impeding adversaries in significant ways..

 To assess stream-cipher approaches, it is valuable to estimate k as a function of underlying characteristics of the cipher, of the key source, and of the messages being encrypted.  Appraisals of SCE shall provide such accounts.

SCE investigates prospects of quasi-Vernam approaches that have an ideal cryptanalytic resistance level.  Of particular concern is identification of constraints and parameters sufficient for a  desired threshhold of resistance (k) against particular adversarial capabilities.

2. Available Materials and References

• n170401b: SCE Development [Latest]
     
• n170401c: SCE Background
• n170401a: Diary & Job Jar
• n170401-assets: Assets used/cited for SCE Development  
    
• n130101: NIST Cryptographic Resources
  Additional assets and guidance used in the characterization of SCE approaches  
• n170501: CryptoRNG: Random Number Generation
  Relevant assets and materials that bear on the requirement for cryptographic-quality random-number generation in SCE approaches.
    
• [1] Wikipedia.  One-time pad.  Article.  2017-04-07 version accessed on the Internet at <https://en.wikipedia.org/w/index.php?title=One-time_pad&oldid=774221178>.  An informal introduction to the practical situation that does not address equivocation and how perfect need not be synonymous with unbreakable.  SCE development is intended to clarify that situation and the hypothesis of  "all equally likely" plaintexts being neither a consequence nor a guarantee.
    
• [Pierce1980] Pierce, John R.  An Introduction to Information Theory: Symbols, Signals, and Noise.  Dover Publications (New York: 1980).  ISBN 0-486-24061-4 pbk.  An unabridged and revised edition of the author's 1961 popular account.  The survey of information theory keeps mathematical aspects mainly accessible. This is recommended along with [Shannon1963] for helpful background before tackling [Shannon1949].
    
• [Shannon1963] Shannon, Claude E., Weaver, Warren.  The Mathematical Theory of Communication.  University of Illinois Press (Urbana: 1963). The 1998 Illini Books Edition reissue with Foreword by Richard E. Blahut and Bruce Hajek.  ISBN 0-252-72548-4 pbk. Kindle edition available.  Includes expanded expository paper by Warren Weaver and, with minor corrections, the original [Shannon1948].
    
• [Shannon1948] Shannon, Claude E.  A Mathematical Theory of Communication.  Bell Systems Technology Journal 27, 3 (July 1948), pp. 379-423; 27, 4 (October 1948), pp. 623-666.  The foundation of Information Theory.  Included in [Shannon1963].
    
• [Shannon1949] Shannon, Claude E.  Communication Theory of Secrecy Systems.  Bell Systems Technology Journal 28, 4 (October 1949), pp. 656-715.  Building on [Shannon1948], this paper applies information theory to communication ciphers, introducing important distinctions of perfect secrecy, ideal secrecy, and practical measures.

Attribution:

Hamilton, Dennis E.

SCE: Stream Cipher Equivocation.   nfoWorks nfoNote folio n170401 0.0.6, June 17, 2017.  Accessed at <http://nfoWorks.org/notes/2017/04/n170401.htm>.

Revision History:
 

0.0.6 2017-06-17-11:23 Touch ups and word-smithing

0.0.5 2017-04-22-13:21 Tie into NIST resources.

0.0.4 2017-04-21-09:28 Touch-ups with discussion of Equivocation versus Attack Difficulty

0.0.3 2017-04-17-10:10 Add Synopsis and 5Ps

0.0.2 2017-04-15-17:02 Add Basic References

0.0.1 2017-04-14-14:33 First Draft of Overview

0.0.0 2017-04-11-10:22 Cover Page for Initial Material

Serve as placeholder.  Also start a job jar page for recording work items for building more content. 

You are navigating nfoWorks. This work is licensed under a Creative Commons Attribution 2.5 License.

created 2017-04-11-10:22 -0700 $$Author: Orcmid $ $$Date: 17-06-17 11:31 $ $$Revision: 192 $