KeccakTools

KeccakFPropagation Class Reference

#include <Keccak-fPropagation.h>

Inheritance diagram for KeccakFPropagation:
Collaboration diagram for KeccakFPropagation:

List of all members.

Public Types

enum  DCorLC { DC = 0, LC }

Public Member Functions

 KeccakFPropagation (const KeccakFDCLC &aParent, KeccakFPropagation::DCorLC aDCorLC)
DCorLC getPropagationType () const
void display (ostream &out) const
unsigned int getWeight (const SliceValue &slice) const
unsigned int getWeightRow (const RowValue &row) const
unsigned int getWeight (const vector< SliceValue > &state) const
unsigned int getMinReverseWeight (const SliceValue &slice) const
unsigned int getMinReverseWeightRow (const RowValue &row) const
unsigned int getMinReverseWeight (const vector< SliceValue > &state) const
unsigned int getMinReverseWeightAfterLambda (const vector< SliceValue > &state) const
void directPi (unsigned int &dx, unsigned int &dy) const
void reversePi (unsigned int &dx, unsigned int &dy) const
void directRhoPi (BitPosition &point) const
void reverseRhoPi (BitPosition &point) const
void directRhoPiAfterTheta (BitPosition &point) const
void reverseRhoPiBeforeTheta (BitPosition &point) const
unsigned int getLowerBoundOnWeightGivenHammingWeight (unsigned int hammingWeight) const
unsigned int getLowerBoundOnWeightGivenHammingWeightAndNrActiveRows (unsigned int hammingWeight, unsigned int nrOfActiveRows) const
unsigned int getLowerBoundOnReverseWeightGivenHammingWeight (unsigned int hammingWeight) const
unsigned int getLowerBoundOnReverseWeightGivenHammingWeightAndNrActiveRows (unsigned int hammingWeight, unsigned int nrActiveRows) const
SliceValue getMinimumInKernelSliceAfterChi (const SliceValue &sliceBeforeChi) const
SliceValue getMinimumInKernelSliceBeforeChi (const SliceValue &sliceAfterChi) const
AffineSpaceOfSlices buildSliceBase (SliceValue slice) const
AffineSpaceOfStates buildStateBase (const vector< SliceValue > &state, bool packedIfPossible=false) const
ReverseStateIterator getReverseStateIterator (const vector< SliceValue > &stateAfterChi, unsigned int maxWeight=0) const
bool isChiCompatible (const RowValue &beforeChi, const RowValue &afterChi) const
bool isChiCompatible (const vector< SliceValue > &beforeChi, const vector< SliceValue > &afterChi) const
bool isRoundCompatible (const Trail &first, const Trail &second) const
bool isThetaJustAfterChi () const
void directLambda (const vector< SliceValue > &in, vector< SliceValue > &out) const
void reverseLambda (const vector< SliceValue > &in, vector< SliceValue > &out) const
void directLambdaBeforeTheta (const vector< SliceValue > &in, vector< SliceValue > &out) const
void reverseLambdaBeforeTheta (const vector< SliceValue > &in, vector< SliceValue > &out) const
void directTheta (const vector< SliceValue > &in, vector< SliceValue > &out) const
void reverseTheta (const vector< SliceValue > &in, vector< SliceValue > &out) const
void directLambdaAfterTheta (const vector< SliceValue > &in, vector< SliceValue > &out) const
void reverseLambdaAfterTheta (const vector< SliceValue > &in, vector< SliceValue > &out) const
void directThetaEffectFromParities (const vector< LaneValue > &C, vector< LaneValue > &D) const
void directThetaEffectFromParities (const vector< RowValue > &C, vector< RowValue > &D) const
void getXandZfromT (unsigned int t, unsigned int &x, unsigned int &z) const
unsigned int translateAlongXinT (unsigned int t) const
UINT64 displayTrailsAndCheck (const string &fileNameIn, ostream &fout, unsigned int maxWeight=0) const
void displayParity (ostream &fout, const vector< RowValue > &C) const
void displayParity (ostream &fout, PackedParity p) const
string buildFileName (const string &suffix) const
string buildFileName (const string &prefix, const string &suffix) const

Public Attributes

vector< ListOfRowPatternsdirectRowOutputListPerInput
vector< ListOfRowPatternsreverseRowOutputListPerInput
vector< AffineSpaceOfRowsaffinePerInput
const KeccakFDCLCparent
unsigned int laneSize
const string name

Protected Attributes

KeccakFDCLC::LambdaMode lambdaMode
KeccakFDCLC::LambdaMode reverseLambdaMode

Detailed Description

This class provides the necessary tools to compute the propagation of either differences or linear patterns through the rounds of Keccak-f. To provide methods that work similarly for linear (LC) and differential cryptanalysis (DC), an instance of this class is specialized in either DC or LC. The convention of the direction of propagation is as described in the Keccak main document:

  • "direct" means in the direction that allows to describe the output patterns in an affine space (same direction as the rounds for DC, inverse rounds for LC);
  • "reverse" means the opposite of "direct" (hence same direction as the inverse rounds for DC, rounds for LC).

In this context, the words "before" and "after" refer to the "direct" direction.


Member Enumeration Documentation

This type allows one to specify the type of propagation: differential (DC) or linear (LC).

Enumerator:
DC 
LC 

Constructor & Destructor Documentation

KeccakFPropagation::KeccakFPropagation ( const KeccakFDCLC aParent,
KeccakFPropagation::DCorLC  aDCorLC 
)

This constructor initializes the different attributes as a function of the Keccak-f instance referenced by aParent and whether the instance handles DC or LC (aDCorLC).

Parameters:
aParentA reference to the Keccak-f instance as a KeccakFDCLC object.
aDCorLCThe propagation type.

Member Function Documentation

string KeccakFPropagation::buildFileName ( const string &  suffix) const

This method builds a file name by prepending "DC" or "LC" as a prefix and appending a given suffix to the name produced by KeccakFDCLC::getName().

Parameters:
suffixThe given suffix.
Returns:
The constructed file name.
string KeccakFPropagation::buildFileName ( const string &  prefix,
const string &  suffix 
) const

This method builds a file name by prepending "DC" or "LC" and a given prefix and appending a given suffix to the name produced by KeccakFDCLC::getName().

Parameters:
prefixThe given prefix.
suffixThe given suffix.
Returns:
The constructed file name.
AffineSpaceOfSlices KeccakFPropagation::buildSliceBase ( SliceValue  slice) const

This method builds an affine set of slices from a given slice pattern. The produced base defines the slices just after χ (so before λ). The parities considered are also those of the slices after χ.

Parameters:
sliceThe slice before χ to propagate.
Returns:
The affine space as a AffineSpaceOfSlices object.
AffineSpaceOfStates KeccakFPropagation::buildStateBase ( const vector< SliceValue > &  state,
bool  packedIfPossible = false 
) const

This method builds an affine set of states corresponding to the propagation of a given input state through χ and λ. The affine space produced thus covers the propagation through a whole round. The parities in the AffineSpaceOfStates object are those before θ.

Parameters:
stateThe state before χ to propagate, given as a vector of slices.
packedIfPossibleIf true, the produced object will have AffineSpaceOfStates::packed set to true, unless the parities do not fit in the PackedParity type. If false, the produced object will have AffineSpaceOfStates::packed set to false.
Returns:
The affine space as a AffineSpaceOfStates object.
void KeccakFPropagation::directLambda ( const vector< SliceValue > &  in,
vector< SliceValue > &  out 
) const

This method applies λ in the "direct" direction:

  • DC: θ then ρ then π;
  • LC: π-1 then ρ-1 then θT.
    Parameters:
    inThe input state value given as a vector of slices.
    outThe output state value returned as a vector of slices.
void KeccakFPropagation::directLambdaAfterTheta ( const vector< SliceValue > &  in,
vector< SliceValue > &  out 
) const

This method applies the part of λ after θ in the "direct" direction:

  • DC: ρ then π;
  • LC: identity.
    Parameters:
    inThe input state value given as a vector of slices.
    outThe output state value returned as a vector of slices.
void KeccakFPropagation::directLambdaBeforeTheta ( const vector< SliceValue > &  in,
vector< SliceValue > &  out 
) const

This method applies the part of λ before θ in the "direct" direction:

  • DC: identity;
  • LC: π-1 then ρ-1.
    Parameters:
    inThe input state value given as a vector of slices.
    outThe output state value returned as a vector of slices.
void KeccakFPropagation::directPi ( unsigned int &  dx,
unsigned int &  dy 
) const

This method multiplies the vector (dx, dy)T by the matrix π or π-1 to the left:

  • for DC, π is used;
  • for LC, π-1 is used.
    Parameters:
    dxThe x coordinate to update.
    dyThe y coordinate to update.
void KeccakFPropagation::directRhoPi ( BitPosition point) const

This method moves the given bit position through ρ and π in the direct direction:

  • for DC, this computes π(ρ(x, y, z));
  • for LC, this computes ρ-1-1(x, y, z)).
    Parameters:
    pointThe coordinates (x, y, z) to update.
void KeccakFPropagation::directRhoPiAfterTheta ( BitPosition point) const

This method moves the given bit position through the operations after θ in the direct direction:

  • for DC, this computes π(ρ(x, y, z));
  • for LC, this leaves the given bit position unchanged.
    Parameters:
    pointThe coordinates (x, y, z) to update.
void KeccakFPropagation::directTheta ( const vector< SliceValue > &  in,
vector< SliceValue > &  out 
) const

This method applies θ in the "direct" direction:

  • DC: θ;
  • LC: θT.
    Parameters:
    inThe input state value given as a vector of slices.
    outThe output state value returned as a vector of slices.
void KeccakFPropagation::directThetaEffectFromParities ( const vector< LaneValue > &  C,
vector< LaneValue > &  D 
) const

This function computes the θ-effect from the parity, in the "direct" direction:

  • DC: the θ-effect;
  • LC: the θT-effect.
    Parameters:
    CThe parity as a vector of lanes.
    DThe resulting θ-effect.
void KeccakFPropagation::directThetaEffectFromParities ( const vector< RowValue > &  C,
vector< RowValue > &  D 
) const

This function computes the θ-effect from the parity, in the "direct" direction:

  • DC: the θ-effect;
  • LC: the θT-effect.
    Parameters:
    CThe parity as a vector of rows.
    DThe resulting θ-effect.
void KeccakFPropagation::display ( ostream &  out) const

This function displays the possible patterns and their weights.

Parameters:
outThe stream to display to.
void KeccakFPropagation::displayParity ( ostream &  fout,
const vector< RowValue > &  C 
) const

Displays the parity pattern and its effect on an ostream.

Parameters:
foutThe stream to display to.
CThe parity as a vector of rows.
void KeccakFPropagation::displayParity ( ostream &  fout,
PackedParity  p 
) const

Displays the parity pattern and its effect on an ostream.

Parameters:
foutThe stream to display to.
pThe parity, packed.
UINT64 KeccakFPropagation::displayTrailsAndCheck ( const string &  fileNameIn,
ostream &  fout,
unsigned int  maxWeight = 0 
) const

This methods reads all the trails in a file, checks their consistency and then produces a report in the given output stream. See also Trail::produceHumanReadableFile().

Parameters:
fileNameInThe name of the file containing the trails.
foutThe output stream to send the report to.
maxWeightThe maximum weight to display trails. If 0, the maximum weight of trails to display is computed automatically so that a reasonable number of trails are displayed in the report.
Returns:
The number of trails read and checked.
unsigned int KeccakFPropagation::getLowerBoundOnReverseWeightGivenHammingWeight ( unsigned int  hammingWeight) const

This method computes a lower bound on the minimum reverse weight for any state having the given Hamming weight. The formula is given in Section 3.1 of "The Keccak reference".

Parameters:
hammingWeightThe Hamming weight.
Returns:
The computed lower bound.
unsigned int KeccakFPropagation::getLowerBoundOnReverseWeightGivenHammingWeightAndNrActiveRows ( unsigned int  hammingWeight,
unsigned int  nrActiveRows 
) const

This method computes a lower bound on the minimum reverse weight for any state with given lower bounds on its Hamming weight and number of active rows. The formulas are as follows. Let l be the resulting lower bound, n be the number of active rows and h be the Hamming weight.

unsigned int KeccakFPropagation::getLowerBoundOnWeightGivenHammingWeight ( unsigned int  hammingWeight) const

This method computes a lower bound on the propagation weight for any state having the given the Hamming weight. The formula is given in Section 3.1 of "The Keccak reference".

Parameters:
hammingWeightThe Hamming weight.
Returns:
The computed lower bound.
unsigned int KeccakFPropagation::getLowerBoundOnWeightGivenHammingWeightAndNrActiveRows ( unsigned int  hammingWeight,
unsigned int  nrOfActiveRows 
) const

This method computes a lower bound on the propagation weight for any state with given lower bounds on its Hamming weight and number of active rows. The formulas are as follows. Let l be the resulting lower bound, n be the number of active rows and h be the Hamming weight.

  • For DC:
  • For LC:
    • if (2nh): l = 2n;
    • else if (5nh): refer to getLowerBoundOnWeightGivenHammingWeight();
    • else l = 2×ceil((n + h)/3).
      Parameters:
      hammingWeightLower bound on the Hamming weight.
      nrActiveRowsLower bound on the number of active rows.
      Returns:
      The computed lower bound.
SliceValue KeccakFPropagation::getMinimumInKernelSliceAfterChi ( const SliceValue sliceBeforeChi) const

This method returns a slice value that has the bits set that are active in all slice values that satisfy the two following conditions:

  • they are compatible through χ with the slice value in parameter;
  • they are in the kernel.
    Note:
    Actually, the LC variant is not really useful here.
    Parameters:
    sliceBeforeChiSlice value before χ.
SliceValue KeccakFPropagation::getMinimumInKernelSliceBeforeChi ( const SliceValue sliceAfterChi) const

This method returns a slice value that has the bits set that are active in all slice values that satisfy the two following conditions:

  • they are compatible through χ-1 with the slice value in parameter;
  • they are in the kernel.
    Note:
    Actually, the DC variant is not really useful here.
    Parameters:
    sliceAfterChiSlice value before χ.
unsigned int KeccakFPropagation::getMinReverseWeight ( const SliceValue slice) const [inline]

This method returns the minimum reverse weight of a slice.

Parameters:
sliceThe value of a slice.
Returns:
The minimum weight of the given slice.
unsigned int KeccakFPropagation::getMinReverseWeight ( const vector< SliceValue > &  state) const

This method returns the minimum reverse weight of a state.

Parameters:
stateThe value of a state given as a vector of slices.
Returns:
The minimum reverse weight of the given state.
unsigned int KeccakFPropagation::getMinReverseWeightAfterLambda ( const vector< SliceValue > &  state) const

This method returns the minimum reverse weight of a state, to which the reverse λ is first applied. This allows to give a state value before χ (so after λ), which is then converted to a state value after the χ of the previous round (so before λ).

Parameters:
stateThe value of a state given as a vector of slices.
Returns:
The minimum reverse weight.
unsigned int KeccakFPropagation::getMinReverseWeightRow ( const RowValue row) const [inline]

This method returns the minimum reverse weight of a slice.

Parameters:
sliceThe value of a slice.
Returns:
The minimum weight of the given slice.
KeccakFPropagation::DCorLC KeccakFPropagation::getPropagationType ( ) const

This method returns the propagation type (DC or LC) handled by the instance.

Returns:
The propagation type as a DCorLC value.
ReverseStateIterator KeccakFPropagation::getReverseStateIterator ( const vector< SliceValue > &  stateAfterChi,
unsigned int  maxWeight = 0 
) const

This method builds an iterator over the possible states propagating through χ in the "reverse" direction. The iterator can be restricted to run through the states only up to a given maximum propagation weight.

Parameters:
stateAfterChiThe state just after χ given as a vector of slices.
maxWeightThe maximum propagation weight considered by the iterator. If 0, the iterator runs through all the possible states.
Returns:
The iterator as a ReverseStateIterator object.
unsigned int KeccakFPropagation::getWeight ( const SliceValue slice) const [inline]

This method returns the propagation weight of a slice.

Parameters:
sliceThe value of a slice.
Returns:
The propagation weight of the given slice.
unsigned int KeccakFPropagation::getWeight ( const vector< SliceValue > &  state) const

This method returns the propagation weight of a state.

Parameters:
stateThe value of a state given as a vector of slices.
Returns:
The propagation weight of the given state.
unsigned int KeccakFPropagation::getWeightRow ( const RowValue row) const [inline]

This method returns the propagation weight of a row.

Parameters:
rowThe value of a slice.
Returns:
The propagation weight of the given row.
void KeccakFPropagation::getXandZfromT ( unsigned int  t,
unsigned int &  x,
unsigned int &  z 
) const

This function converts the t coordinate into (x,z) coordinates.

  • DC: (x,z)=(-2t,t)
  • LC: (x,z)=(2t,-t)
    Parameters:
    tThe t coordinate.
    xThe resulting x coordinate.
    zThe resulting z coordinate.
bool KeccakFPropagation::isChiCompatible ( const RowValue beforeChi,
const RowValue afterChi 
) const [inline]

This method returns true iff the input row pattern is compatible with the output row pattern.

Parameters:
beforeChiThe row value at the input of χ.
afterChiThe row value at the output of χ.
Returns:
It returns true iff the given values are compatible through χ.
bool KeccakFPropagation::isChiCompatible ( const vector< SliceValue > &  beforeChi,
const vector< SliceValue > &  afterChi 
) const

This method returns true iff the given state before χ is compatible with the given state after χ.

Parameters:
beforeChiThe state value at the input of χ.
afterChiThe state value at the output of χ.
Returns:
It returns true iff the given values are compatible through χ.
bool KeccakFPropagation::isRoundCompatible ( const Trail first,
const Trail second 
) const

This method returns true iff two trails can be chained, i.e., if last state of the first trail is compatible through χ and λ with the first state of the second trail.

Parameters:
firstThe first trail.
secondThe second trail.
Returns:
It returns true iff the given trails can be chained.
bool KeccakFPropagation::isThetaJustAfterChi ( ) const

This method returns true iff θ (or θT) is the first step of the linear step between two χ's.

Returns:
It returns true iff θ (or θT) is the first step of the linear step between two χ's.
void KeccakFPropagation::reverseLambda ( const vector< SliceValue > &  in,
vector< SliceValue > &  out 
) const

This method applies λ in the "reverse" direction:

  • DC: π-1 then ρ-1 then θ-1;
  • LC: θ-1T then ρ then π.
    Parameters:
    inThe input state value given as a vector of slices.
    outThe output state value returned as a vector of slices.
void KeccakFPropagation::reverseLambdaAfterTheta ( const vector< SliceValue > &  in,
vector< SliceValue > &  out 
) const

This method applies the part of λ after θ in the "reverse" direction:

  • DC: π-1 then ρ-1;
  • LC: identity.
    Parameters:
    inThe input state value given as a vector of slices.
    outThe output state value returned as a vector of slices.
void KeccakFPropagation::reverseLambdaBeforeTheta ( const vector< SliceValue > &  in,
vector< SliceValue > &  out 
) const

This method applies the part of λ before θ in the "reverse" direction:

  • DC: identity;
  • LC: ρ then π.
    Parameters:
    inThe input state value given as a vector of slices.
    outThe output state value returned as a vector of slices.
void KeccakFPropagation::reversePi ( unsigned int &  dx,
unsigned int &  dy 
) const

This method multiplies the vector (dx, dy)T by the matrix π or π-1 to the left:

  • for DC, π-1 is used;
  • for LC, π is used.
    Parameters:
    dxThe x coordinate to update.
    dyThe y coordinate to update.
void KeccakFPropagation::reverseRhoPi ( BitPosition point) const

This method moves the given bit position through ρ and π in the reverse direction:

  • for DC, this computes ρ-1-1(x, y, z));
  • for LC, this computes π(ρ(x, y, z)).
    Parameters:
    pointThe coordinates (x, y, z) to update.
void KeccakFPropagation::reverseRhoPiBeforeTheta ( BitPosition point) const

This method moves the given bit position through the operations before θ in the reverse direction:

  • for DC, this leaves the given bit position unchanged;
  • for LC, this computes π(ρ(x, y, z)).
    Parameters:
    pointThe coordinates (x, y, z) to update.
void KeccakFPropagation::reverseTheta ( const vector< SliceValue > &  in,
vector< SliceValue > &  out 
) const

This method applies θ in the "reverse" direction:

  • DC: θ-1;
  • LC: θ-1T.
    Parameters:
    inThe input state value given as a vector of slices.
    outThe output state value returned as a vector of slices.
unsigned int KeccakFPropagation::translateAlongXinT ( unsigned int  t) const

This function translates a point expressed in the t coordinate along the x axis.

  • DC: x goes to x+1 (e.g., t←t+192 if lane size is 64)
  • LC: x goes to x-1 (e.g., t←t+192 if lane size is 64)
    Parameters:
    tThe t coordinate of the point to translate.
    Returns:
    The t coordinate after translation.

Member Data Documentation

This attribute contains the same as directRowOutputListPerInput but in the form of an affine space representation.

The output row patterns:

The λ mode contains the lambdaMode attribute to pass to KeccakFDCLC to compute the linear part in the "direct" direction.

This attribute contains the lane size (a copy of parent.laneSize).

This attribute contains a string to help build appropriate file names: "DC" or "LC".

This is a link to the 'parent' KeccakFDCLC class.

The λ mode contains the lambdaMode attribute to pass to KeccakFDCLC to compute the linear part in the "reverse" direction.

The output row patterns in the reverse direction:


The documentation for this class was generated from the following files: