PCFB-mode

1. Using PCFB-mode, all past plain text is provably secure with a security level of 2**m to all kinds of attacks, as long as the vector is unknown up to the position of the first known plain text. This is due to the fact that the m most significant bits of the vector is equal to the previos cipher text, whereas the n-m least significant bits of V are an internal state of the encryption mechanism. Suppose that the encryption algorithm E, the key k, the vector V(i), the cipher text C(i-1) and C(i) and the plain text P(i) are known. Then, for each m-bit value X, there is a n-bit value Y such that if V(i-1) = Y and P(i-1) = X, then (C(i-1),V(i-1)) would decrypt into (P(i-1),V(i)). However, we know that V(i) is a valid vector value only if the m most significant bits are equal to C(i-1). Consequently, the security level against retrospective attacks would be at least 2**m for each past plain text block retrieved.

2. Except for exceptional cases when E_k is such that PCFB mode interfers with operations in the encryption algorithm, PCFB mode is error propagating: Changing one bit of plain text changes the corresponding bit of cipher text. If one bit of cipher text is changed, then one of m most significant bits of V passed on from that stage is correspondingly changed. Assume that E_k is such that this means that all bits of E_k(V) are equally probable to change. (Since E_k might be assumed to be bijective, the value of E_k(V) will at least be different from what it would have been without the change of the text.) This means that, at the next stage, all bits of C (while encrypting) or all bits of P (while decrypting) are equally probably to change, and that all n-m bits of (T>>m) are equally probable to change (or at least be different). Hence, the bits of E_k(V) at the second next step are correspondingly probable to change, etc. The error propagation will not terminate until, at some stage, both the value of (T>>m) and the value of C will become equal to what they would have been without the initial change. This is so simply because E_k might be assumed to be one-to-one.

Note that only if E_k is such that,

(a) for any n-bit blocks P and P’, if P<>P’ and (P>>(n‑m))=(P’>>(n‑m)) then (E_k(P)>>m)<>(E_k(P’)>>m),

then the error propagation past a single error will never terminate. However, if E_k meets condition (a), then it is also true that if E_k(P)<>E_k(P’) and (E_k(P)>>m)=(E_k(P’)>>m) then (P>>(n‑m))<>(P’>>(n‑m)), and any block cipher with this property would have a major security problem.

#INDEX

Attacks:

Three kinds of attacks are of particular interest:

§1 Attacks derived from attacks on E_k in ECB mode: Will still work if they only require knowledge of m most significant bits of plain text blocks and m least significant bits of cipher text blocks. The rest of the input to and output from E_k might be assumed to be unknown to the attacker, unless he makes additional efforts. PCFB mode has an accordingly higher security level than ECB mode (cf §2).

§2 If the proportion of m and n is chosen carelessly (i.e. if m/n is too close to 1), an attack on PCFB mode might reveal more information than what was stated in §1: Assume that the attacker has access to a decryption device, makes a limited change to the cipher text, and observes at which stage the propagation terminates. The attacker would then know that the value of (T>>m) at the stage prior to the termination of the propagation had become equal to what it would have been without the initial change. If the attacker had access to a E_k ECB decryption device (D_k), he could test all 2**(n-m) possible values of (T>>m) until he found a value which fit the PCFB mode cipher text and plain text, and then roll back the PCFB sequence using D_k to find the initial value of V.

§3 Since PCFB mode is error propagating, it should be assumed that it would not recover from errors. If an error should occur, the cipher has to be reset on both sides. If the legitimate parties want to protect the integrity of transactions, executable files and such, this should not result in any additional overhead. It would however be a problem if the legitimate parties want to handle errors by ignoring then (because isolated errors only imply minor distortions in documents like pictures or sound files) or by resending the information (e.g. if it is part of a protocol command sequence). Depending on the nature of the transmission, an attacker might exploit the error propagation property just to make trouble and unnecessarily increase the workload of the legitimate parties.

#INDEX

Randomness:

If the underlying encryption algorithm E_k produces pseudo-random output, clearly so will PCFB mode: Otherwise it would either be the case that the m least significant bits of the E_k() blocks were biased, or that PCFB mode interfered with the E_k algorithm. Under the same assumption, the bit difference between actual and received plain text past a cipher text error should be correspondingly pseudo-random up to the point were the propagation terminates.

#INDEX

PERFORMANCE

The underlying cipher is invoked once for every m bits of plain text / cipher text. The sender and recipient both need to store the current value of the vector V. They might also want to store the initial value of V to enable a reset, as an alternative to including the initial value of V in the key and run a key establishment protocol at each reset. No counters are needed, but might be considered to be used as an additional parameter for vector initialization across sessions, as an alternative to key establishment protocols with a required non-repetitive seed.

PCFB mode is serialized. The m bit blocks of cipher text / plain text have to be processed in order in both encryption and decryption mode. I.e. step 3 has to return a value before step 1 might be executed at the next stage, and step 1 has to return before step 2 is executed. Steps 2 and 3 might be executed in parallel.

#INDEX

CRYPTOGRAPHIC SERVICES

If the legitimate parties decrease the entropy of the plain text in an appropriate manner, the location of the first occurrence of an error in the cipher text might be pinpointed down to an interval depending on the properties of the entropy decrement. E.g. if the sender inserts short strings of zeroes followed by an integer indicating the offset to the next string of zeroes, the error might be located to somewhere in between the last correctly received string of zeroes and the expected location of the next string of zeroes. The probability of the location of the error being correctly determined, is equal to 1-(2**(-l)), were l is the length of the strings of zeroes plus the length of the integer. If an entire message is correctly received, the legitimate parties might rule out random errors as well as forgery and other kinds of tampering with a probability corresponding to the probability of the entropy decrement occurring as a random result.

Conversely, if a message is incorrectly received, random errors cannot be distinguished from deliberate tampering, unless further additions are made to the protocol. (1) If the key establishment protocol includes a cross-session counter, a copy-and-paste operation from a previous session might be recognized as immediately resulting in garbage plain text reception (as usual, with a probability corresponding to the risk of a random error taking place immediately after the end of the key establishment). (2) If no counter is used, the message is re-sent and an error takes place at the precise same spot, then this event might be recognized as some sort of active attack. (Note that an intelligent attacker would not let himself be trapped by this method. All kinds of attempted forgery would not be detected, but practically none would be successful.) If it is assumed that the location of such errors / attacks is evenly distributed across the span of transmissions, the expected workload of the second method will be equal to sending one half message twice.

#INDEX

INTELLECTUAL PROPERTY CONSIDERATIONS

Free to use.

#INDEX

FLEXIBILITY

Any block size n of the underlying cipher is supported, but n should be sufficiently large and the quote of m/n should be sufficiently small, to take advantage of the security attributes of this mode.

The vector V should not be larger than twice the block size of the underlying cipher, or else error propagation might not start immediately past an error. If the vector V is larger than the block size of the underlying cipher, the algorithm should be modified so that the values of E_k(V[i]) are piped down within the execution of step 1, and not only by the shift right operation in step 3. Cf the Steak Cipher algorithm for an example of how this could be done.

#INDEX

ERROR PROPERTIES

PCFB mode is error propagating in both directions. The error properties are essential to PCFB mode and are described in detail above.

#INDEX

USAGE ERRORS

The initial value of the vector V should be considered as secret key data, or else the deployment of PCFB mode would loose some benefit compared to other modes. Such knowledge would however not compromise the rest of the key, assuming that E_k is secure in ECB mode. Some other errors - choosing m too large, or a size of the vector V greater than the block size of the underlying cipher - are covered above. There is also a potential risk that PCFB-m/n mode is confused with CFB-m/n mode.

#INDEX

Henrick Hellström

StreamSec HB