#include <Keccak-fPropagation.h>

Inheritance diagram for KeccakFPropagation:

Collaboration diagram for KeccakFPropagation:

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< ListOfRowPatterns >	directRowOutputListPerInput
vector< ListOfRowPatterns >	reverseRowOutputListPerInput
vector< AffineSpaceOfRows >	affinePerInput
const KeccakFDCLC &	parent
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

enum KeccakFPropagation::DCorLC

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:

aParent	A reference to the Keccak-f instance as a KeccakFDCLC object.
aDCorLC	The 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:

suffix The 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:

prefix	The given prefix.
suffix	The 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:

slice The 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:

state	The state before χ to propagate, given as a vector of slices.
packedIfPossible	If 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:

in The input state value given as a vector of slices.

out The 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:

in The input state value given as a vector of slices.

out The 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:

in The input state value given as a vector of slices.

out The 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:

dx The x coordinate to update.

dy The 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:

point The 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:

point The 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:

in The input state value given as a vector of slices.

out The 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:

C The parity as a vector of lanes.

D The 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:

C The parity as a vector of rows.

D The resulting θ-effect.

void KeccakFPropagation::display ( ostream & out ) const

This function displays the possible patterns and their weights.

Parameters:

out	The 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:

fout	The stream to display to.
C	The 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:

fout	The stream to display to.
p	The 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:

fileNameIn	The name of the file containing the trails.
fout	The output stream to send the report to.
maxWeight	The 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:

hammingWeight The 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.

For DC:
- if (3n ≥ h): l = 2n;
- else if (5n ≤ h): refer to getLowerBoundOnReverseWeightGivenHammingWeight();
- else l = ceil((n + h)/2).
For LC:
- if (4n ≥ h): l = 2n;
- else refer to getLowerBoundOnReverseWeightGivenHammingWeight().
  Parameters:
  
  hammingWeight Lower bound on the Hamming weight.
  
  nrActiveRows Lower bound on the number of active rows.
  
  Returns:
  The computed lower bound.

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:

hammingWeight The 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:
- if (n ≥ h): l = 2n;
- else if (5n ≤ h): refer to getLowerBoundOnWeightGivenHammingWeight();
- else l = ceil((3n + h)/2).
For LC:
- if (2n ≥ h): l = 2n;
- else if (5n ≤ h): refer to getLowerBoundOnWeightGivenHammingWeight();
- else l = 2×ceil((n + h)/3).
  Parameters:
  
  hammingWeight Lower bound on the Hamming weight.
  
  nrActiveRows Lower 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:

sliceBeforeChi Slice 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:

sliceAfterChi Slice value before χ.

unsigned int KeccakFPropagation::getMinReverseWeight ( const SliceValue & slice ) const [inline]

This method returns the minimum reverse weight of a slice.

Parameters:

slice The 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:

state The 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:

state The 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:

slice The 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:

stateAfterChi	The state just after χ given as a vector of slices.
maxWeight	The 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:

slice The 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:

state The 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:

row	The 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:

t The t coordinate.

x The resulting x coordinate.

z The 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:

beforeChi	The row value at the input of χ.
afterChi	The 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:

beforeChi	The state value at the input of χ.
afterChi	The 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:

first	The first trail.
second	The 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:

in The input state value given as a vector of slices.

out The 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:

in The input state value given as a vector of slices.

out The 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:

in The input state value given as a vector of slices.

out The 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:

dx The x coordinate to update.

dy The 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:

point The 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:

point The 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:

in The input state value given as a vector of slices.

out The 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:

t The t coordinate of the point to translate.

Returns:
The t coordinate after translation.

Member Data Documentation

vector<AffineSpaceOfRows> KeccakFPropagation::affinePerInput

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

vector<ListOfRowPatterns> KeccakFPropagation::directRowOutputListPerInput

The output row patterns:

for DC, same as KeccakFDCLC::diffChi;
for LC, same as KeccakFDCLC::corrInvChi.

KeccakFDCLC::LambdaMode KeccakFPropagation::lambdaMode [protected]

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

unsigned int KeccakFPropagation::laneSize

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

const string KeccakFPropagation::name

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

const KeccakFDCLC& KeccakFPropagation::parent

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

KeccakFDCLC::LambdaMode KeccakFPropagation::reverseLambdaMode [protected]

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

vector<ListOfRowPatterns> KeccakFPropagation::reverseRowOutputListPerInput

The output row patterns in the reverse direction:

for DC, same as KeccakFDCLC::diffInvChi;
for LC, same as KeccakFDCLC::corrChi.

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

in	The input state value given as a vector of slices.
out	The output state value returned as a vector of slices.

hammingWeight	Lower bound on the Hamming weight.
nrActiveRows	Lower bound on the number of active rows.

t	The t coordinate.
x	The resulting x coordinate.
z	The resulting z coordinate.

KeccakFPropagation Class Reference

Public Types

Public Member Functions

Public Attributes

Protected Attributes

Detailed Description

Member Enumeration Documentation

Constructor & Destructor Documentation

Member Function Documentation

Member Data Documentation