Implementation details of the π step of the Keccak round function In the official Keccak implementation overview, there is a section discussing different ways to organise the internal Keccak-f state -- namely section 1.2, Bit and byte numbering conventions -- and at https://keccak.team/software.html, you can find a reference software implementation as well as a list of third-party ones. At least two of the third-party C implementations, however, refer to an array of 24 integer constants that are evidently used in the π step of the Keccak-f permutation, but they are not mentioned in the specification. In the keccak-tiny-unrolled.c file from David Gil's implementation, for example, the array is defined as follows:

static const uint8_t pi[24] = \
  {10,  7, 11, 17, 18, 3,
    5, 16,  8, 21, 24, 4,
   15, 23, 19, 13, 12, 2,
   20, 14, 22,  9, 6,  1};

In the π step, 24 out of all the 25 lanes comprising the internal Keccak state are moved to different positions. It's a simple 'bijective' mapping, but the order in which the lanes are processed by David Gil's program isn't obvious because the state array is flattened to one dimension and the π step is combined with the 'chronologically first' ρ mapping in which each lane is bitwise rotated by a fixed number of positions. All the rotation offsets as defined in section 1.1 are given below (note the indices):

The corresponding rho array from the above-mentioned file looks like this (zero skipped as idempotent, rho and pi arrays' sizes equal):

static const uint8_t rho[24] = \
  { 1,  3,  6, 10, 15, 21,
   28, 36, 45, 55,  2, 14,
   27, 41, 56,  8, 25, 43,
   62, 18, 39, 61, 20, 44};

I don't want to say something blatantly wrong, but now, given this array, numbering the state lanes in the row-major scheme (starting from zero) and knowing that in the actual code (see the keccakf() function) its elements are taken in the order defined in that same array, we can conclude that the first element of the pi array is just an index of the 1-dimensional state array element (a single lane) which should be replaced with the lane rotated by rho[i] positions. The order of lanes in the a array from the keccakf() function then becomes as follows (i - lane stored in a[i]):

0 - 12     7 - 9    14 -  1    21 - 18
1 - 13     8 - 5    15 - 22    22 - 19
2 - 14     9 - 6    16 - 23    23 - 15
3 - 10    10 - 2    17 - 24    24 - 16
4 - 11    11 - 3    18 - 20
5 - 7     12 - 4    19 - 21
6 - 8     13 - 0    20 - 17

For example, the 13th lane rotated by rho[0] = 1 position to the left should take the place of the second one, so a[pi[0]=10] = 2. Similarly, the second lane rotated by rho[1] = 3 positions should replace the ninth one, so a[pi[1]=7] must be the ninth lane.

I'd like to know where these constants come from and why the state is organised in such a way. I've read the linked overview briefly, but it says nothing about any explicit formula for the π constants and I haven't found anything really helpful elsewhere either. Could you please help me?

From my implementation code, the indexes for the pi array are calculated as follows:

For x = 0 To 4
    For y = 0 To 4
        State[(0 * x) + (1 * y), (2 * x) + (3 * y)] = tempState[x, y]
    Next y
Next x

From the Keccak specification:

  The mapping $π$ is a transposition of the lanes that provides dispersion aimed at long-term diffusion. Without it, Keccak-f would exhibit periodic trails of low weight... For $π$ we have chosen a matrix that defines a permutation of the axes where they are in a single cycle of length 6.

  The mapping $ρ$ consists of translations within the lanes aimed at providing inter-slice dispersion. Without it, diffusion between the slices would be very slow. It is translation-invariant in the z-direction.

For rho offset calculation:

x = 1
y = 0

For t = 0 To KECCAK_LANES - 2
    RhoOffsets[(5 * y) + x] = ((t + 1) * (t + 2) / 2) Mod KECCAK_LANELENGTH
    newX = ((0 * x) + (1 * y)) Mod 5
    newY = ((2 * x) + (3 * y)) Mod 5
    x = newX
    y = newY
Next t

You may notice that the multiplication constants for x and y are identical to pi, and the actual computed constants are a simple geometric sequence [0,1,3,6,10,15,21,...,300] modulo 64, or whatever the lane length happens to be for smaller Keccak instances.

The reason keccak-tiny seems to use a completely different order for the rho offsets is because both pi and rho are linear and can be done in reverse order as long as the order of the offsets is changed, and that is exactly what they did. Because the order of rho is basically the inverse of pi, the fact that they switched the order makes their rho offset order identical to the geometric sequence.

So how do we see the relation between the rho offset order and the pi order? Looking at the x,y table of rho values, the 0th element (0) in the 0th position (0,0), the 1st element (1) is in the 5th position (1,0), the 2nd element (3) is in the 2nd position (0,2), the 3rd element (6) is in the 11th position (2,1), and so on, with the final element (44) in the 6th position (1,1).

Following those element positions in the sequence of the pi values within the state (x+5y), the 0th pi value is 0, the 5th value is 10, the 2nd value is 7, the 11th value is 11, and so on, with the final value being 1, matching the pi sequence table. You can calculate the pi value from the x,y position of the sequential element in the rho table, $π_{x,y}$ = $5*((2x+3y) \mod 5 )+y$

Since pi mixes the entire state by repositioning lanes, and rho rotates the bits within each lane, they are combined as a single gate free operation in hardware. The final positions of lanes within the state follows pi only.


BLS hash as a group element exponent? In BLS short signatures paper, the authors describe a hash function $H\colon\ \{0, 1\}^∗ → G^∗$, where $G$ is a Gap-Diffie-Hellman group.
They present a structure where a standard hash is used on a field element, and then mapped to a subgroup of $G$, later to be used in the security proof as a random oracle.
How would the security proof change (or break) if we'll simply use an exponentiation of some generator of $G$? i.e., to have $H(m) := g^m$ for some generator $g$.

It is not a secure hash function. For example, one can easily break the
collision resistance property: let $q$ be the order of $g$, then $m$ and $m+q$ have the same hash value, $H(m+q)=g^{m+q}=g^m=H(m)$.


Encrypting and MACing different data with same key It's a well-known best practice to not use one key to both encrypt and MAC data. In my application, there are instances where I MAC a piece of data without having encrypted it first. Do I still need a different key than the one used for encryption?  Is it OK to use the same key to MAC one piece of data if I'm going to re-use that key to encrypt some other data under the same key?

It depends on how you encrypt and mac.

If you can still choose then you should use an authenticated encryption with associated data mode (AEAD) like Galois/Counter Mode. If all data you want authenticated in a message has to be transmitted in the clear then just leave the encrypted part empty. These modes have the advantage that they were designed to use just one key and have solid security proofs.

For any other combinations it depends on what algorithms and modes you use for encryption and mac. Mostly this analysis is not worth the trouble, as deriving two keys from one master key is pretty simple (HMAC(masterKey,"Key one"), and HMAC(masterKey,"Key two") for example, or AES(masterKey,0x0…01) and AES(masterKey,0x0…02)). Also any custom crypto (and using the same key twice this way is non-standard) has the disadvantage that code and security reviews get way more complicated and any error is on you.

If you use two algorithms with completely different roots (for example Sha256-HMAC and AES counter mode) you are probably on the safe side, but that is just my feeling with no rigid argumentation behind it.


RSA with $\lambda(n)$ or $\varphi(n)$ The PKCS #1 v2.0 specifications suggest using $\lambda(n) = \mathrm{lcm}(p-1,q-1)$. What is the benefit of choosing $\lambda(n)$ over $\varphi(n) = (p-1)(q-1)$ in RSA key generation?

Choosing $\lambda(n)$ rather than $\varphi(n)$ may result in a smaller private exponent.


How do I calculate a password space if the password only has eight alphabetic characters (not case sensitive) I read this wiki article and saw this formula for random password's information entropy. Also the wiki article mention that the symbol count for non case sensitive is 36. Is there a way I can calculate the password space with this information.

The choice of 8 fully random characters is exactly 3 bits as $\log_2(8) = 3$. So to calculate the strength in bits you simply multiply with the size of the password: e.g. 16 * 3 = 48 bits of strength for 16 characters.

To translate that to the password space - the number of possible passwords - you simply can perform $2^{48}$ which means that there are 281,474,976,710,656 possible passwords. A little known trick to get an idea of the number of decimal digits is to multiply by 3 and then divide by 10 and round up: so $\large\lceil\normalsize{48 * 3 \over {10}}\large\rceil\normalsize = 15$, i.e. above number contains 15 digits. A more direct method is to simply perform exponentiation with the password size: $8^{16}$ will give you the same large number. However, I use the trick above to perform such calculations without calculator.

Note that protection against brute force should require key stretching by e.g. using a password hash. For such kind of passwords additional protection (such as account locking) should be implemented. The system needs to deal with low entropy passwords.

The trick above depends on a little known constant: 3.3219280948873626. This is the result of $\ln(10)\over\ln(2)$, i.e. each decimal digit takes about 3.3219280948873626 bits to be represented. It's quite close to 3.3333 wich makes calculations rather efficient. The little difference makes it so that $2^{10} = 1024$, or just over a thousand (a kilo in ancient Greek).


How does linear vs. non-linear operations relate to cryptographic security and differential cryptanalysis? I understand what a linear operation is and what a non-linear operation is, but I would like an explanation of specifically how a non-linear operation on input data mitigates differential crytanalysis attacks. Please note that I am asking this question in the context of developing a cipher rather than simply understanding generically linear vs. differential cryptanalysis.

If you have a linear function $F$ then the output difference corresponding to
the input difference $d$ is
$$
F(x\oplus d) \oplus F(x)=F(x)\oplus F(d) \oplus F(x)=F(d),
$$
for any value  of $x,$which is a devastating differential characteristic holding with probability one.

You can take $F$ to be an sbox, or a parallel set of sboxes which make up part of a round. Iterating, you can get a differential characteristic with probability one for the whole cipher since differential characteristics are independent of key addition. This completely breaks the cipher.

Now let $n$ be the input and output bitlength of $F$ and let $F$ be a nonlinear permutation  i.e., a proper sbox. The goal is to have many different output differentials, each holding with small probability, corresponding to each input differential.

The best possible case is that each output differential which holds occurs for exactly $2$ out of $2^n$ $x$ values. Note that in binary the output differential corresponding to some $d$ and a fixed $x$ also occurs for $x'=x\oplus d,$ i.e., they come in pairs.

Such a function is called almost perfect nonlinear (APN) but exists only for $n$ odd, thus is not much used since sboxes of byte or multiple byte or nibble length are popular. AES snoxes have maximal differential characteristic probability $2^{2-n}$ instead of the optimal $2^{1-n}$ which an APN sbox would give.


EC Calculations in Java Just for the sake of learning, I'm attempting to write an ECDSA implementation in Java.

I have what I believe is a correct implementation for point addition and doubling, but I'm not sure how to implement point multiplication - Every online description I've found says to use an algorithm like this:

public static Point pointMultiply(BigInteger kin, Point a, Curve curve) {
        Point r = new Point(BigInteger.ZERO, BigInteger.ONE);

        BigInteger k = kin.mod(curve.getN());
        int length = k.bitLength();

        byte[] binarray = new byte[length];

        for(int i = 0; i < length; i++) {
            binarray[i] = k.mod(BigInteger.TWO).byteValue();
            k = k.divide(BigInteger.TWO);
        }

        for(int i = length - 1; i >= 0; i--) {
            r = pointAdd(r, r, curve);

            if(binarray[i] == 1) {
                r = pointAdd(r, a, curve);
            }
        }

        return r;
    }

Except all of those descriptions define r as the point at infinity. That's great, except my point doubling/adding code requires actual values in order to operate on the point. How do I find an actual value for that point so I can manipulate it, and if there is no defined value, how would I implement point multiplication?

Most of the descriptions of the point at infinity I've found say that it either isn't a real point and is some sort of abstract thing (in which case I don't understand how one can manipulate it) or that it has coordinates of (0,1), which does not give me a correct pubkey when I test it against BouncyCastle.

How do I find an actual value for that point so I can manipulate it

You don't, because the articles you read are right, there is no affine representation for the point at infinity. The usual approach is then to have a flag or something in your point class that indicates whether it currently holds the point at infinity and trigger special behavior on the additon and doubling routines when this flag is set.

  that it has coordinates of (0,1)

This is true for curves in so-called Edwards form with $c=1$ (which is quite usual).

  how would I implement point multiplication?

In serious implementations projective coordinates or jacobian coordinates are used for these calculations and the point at infinity does have a representation using these coordinates with which you can work more easily.


How were semagrams encrypted in the pre-digital era? Historically messages in languages that use alphabets have been encrypted manually according to some kind of algorithm (e.g. mono- and poly-alphabetic ciphers). But how wew messages encrypted in a semagram-based language like Chinese?

There was a telegraphic code that mapped the comparatively frequently used 10000 words (that's very much more than for common daily use, e.g. newspapers) of Chinese to [0,9999]. There was once also a patented mechanical device that effected a poly-alphabetical substitution of [0,9] with a set of disks containing certain scrambled alphabet of [0,9], which the user selected 4 of them (aggreed upon with the partner) to encrypt the 4 digits from the telegraphic code. Since frequency analysis of the digits barely helps, the result from that device isn't bad IMHO even today (anyway assuming one has a somewhat larger set of disks than at that time.)


Order of letters on 3-rd rotor: Enigma III In the photo you can see the three Enigma's rotors.

On the 1-st rotor (marked with number 50 on the photo) letters put on clockwise.
On the 2-nd rotor letters put on counterclockwise.

Question. What is an order rule on the 3-rd rotor?

Edit. After the Maarten Bodewes comment, I have tried
Number mod 1 and Number mod 2:

Edit2. On the second side of the 1-st rotor (marked with number 51 on the photo) letters put on clockwise.

OK, so first you need to index the alphabet. So let's say that A=0 and Z=25 - a zero based index - as we need to perform modular arithmetic.

Lets reference the letters of the first wheel with index $i_1$ and the letters of the second wheel $i_2$. Then $i_2$is simply $i_1+20 \mod 26$. Note that the second wheel moves in the other direction as the first wheel, but that the alphabet is reversed to counter clockwise.

The third wheel has a repeating pattern of three characters: "BAC EDF ...". Here the arrow is to the side. The letters are now clockwise again.

Let's simplify the third wheel so that A is converted to B, B becomes A and C stays C. So index 0 becomes 1, index 1 becomes 0 and index 2 stays 2. The offset from the start of each set of three characters can then be written as $k_3 = (-j_3 + 1) \bmod 3$ for all mappings. To calculate the offset in the simplified wheel we have to add the start of the set: $l_3 = \lfloor j_3 / 3 \rfloor \cdot 3$.

Finally, we should undo the given simplification: a quick check will find that the alphabet has shifted 16 characters.

So the answer becomes $$i_3 = k_3 + l_3 = (-j_3 + 1) \bmod 3 + \lfloor j_3 / 3 \rfloor \cdot 3 \mod 26$$ where $$j_3 = i_2 + 16 \mod 26$$

Obviously it is much easier to simply write down which character comes up at the other wheel for each character of the alphabet. Then you only need to shift up to 25 places for each setting of the wheel.

Note that it is possible to change the order of the wheels and how the wheels are positions in relation to each other. If these changes could not be made it would be easy simply to change the to right hand wheels with a single wheel (which would have the same formula as wheel 3, but with constant 10 as $20 + 16 \bmod 26 = 10$).


Estimating bits of entropy I know there are different statistical tests out there (NIST, Dieharder, etc), which all do different ways of analyzing entropy.

What I'm having a hard time finding is any particular literature which describes how to go from those tests to actual bits of entropy in the byte stream.

How do you go from p value of a byte stream (say a 100 MB long) to bits of entropy?

Updated:

As mentioned below, you can't estimate entropy of the output (not possible), but only by understanding the physics of the underlying process that generates the entropy.

Entropy is a function of the distribution. That is, the process used to generate a byte stream is what has entropy, not the byte stream itself. If I give you the bits 1011, that could have anywhere from 0 to 4 bits of entropy; you have no way of knowing that value.

Here is the definition of Shannon entropy. Let $X$ be a random variable that takes on the values $x_1,x_2,x_3,\dots,x_n$. Then the Shannon entropy is defined as

$$H(X) = -\sum_{i=1}^{n} \operatorname{Pr}[x_i] \cdot \log_2\left(\operatorname{Pr}[x_i]\right)$$

where $\operatorname{Pr}[\cdot]$ represents probability. Note that the definition is a function of a random variable (i.e., a distribution), not a particular value!

So what is the entropy in a single flip of a coin? Let $F$ be a random variable representing such. There are two events, heads and tails, each with probability $0.5$. So, the Shannon entropy of $F$ is:

$$H(F) = -(0.5\cdot\log_2 0.5 + 0.5\cdot\log_2 0.5) = -(-0.5 + -0.5) = 1.$$

Thus, $F$ has exactly one bit of entropy, what we expected.

So, to find how much entropy is present in a byte stream, you need to know how the byte stream is generated and the entropy of any inputs (in the case of PRNGs). Recall that a deterministic algorithm cannot add entropy to an input, only take it away, so the entropy of all inputs to a deterministic algorithm is the maximum entropy possible in the output.

If you're using a hardware RNG, then you need to know the probabilities associated with the data it gives you, else you cannot formally find the Shannon entropy (though you could give it a lower bound if you know the probabilities of some, but not all, events).

But note that in any case, you are dependent on the knowledge of the distribution associated with the byte stream. You can do statistical tests, like you mention, to verify that the output "looks random" (from a certain perspective). But you'll never be able to say any more than "it looks pretty uniformly distributed to me!". You'll never be able to look at a bitstream without knowing the distribution and say "there are X bits of entropy here."


Does such a cryptographic protocol exist? Persons A, B and C put x€, y€ and z€ in a pot, respectively. Suppose that anyone can make a withdrawal from the pot as long as they prove they have such a right and that the y€ that B deposited is addressed to me. Is there a way for me to prove cryptographically that I am entitled to that amount without revealing that its origin was B?

How about the following, not practical, but proof of viability with lot's of usage of Secure-Multi-Party-Computation) :

A,B,C generate using secure multi-party-computation: a joint private/public key, none of them have the private key individually only together. Also a simple symmetric key shared between them (each with one shard).

The initial balance sheet is encrypted with the shared symmetrical key.

When someone wants to give money to someone, they sign a statement saying so with their own personal private key, and then encrypt the signed transfer order with the shared public key.
When this encrypted transfer order is presented, together they may apply secure multi party computation, to verify it, verify balance, approve/reject the order and produce new encrypted balance(Possibly also provide ZKP of correctness of the process).


Asymmetric sign in public enviroment I have RTS game, where all players run game and server just relays messages. Game can generate and store text file on player pc. I want to allow some players to be moderators, so I need to sign or encrypt their ids + number representing their permissions.

Problems:

everyone knows permissions and ids of other players.
player can see code that encrypts message (so goodbye symmetric cryptography)

What I have so far:

Textbook RSA 1024 bit + bignum library
I encrypt message with my private key and store in text file on player pc
Game got my public key and can verify if decrypted number is player id + permissions + checksum
Ids are authenticated by server

I read about RSA padding and my conclusion is - if everybody know message after it is decrypted there is no point in padding (because people got multiple copies of various messages, and they know what message will be decrypted to). Am I correct?

Maybe there is other cipher that I could use (preferred solution without need for bitwise  operations).

"if everybody know message after it is decrypted there is" still a point in padding,

since it would (hopefully) stop people from learning the message before it is decrypted.

It would probably be better to

sign the message with your private key, rather than encrypt the message with your private key.

RSA needs padding for signatures too, although that padding is different from RSA encryption padding.

Also, although you can probably still get away with 1024-bit RSA since it's just

for a game, but you should make it easy for you to move to longer public keys.


About the Algebraic Normal Form (ANF) of S-Box in DES I've thought up a way to represent the transformation of S-Box in DES by ANF. Let
$x_i\;(1\le i\le 6)$ be the input of an S-Box,
$y_i\;(1\le i\le 4)$ be the output, for example, then
$$y_1= 1\oplus x_1\oplus\dots\oplus x_1x_5\oplus\dots\oplus x_3x_4x_5x_6\oplus\cdots$$
Here the "$\oplus$" is "xor" operation and the operation between two continuous inputs is "and". I've omitted many terms because it's too long.

(This paragraph is in the old version)I think this is a very basic problem so it must be researched by so many people. But I can't find related papers. Can someone explain the ANF researches on S-Box of DES or provide some resources for me? Thanks a lot.

This is an explict expression because the left side is a single output and the right side is a polynomial of inputs with degree at most 6.

In algebraic cryptanalysis, reaserchers always represent the relations between inputs and outputs in an implicit way, like
$$f(x_1,x_2,x_3,x_4,x_5,x_6,y_1,y_2,y_3,y_4)=0$$
What I want to know is that are there any advantages or applications of explicit form compared with the implict form?

Prior to answering this question, I present a preface about ways of demonstrating a "boolean function". There are two broad ways of representing namely "Boolean form" and "polynomial form".
In the boolean form representation, the boolean function is shown in one of the ways of Truth table, d.n.f, or c.n.f. On the other side, the polynomial form representation of a boolean function can be represented in the ANF (Algebraic Normal Form) or WHT(Walsh Hadamard Transformation).
For highlighting the importance of this classification, we can mention that each way exhibits and extracts unique properties of a boolean function. But why this boolean function and its properties are important? Almost all the cryptographic transformations as SBoxes, PBoxes, and even round functions are a kind of boolean functions. Moreover, the majority of cryptographic elements can be described with them, and cryptanalysis methods take advantage of the properties of these boolean functions to reveal their weaknesses, as an example, we can mention the correlation property between inputs and outputs of an SBox.
Turning to ANF, ANF  representation of a boolean function can be defined as:

This means: boolean function f consists of n variables which these variables can either 1 or 0 and the result of this function, as well, can be either 0 or 1. With respect to this definition,  a boolean function consisting of 3 variables in ANF form could be:
              f(x1,x2,x3) = x1x2 + x2x1 + x1x3

which we can easily sketch in our well-known learned schematic diagrams in high school as follows:

In this scheme, the domain consists of three different variables namely, x1, x2, and x3 which any can either 0 or 1 in the function f representation.
But how this ANF rule is defined?
As I told ANF or the other name of "positive polarity reed muller", is a way of showing a boolean function in a polynomial form with xor operator. Actually, this representation is with the presence of all linear combination of monomials. A simple way of clarifying this definition is as follows:

In this representation, each "a" variable can be either 1 or 0. For instance, the global form of a 2 variable boolean function can be defined as:

For example, we can show AND function in the ANF form as follows:

Here a0, a1 and a2 are 0 and a3 is 1.
Before we want to answer the question of why this form of representation is important, we should remark that the part in this representation form that is crucial for cryptographers are coefficients of the terms. As mentioned above example in the AND function ANF representation, the three coefficients a0, a1, and a2 are 0sand the only x1x2 term coefficient is 1.
Returning for explaining the importance of this representation, showing a boolean function with n number variables needs n different number minterms, however, in ANF form, this could be shown with fewer terms and also these few terms give a complete description of that boolean function.
The most important application of ANF form is describing SBoxes with a minimum number of logic elements. The result of this representation indicates the important SBoxes properties such as algebraic order, algebraic weight, linear and affine, completeness, and many others which are widely used in cipher designing and cryptanalysis.


Invalid curve attack: finding low order points Background
Here's a description of page 182 of "Guide to Elliptic Curve Cryptography" by Hankerson, Menezes and Vanstone. Here's a quote from that page:

The main observation in invalid-curve attacks is that the usual formulae for adding points on an elliptic curve $E$ defined over $\mathbb F_q$ do not involve the coefficient $b$ (see §3.1.2). Thus, if $E'$ is any elliptic curve defined over $\mathbb F_q$ whose reduced Weierstrass equation differs from $E$’s only in the coefficient $b$, then the addition laws for $E'$ and $E$ are the same. Such an elliptic curve $E'$ is called an invalid curve relative to $E$.
Suppose now that $A$ does not perform public key validation on points it receives in the one-pass ECDH protocol. The attacker $B$ selects an invalid curve $E'$ such that $E'(\mathbb F_q)$ contains a point $R$ of small order $l$, and sends $R$ to $A$. $A$ computes $K=dR$ and $k = KDF(R)$. As with the small subgroup attack, when $A$ sends $B$ a message $m$ and its tag $t=MAC_k(m)$, $B$ can determine $d_l = d \bmod l$. By repeating the attack with points $R$ (on perhaps different invalid curves) of relatively prime orders, $B$ can eventually recover $d$.

Question
I am having a problem understanding one aspect of invalid-curve attacks: given some curve $E$, how does one finds an invalid curve $E'$ ($E$ and $E'$ have same parameters except for coefficient $b$) and a small-order point $R$ on $E'(\mathbb F_q)$? Is there an efficient algorithm for finding curves with small order points?
I would appreciate an example showing how to find such a curve $E'$ and a point $R$ for some "popular" $E$ (e.g. one of the NIST curves).
Related questions
Why do public keys need to be validated?
Attacks on schemes based on elliptic curves when the transmitted points are not on the curve


Known Plaintext Attack against 3-round SPECK48/96 I am attempting to break 3-round SPECK48/96 using a known-plaintext attack, provided with 10 PT-CT pairs. Here is a diagram:

I have seemed to almost figure this out, but I cannot figure out how the right side affects the state of the text, due to the left rotation.
Say I am trying to attack the first set of 8 bits on the left side (24...31). That means I will perform the rotr 8 and addition, then make my $sk_0$ guess on the 16...23 bits. I then XOR with the right side.

$sk_1$ will then be guessing bits 8...15 as those are the bits that were affect by $sk_0$ (due to rotr 8). However, this rotl 3 will cause the bits that were affected by the subkey to move in the other direction, so now each round's subkey guess will be affecting different parts of the plaintext (as opposed to on the left side, where I can trace the movement of these bits).

I may have not been clear but I was trying to explain my thought process...I just cannot seem to figure out how to approach this.

Here is how I would approach this:

First off, strip off the unkeyed parts of the cipher at the beginning and the end.  That is, process the plaintexts with the 'rotr 8/add/rotl 3' at the beginning, and process the ciphertexts with the 'xor/rotr 3' at the end (rotr because we're working the inverse direction).
Next, we focus in on only the right side ciphertext output; this allows us to skip the entire third round (!)

With these two simplifications, the remaining cipher has only one nonlinear step (the addition in round 2).  We proceed to attack that.

The obvious way to start is looking at bit 0 of the addition (we start at the lsbit because there's no carry from unknown bits; if we were doing a differential attack, we'd start at the msbit, as a differential in the msbit propagates with probability 1); the addend on the vertical path is the xor of 1 known bit and 1 key bit; the addend from the right side is the xor of 2 known bits and 1 key bit; we can deduce the lsbit of the sum from xor of 2 known plaintext bits, 1 known ciphertext bit, and 2 key bits (one from subkey 1, the other from subkey 2).  We know that the two addends are consistent with the sum, so we go through all 5 possibilities of the key bits, and see which settings are consistent with all known plaintext/ciphertext pairs.

Now, it turns out that addition in the lsbit is actually linear, and so there will be 16 possible settings for the key bits that'll be consistent, but that's OK.

Now, we extend the attack to bits 0 and 1 of the addition; the addends and the sum are also functions of a known plaintext/ciphertext bits, and a handful of key bits, and so we go through those possibilities, and eliminate those which aren't consistent with the known plaintext/ciphertext pairs (and now that there's real nonlinearity, they'll be some considerable pruning).

I could go on, but it should be fairly obvious where to go from here...


Are mouse movement coordinates useful as a seed for a RNG? Is it good to use a mouse movement as a 64-bit random seed for a Pseudorandom Generator like AES in Counter Mode?

Should I only need to get the X and Y coordinates of the mouse movement?

I suppose as far as entropy sources go, you could have chosen much, much worse. In fact a user properly moving his mouse while you collect a bunch of samples and hash them all together to obtain a seed is a pretty good random bit generator. Be conservative in your entropy estimates, for instance I would estimate no more than two bits of entropy per sample if you collect them intelligently (e.g. avoid continuous duplicates and keep a reasonably large sampling rate).

However obviously, a single mouse position is a terrible seed to use, since it doesn't even cover the whole 64-bit space. Your monitor is probably at best 1920x1080, which corresponds to about 2 million possible positions. WEAK.

But while this may be useful to keep in mind, it's probably best if you use an existing CSPRNG for your randomness needs, that way you don't bother the user, and you delegate security to someone else (which may be a good or a bad thing). You should always use the CSPRNG provided by your operating system as it is best placed to collect entropy, whether you like it or not. Under Windows, you can use CryptGenRandom() to access it.

It might seem counterproductive to use another RNG to seed your own, but entropy collection isn't exactly a trivial little thing that you just plug into a program. It has to be carefully and constantly monitored and tracked to keep a good estimate of the available entropy and ensure you don't lose any of it. Sure, making your own ultrafast PRNG using AES in counter mode for your specific needs might be worth it, but you need to consider the limits of your own random generator.


Containers for secret key What 'container' is used normally to store/transport secret keys (for symmetric algorithms)?

I have come across PKCS12 format where a public key certificate as well as a private key can be bundled together and stored in an archived file format.

Similarly how can an array of random bytes that can be used as a secret key be bundled/packed?

well it probably varies on how you want to access the key, one of the most extreme version could be an HSM which should keep it really safe but is also rather expensive.

another way would be encrypting it with a key that just you know  with plain AES and storing the base64 somewhere for example, that's what I do for some of them if you want to require entering a password you use use a key derivation function to create the key, but then you must make sure that you either use no salt or always the same.

when you want to do it for automatic access (like for needing the keys on a webserver) then you can either store the key somewhere in plaintext or you encrypt the key and save the encryption key somewhere ELSE, for example if your secret key is in a MySQL database, then store the encryption key somewhere deep in your Harddrive, even better if used with very strong permission management in there.

if you want automatic access you have to have direct access to the key which complicates it a lot.

by the way depending on how you set your HSM, you can use the key in an automated fashion, but not access the key itself.

essentially this means that you don't do the en/decryptions youself in your script/program/whatever but you send whatever needs to be crypted to the HSM which just does it for you (which also makes sure that you dont accidentially do bad things, which weaken the security drastically, because it can make it easier to use the crypto in the first place, because you just have your black box where you throw in your input and get the result).

of course it would still be annoying if someone broke in and got the ability to use your key as long as they are in, but as with HSMs you can usually not export the key at all, and even if you can, it's usually only if you supply extra permission credentials to do that. this means while the attacker can do a lot of stuff, as soon as he's removed from the machine, he cannot do crypto anymore because he didnt get the key.


How to get the order of a group generator in DH? For a DH parameter prime, if the generator $g$ is 2, how do I get the order $q$?

To extend kelalaka's answer, if $p$ is a safe prime (that is, if $p = 2q+1$ with $q$ prime), then:

If $p \equiv 7 \pmod 8$, then the order of $g=2$ will be $q$

If $p \equiv 3 \pmod 8$, then the order of $g=2$ will be $2q$

If $p = 5$ (the only other possibility), then the order of $g=2$ is 4 (that is, $2q$)


How do I generate a session key using the Diffie Hellman algorithm? How to generate a session key between two nodes in two different subnets when the nodes don't know each other directly, using diffie hellman algorithm?

If the nodes can send messages to each other ( via any number of hops/ intermediate nodes) then you can do straight standard diffie-hellmen even if they don't have a prior relationship. Indeed, thats the point of diffie-hellmen.

However, any one of the intermediate nodes could launch a man in the middle attack and could then impersonate either node to the other. There is no way to stop this if the nodes actually don't know anything about eachother. If they do know each other, you can used authenticated diffie-helmen key exchange or a public key crypto system. Agian, these only work if the nodes know each other's public key before hand.


Cryptography Headers in Cryptographic Libraries I have a question regarding the headings in cryptography. In python, in the pycryptodome module, I am doing symmetric encryption, which asks for a header that goes as follows:

Cipher = Crypto.Chiper.AES.new(key)
Cipher.update(HEADER)

My question is, how do I configure the header correctly? I've seen examples of just putting a str, like , and never explaining beyond what they are for, because I should use them, how I should use them, etc. If I need to know how to use them correctly, because I should use them, I understand that they are associated data that are linked or related to the content to be encrypted.

What associated data (or encrypted header in the plaintext message) to use is dependent on the protocol, not on the cryptographic algorithm.

Generally, for messages in a transport protocol, you'd use the to avoid replay attacks.

The header data may also contain other meta-data that you want to authenticate for the message.

Beyond that, there is nothing to tell you, because you've only listed a (partial) algorithm, and not the protocol.


Is there an algorithm that allows verification that 2 encrypted or hashed bits of data are the same, given that I may only know half of the key/ salt? We have an interesting problem.

Currently, we store a salted hash of some secret key known only to the clients of our clients to allow us (and our clients) to find other records that were generated by the client's clients, without either us or our clients being able to identify the client's client or know their secret key. We know the salt.

We now have a requirement to change the salt every 12 months, but we still need to be able to match the last year's records.

The only way I can see to do this is by keeping the current salt and the previous salt, and storing every record with both hashes, then when we want to find other records, look for either of the two stored hashes in either of the two stored hashes on the other records, which is double the  computation on storage, double the storage and up to 4 times the search time.

I think we need something like a 2-part key, so every 6 months we can generate a new half-key, and delete the oldest half key, so if the key is $k_1k_2$, in 6 months I can throw away $k_1$ and generate $k_3$, so the new full key is $k_2k_3$.

So what I'm looking for is a function where the client's client passes in their key, $s$, and we pass in a 2 part key, $k_n$ and $k_{n+1}$, and receive a digest, such that there is another function where we can pass in two digests and the current $k_nk_{n+1}$ and get true if the two digests were generated with the same $s$ and share at least one of $k_n$ and $k_{n+1}$, without us ever being able to tell what $s$ is.

If it's not possible, then we will have to go with the double hash storage, but what I'm describing sounds like something that is possible with commutative operations...

I ran into a situation with a similar requirement, and here's the idea I came up with:

We don't use a conventional 'salted hash', instead to encode a user's password, we first hash it (optionally with the user's id, but without a salt) to form a value $h$, and then you select a random Elliptic Curve point $X$, you compute the point $Y = hX$ (where $hX$ is point multiplication), and then you encode store it as the pair of points $(X, Y)$.  To validate the password that the user enters, you again hash the password the user gave you, and then check if $hX \overset{?}= Y$; if it is, you accept the password.

This encoding is effectively one-way, given $(X, Y)$, it's infeasible to recover the password hash $h$ that would match it (assuming that we use a strong curve); this is the ECDLP problem.

$X$ effectively acts as salt; given a pair of encoded passwords $(X, Y)$ and $(Z, W)$, it is infeasible to determine whether they encode the same password; this is the dECDH problem.

And, finally (here's why it is of interest to you), it's updatable; at any time (be it once a year, or more often if we choose), we can select a random integer $r$, and replace $(X, Y)$ with $(rX, rY)$; effectively changing the salt we use without changing the password it matches.

Depending on your actual requirements, something like this might be adaptable to your situation.


Efficient pen-and-paper calculation of the Galois Field multiplication? I have been reading on multiplication over GF for the Inverse Matrix Step in AES, and I feel like converting the hex numbers to binary, multiplying them and then doing the modifications required for GF arithmetic is too time-consuming when done by hand.

It would be very helpful if someone could help me with a faster way to do it.


Metrics for Measuring the Distance of Two Numbers in Cryptography Hamming Distance (HD) has been used to measure the distance of two numbers when they are converted into binary representations. e.g., $Ham(1, 2)=2$ as 0001'XOR'0010'='0011' while $Ham(128, 1)$ equals $2$ as well. Here we see HD does not work well as it falsely indicates that the distance between $1$ and $2$ is equal to the distance between $1$ and $128$.
So my question is if there are any other distance measurement methods (or encoding methods) that can deal with this issue?

Nothing is falsely indicated there!
The Hamming distance is between strings (vectors) of the same length in the space $\{0,1\}^n. $ However the integer representation of such vectors is in a different space and the distance there is different.
Besides integer distance $|x-y|$ between two integers you can have minimal cyclic distance $$\min \{|x-y|,|n-x+y|\}$$
for two elements modulo $n.$
Note Some such distances won't be a metric. The  triangle equality or symmetry may be violated.
More generally since polynomials are also widely used in Crypto, you could have metrics depending on the Hamming distance of their truth tables, or value tables if non-binary.
Or the minimal degree of two polynomials minus the number of common roots they have.
Edit: Or edit distance (levenshtein distance) which is usually defined as the minimal number of $$(insertions+ deletions+substitutions)$$ required to map a string of length $m$ to a string of length $n$ where $n=m$ is not needed. Sometimes, a weight is put on the different operations and weighted cost is minimized.


cryptographic accumulators: accumulator size vs. max. number of set members? Here's a basic question about cryptographic accumulators, or at least ones based on fixed-size accumulator values (such as RSA ones based on modulo arithmetic), that is strangely not even mentioned in most of the key historical papers or Wikipedia.

Cryptographic accumulators are being touted as a magical solution for the application of distributed certification/licensing by government/corporate authorities.  For example, I have heard claimed that the DMV (Department of Motor Vehicles) could publish a hash function and an accumulator, both of which were of constant size---or at least a size that does not grow linearly with the number of licensed drivers---and that would allow me (a driver) to present a proof to you (a car rental company) that I am licensed.  The car rental company could then check that proof without learning the driver license number of any other licensed driver.  All the crypto papers focus on the last property (privacy).  For the purposes of this SE question, I will take that as granted.

I have a much more simple question:

This immediately strikes me as impossible.  How can a constant-size accumulator contain set membership information for a variable number of members?  That seems to violate basic information theory.  How can, say, 512 bits of accumulator contain information for millions of "bits" of information (if we assume that somehow each licensed driver was only 1 bit of information)?  I could then use an accumulator to compress anything to 512 bits :)

Clearly, I am missing something very fundamental about how this whole thing works, including that the claim itself may be wrong or my understanding of its application is wrong:

does a, say, 512 or 2048 bit accumulator allow one to track only a limited amount of set members, but that number is much more than 512 or 2048?  If so, how many, and how can this possibly work?  Why does it not violate information theory?
is the set membership test that is done by a cryptographic accumulator probabilistic and/or does it suffer false positives or negatives (e.g. like a Bloom filter), and does that explain why it seems information theory is being violated?
does the DMV example I cited above require more than just a basic (fixed-size, e.g. RSA) cryptographic accumulator to work?  Does it require an accumulator whose size is linear in the maximum number of set members?
does the DMV example I cited above require other storage that I didn't mention above (for example, does each license holder have to store a constant amount of data that none of the other parties could generate even if everyone revealed their secrets to everyone else) and therefore the storage required across the system is, in fact, linear in the number of license holders?
more generally, what is the relationship between the accumulator size in bits and the maximum number of members that can be tracked, and are there other tradeoffs (e.g. probability of getting the correct answer) that can also be tweaked in designing the hash function?

Another way to think about it: some folks like to introduce cryptographic accumulators using the (non-secure, non-private) example of assigning each member its own prime number and the published accumulator simply being the product of all the primes of the members in the set.  Then my "proof" consists of handing you the product of all the primes in the set except my prime, and you can multiply them together to see they make the published product.  Well, in this simplified case, clearly the accumulator is going to get bigger as there are more primes that may be factors inside it.  But the other cryptographic accumulator algorithms (e.g. RSA) use modulo arithmetic and other methods that constrain the accumulator size...so how many members can be tracked given a particular limitation?

Thanks.

NOTE: Chat about this topic going on here: https://chat.stackexchange.com/rooms/88146/cryptographic-accumulators-accumulator-size-vs-max-number-of-set-members

Disclaimer: I am not a hard-core cryptographer, and I am only familiar with a subset of the various accumulator implementations. So this is a layman's answer.

Accumulators are not attempting to set a bit for every member of the set. The reason they can violate the intuition that they must have at least 1 bit for every potential set member is because they are lossy. Unlike a bit set, accumulators do not provide a 2-way lookup. You can put stuff in, but you can't get stuff out. Specifically, you can't start from the accumulator value and enumerate all members of the set; there is an infinite number of values "in" any given accumulator.

You can think of an accumulator like the hands of a clock. Perhaps the hands say 3:15. If I say to you, "3994 seconds have elapsed" as you look at the clock, your natural response would be, "Since when?" Without a reference start time and knowledge about how many times the hands of the clock have "wrapped", there could be an infinite number of valid assertions about elapsed time. (Accumulators depend on arithmetic in a modular field, which has this same wrapping property. 5 * 7 mod 4 = 35 mod 4 = 3. But I can give you lots of other factors that multiply together to yield 3 in a mod 4 field.)

You might be tempted to say, "Well, if a given accumulator value is compatible with an infinite number of set members, how can it "store" anything?"

To understand the answer, let me alter the clock situation a bit. You are standing in front of a clock that says 3:15 when Alice says, "4 billion 200 million 93 thousand 74 seconds have elapsed" Now you say to Alice, "Since when?" and Alice says, "Since the clock said midnight."

Even though there is an infinite number of explanations for the clock saying 3:15, Alice's assertion is testable. You can do the math that divides clock hand revolutions into the given number of seconds, and see if it's really the case that the clock said midnight at the interval that Alice claims.

Now, you can think of an accumulator as being the product of many numbers multiplied together in a wrapping, modular field. When you test set membership with the accumulator, you can't just assert "X is in the accumulator", any more than you can say "how much time has elapsed?" without a frame of reference. Instead, you have to make a claim that X is "in" the accumulator because X times Y produces that accumulator value in its modular field. That is easy to test. The Y in this example is like picking some other arbitrary reference point in a clock discussion to answer the question, "Since when?"

Notice that for X to be useful, Y must also be given. In information theory, the amount of information that must be known grows with each new set member--but the knowing is distributed to all the owners of the set members; it does not need to be held centrally. The value in the accumulator is the reference against which each set member's claims can be tested by them presenting both X and Y.

It turns out that it is computationally "hard" (meaning there is no practical way to brute-force a correct answer) to explain an accumulator as the product of X and Y, in large modular fields, unless you have been given X and Y. This is due to the irreversibility of modular math (you can't divide, any more than you can look at clock hands and know how many times they've gone around when they say 3:15). Thus, if you "own" a value that is a member of a set represented by an accumulator, and you have been told what the product of all the other set members are, you can show that your value is "in" the accumulator with some very simple math. But if you pick an arbitrary number and want to prove it is in the accumulator, you could compute till the end of the universe, and never find a solution.

It might sound like I'm claiming that accumulators can "hold" an infinite number of values. I believe that's not the case; there's a relationship between accumulator bit size and the number of possible factors (set members) and computational hardness. A mathematician could state it precisely, but I believe a simple summary is, "you can put as many set members into an accumulator as you like, but at some point, you begin to degrade computational hardness." And I think that the point where computational hardness degrades, for the 256-bit accumulators I'm used to, is very, very, very large. Certainly more than billions or trillions (which is a tiny fraction of a 256-bit number).

Cryptographers and mathematicians, is this answer accurate to one or two decimal places? :-)


What are some hashes that do not exhibit the avalanche effect? I do not know much about cryptography. But, I'm in a situation where I need a hashing method that does not exhibit the avalanche effect. I tried Googling but couldn't find anything.

In general, most hashing methods do not exhibit the avalanche effect:

most hash functions -- unless they were specifically designed to be cryptographically secure -- accidentally fail the avalanche test -- all cyclic redundancy checks (CRCs), all error correcting codes, nearly all checksums,  etc.
A few hash functions -- such as Locality-sensitive hashing and the way feature hashing summarizes a document as a short vector of integers -- deliberately fail the avalanche test, because they are designed to have certain features that are incompatible with the avalanche effect.

In cryptography, my understanding is that failing the avalanche test makes a hash function vulnerable to many attacks that every cryptographic hash function is specifically designed to prevent. So every cryptographic hash function either exhibits the avalanche effect or is considered broken.

Are you looking for an example of a broken hash function to show students why this is such a bad thing? Or (what I would find more interesting) are you designing a system where this property would be useful in some way?
I'd like to learn more about what you are trying to do.


How to derive a symmetric key from ECDH shared secret? I am trying to implement the internal primitives of ECDH. Currently I'm able to multiply the receiver's public EC point with the sender's private key to arrive at the shared EC point. Next step is to input the x-coordinate of the shared point which is a bignum to a hashing function. The curve is secp521r1 so the shared x-coordinate is of size 66 bytes.

Question 1

What format must the x-coordinate bignum be converted to before hashing it? The other party is openssl.

Is something like below sufficient...

...
print_hex(hash_input_buffer, shared_x_coordinate_bignum_bytes, 66);
...

void print_hex(unsigned char* to, unsigned char* from, int len)
{
    for (int i = 0; i < len; ++i)
    {
        sprintf((char*)to + (i * 2), "%02x", from[i]);
    }
}

OR

sprintf(hash_input_buffer, "%64x", shared_x_coordinate_bignum_bytes);

Question 2

If the hashing function is SHA-512 and I want to derive an AES-256 key from it, should I just take the first 32 bytes of the 64 byte hash output?

The general idea to derive keys from (ephemeral) Diffie-Hellman key agreement is to use a KBKDF - a key based key derivation function. KBKDFs are mostly ill defined with regards to what security requirements they adhere to. Fortunately creating a KBKDF isn't thought to be too hard. Using a cryptographically secure hash generally gets you a long way. You should however note that in that case the hash should not be vulnerable to timing- and other side channel attacks.
The input of a KBKDF or a hash is bits. Generally though only bytes are used as input. So you should be using the 66 bytes of the shared secret directly. Your conversion to hexadecimals likely already leaks side channel (timing) information. So the answer to the first question is: don't convert the x-coordinate at all.
You can indeed take any part of the SHA-512 hash as key. It is however more standard within the cryptographic community to take the first - leftmost - bytes of the resulting hash value. So that should answer question 2: just use the leftmost bytes as you're already doing.
If you want to be standards compliant and use a KBKDF then please take a look at HKDF.


What is the algorithm used to encrypt Linux passwords? I noticed during an assignment that, if I create an user with a password (azerty for exemple), and then call the command to change the password but give him exactly the same password:

passwd user
>> azerty

the encrypted string stored in ./etc/shadow changes (despite the password not changing).

What algorithm is used here?

It's not encryption, it's a one-way hash.

There are a handful of different password hashes usually used for Linux system users' passwords, they're listed in the man page for crypt(3)

The first is the original crypt algorithm, that only supported 8 character passwords (among other flaws), and which you'll hopefully never see again.

The second is the MD5-based md5crypt ([a], [b]), marked with $1$. It's considered dated mostly because it doesn't support changing the amount of iterations, i.e. the cost of the computation.

Currently more used are the SHA-256 and SHA-512 based hashes, sha256crypt and sha512crypt, which are similar in structure to md5crypt but support variable amounts of iteration. They're marked with $5$ and $6$ respectively. As @SEJPM quickly enough commented, sha512crypt ($6$) is what at least Ubuntu and Debian currently use by default.

For $1$, $5$, and $6$, the characters after the identifier up to the next $ are the salt, which is generated randomly when the password is changed.

The remaining option, not in mainline glibc is the Blowfish-based bcrypt, marked with $2a$ (or another letter). Bcrypt also uses a salt.

For more information on password hashing, and as to why use salts and why slower is better, see
"How to securely hash passwords?" on security.SE.


Help with RSA-2048 crypto ransom virus The RSA-2048 Crypto Ransom Virus has devastated me, I tried the backup method, the previous version, the Shadow Explorer, it deleted all my restore points, Its took out 5 HDs and my USB pen that happened to be plugged in, everything is encrypted, all my kids pictures and videos, spreadsheets, PDF's, Music and more. I need to know if I should pay these bastards? or is it possible to decrypt? I have attached a picture of the DECRYPT_INSTRUCTION.HTML. I also tried TeslaDecoder with no luck. Can someone please help? I also can send you one of my encrypted files.

First off, I am sorry to hear about your circumstances. Unfortunately, the virus that you caught seems to be CryptoWall 3.0 or at least a variation of it. Therefore I am bringing bad news. As stated here it is not possible to decrypt or recover the files without paying these [insert swearword].

This is mainly through the nature of the encryption algorithm used, as the key used to decrypt your files is only known to the creators/distributors of the virus.

For the future, make sure to have backups of all your data on a drive that is not connected to your computer and most importantly NEVER click on links or open attachments from E-Mails when you can't 100% verify the senders integrity.


PKCS#7 CMS - Message digest calculation process i'm studying RFC 5652 in order to know exactly how to encode/decode PKCS#7 ASN.1 data.
I don't understand how one can create a signature when the field "signedAttrs" is present:

The result of the message digest calculation process depends on
whether the signedAttrs field is present.  When the field is absent,
the result is just the message digest of the content as described
above.  When the field is present, however, the result is the message
digest of the complete DER encoding of the SignedAttrs value
contained in the signedAttrs field.  Since the SignedAttrs value,
when present, must contain the content-type and the message-digest
attributes, those values are indirectly included in the result.

By reading the above text I get confused: SignedAttrs field contains message-digest and content-type values but message-digest can be present once calculated and the digest has to be calculated on:
eContent OCTET STRING + full DER encoding of SignedAttrs field (Containing message-digest field).
In the example below there is a PKCS#7 Signed data structure where the envelopedData content field value is being signed + the signed attributes. Where
does exactly the messageDigest value come from?

Closely related: What does CMS standard mean by "initial input to the message digest"
The signature schemes envisioned by PKCS7/CMS use two stages, where the data to be signed is first hashed and that hash is used in signature generation and verification (RSA, EG, DSA, and ECDSA). For your example -- RSASSA-PKCS1-v1_5 with SHA1 -- some data is hashed with SHA1, and that hash is encoded, padded and modexp'ed, which was described in older versions of PKCS1, and PKCS7, as 'encrypting with the private key', although that description was found to be harmful and is no longer used. (See my https://security.stackexchange.com/questions/159282/#159289 for some of the Qs/As here and on security.SX on this topic, and there are more you can find by searching.)
PKCS7 originally simply applied this process to the data (what is now eContent). It and its successor CMS were enhanced to allow either that basic process or a two-stage process:

the hash of (the value of) eContent (your first red bracket) is computed, and that value is placed in the messageDigest attribute in signedAttrs. In addition eContentType is copied to the contentType attribute in signedAttrs. Other attributes may be added, and some standards that build on CMS define additional requirements on the attributes in signedAttrs.

(an encoding of) the signedAttrs structure is signed. This is almost your second red bracket, except with the tag modified as described below.

The specification for these two options is intermixed in the document. First note that the previous section (5.3) defines signedAttrs:
      signedAttrs is a collection of attributes that are signed.  The
      field is optional, but it MUST be present if the content type of
      the EncapsulatedContentInfo value being signed is not id-data.
      SignedAttributes MUST be DER encoded, even if the rest of the
      structure is BER encoded.  Useful attribute types, such as signing
      time, are defined in Section 11.  If the field is present, it MUST
      contain, at a minimum, the following two attributes:

         A content-type attribute having as its value the content type
         of the EncapsulatedContentInfo value being signed.  Section
         11.1 defines the content-type attribute.  However, the
         content-type attribute MUST NOT be used as part of a
         countersignature unsigned attribute as defined in Section 11.4.

         A message-digest attribute, having as its value the message
         digest of the content.  Section 11.2 defines the message-digest
         attribute.

The part you quote (5.4) then says, more fully:
   [With or without signedAttrs] the initial input to the message
   digest calculation process is the "value" of the encapsulated content
   being signed.  Specifically, the initial input is the
   encapContentInfo eContent OCTET STRING to which the signing process
   is applied.  Only the octets comprising the value of the eContent
   OCTET STRING are input to the message digest algorithm, not the tag
   or the length octets.

   The result of the message digest calculation process depends on
   whether the signedAttrs field is present.  When the field is absent,
   the result is just the message digest of the content as described
   above.  When the field is present, however, the result is the message
   digest of the complete DER encoding of the SignedAttrs value
   contained in the signedAttrs field.  Since the SignedAttrs value,
   when present, must contain the content-type and the message-digest
   attributes, those values are indirectly included in the result.  The
   content-type attribute MUST NOT be included in a countersignature
   unsigned attribute as defined in Section 11.4.  A separate encoding
   of the signedAttrs field is performed for message digest calculation.
   The IMPLICIT [0] tag in the signedAttrs is not used for the DER
   encoding, rather an EXPLICIT SET OF tag is used.  That is, the DER
   encoding of the EXPLICIT SET OF tag, rather than of the IMPLICIT [0]
   tag, MUST be included in the message digest calculation along with
   the length and content octets of the SignedAttributes value.

Breaking that down: without signedAttrs the hash of eContent is used for the signature in section 5.5. With signedAttrs, the hash of signedAttrs -- only signedAttrs, with the tag of the encoding modified as described -- is used for the signature in 5.5. But since the content of signedAttrs includes the hash of eContent, and the value of eContentType, the signature effectively protects those as well: if you change eContent without changing signedAttrs then the verifier will detect that hash(eContent) doesn't match signedAttrs.messageDigest, and if you change eContent and signedAttrs.messageDigest then the verifier will detect that the signature isn't valid for the modified signedAttrs.
   When the signedAttrs field is absent, only the octets comprising the
   value of the SignedData encapContentInfo eContent OCTET STRING (e.g.,
   the contents of a file) are input to the message digest calculation.
   This has the advantage that the length of the content being signed
   need not be known in advance of the signature generation process.

   Although the encapContentInfo eContent OCTET STRING tag and length
   octets are not included in the message digest calculation, they are
   protected by other means.  The length octets are protected by the
   nature of the message digest algorithm since it is computationally
   infeasible to find any two distinct message contents of any length
   that have the same message digest.

This repeats, more verbosely, that without signedAttrs the hash of eContent is used for the signature in 5.5.
5.5 then completes the sequence:
   The input to the signature generation process includes the result of
   the message digest calculation process and the signer's private key.
   The details of the signature generation depend on the signature
   algorithm employed. [...]

"The result of the message digest calculation process" used for signature generation (and verification) -- as defined in 5.4 -- is EITHER: (without signedAttrs) the hash of the value of eContent OR: (with signedAttrs) the hash of the encoding of signedAttrs.


Attribute Authentication in Attribute Based Encryption (ABE) When a data user requires access it asks the key issuer to generate a key for it using the specified attributes.

How does the key issuer authenticate that the data user actually acquires the attributes it claims to possess?

If you take a look at the KP-ABE paper or the first paper proposing the idea of ABE you can see that the set of attributes one claims to have is not authenticated.

In fact there is a setup phase during which one will take the attributes one wants to publicly disclose, and will generate a discrete logarithm public key, so to say, for each of those attributes and a key generation phase during which the same "authority" will generate private keys for each of those attributes.
One can then publish the set of attributes, the "set of attributes' public keys", as well as a randomly chosen integer $y$. And those publicly disclosed keys can then be used to encrypt data for a subset of those attributes, by whoever wishes to do so.

Now, the magic of ABE is that when you decide to encrypt for a given subset of attributes, only the persons owning all of the corresponding attributes' private keys (generated at the key generation phase by the "authority") can then combine this subset of keys in order to decrypt that ciphertext.
The persons who do possess all of these attributes' private keys can then perform the so called decryption phase, which will the bilinear map $e$ used to "stitch together" the plaintext only if the ciphertexts was addressed to the given subset of attributes out of all the attributes' keys one may possess.

However the way one distributes the attributes and their corresponding private keys created during "setup" to individuals for them to perform "key generation", is not taken into account by the scheme itself and should obviously be done in a secure, authenticated way which deals appropriate attributes to each individuals.

So, the "authority" generating the public keys and the private keys must effectively assign the attributes' private keys to the people who "own" those attributes, but the ABE schemes themselves do not take care of this practical aspect of the problem.


Why do some people believe that humans are "bad at" generating random numbers/characters like this? I'm not even sure if they are serious, but I've heard many times that some people refuse to not only trust their computer to generate a random string (which is understandable) but also don't trust themselves to do it. So, instead of simply typing/writing down:
fcC540dfdK45xslLDdfd7dDL92

And then randomly changing a few of those to other ones a few seconds later, such as one in the beginning, one in the middle and one in the end, they use dice which they roll again and again to generate random numbers, which are then treated as "truly random" and thus "truly secure".
Why would a dice roll be "more random" than simply coming up with a sequence in your head, and then changing some of them?
I simply don't believe that this could possibly be "not secure". Why the need to do the very tedious dice rolling? It feels like a ritual that they go through, based not on logic and reason, but on some sort of delusion that their brain is going to generate the same sequence as others who guess it, or a computer, even though they also change some of them after the phrase is "done".
I don't understand this. Is there anything that speaks for this practice as being "more random"/"more secure"?

In short, it is more than a belief: there is strong evidence that humans are not good entropy sources. There is a test for this

Man vs. Machine. Or, why Man is not a Particularly Good Source of Entropy.

Try to win!
So we don't rely on whether generating a random number from the mind or random keyboard typings and mouse movements that seem like a monkey playing on the computer from outsiders. We rely on good entropy sources like the /dev/urandom. That kind of sources comes from good research.
Some researches on supporting this;

1972, W. A. Wagenaar, Generation of random sequences by human subjects: a critical survey of the literature

1997, Brugger, P., Variables that influence the generation of random sequences: An update. Perceptual and Motor Skills

2005, Persaud, N, Humans can consciously generate random number sequences: A possible test for artificial intelligence. Medical hypotheses, 65(2), 211-21

2012, Schulz et. al, Analysing Humanly Generated Random Number Sequences: A Pattern-Based Approach

2012, Williams and  Griffiths Why Are People Bad at Detecting Randomness? A Statistical Argument

2014, Towse et. al, Not all numbers are equal: preferences and biases among children and adults when generating random sequences

Other online tests;

not so random with the collected results.


How to determine the shift key to decrypt a ciphertext which was encrypted using Caesar cipher? So I found this question in a model paper,

  Break ciphertext ”BJJY GPXF DI TJPM ZSYH” which is encrypted by a
  Caesar Cipher.

This gives a meaningful plaintext if we use 21 as the shift key. So the answer is

  "GOOD LUCK IN YOUR EXAM"

Do we have to find the shift key by guessing all the possible keys until we find the correct one, or is there any other way to find it?

There are only 26 possible shifts with the Caesar cipher, so you can check them all pretty quickly with a computer, or by hand for fun.

You could also get one step more sophisticated and do a frequency analysis: make histograms of ciphertext letters and compare those to the frequencies of English (e is the most common single letter; followed by t, a...just remember Etaoin Shrdlu and you'll be fine). Then you can do a $\chi$-squared test to compare your ciphertext frequencies to the expected ones from English.

Usual warning: because of how easy this is to break, make sure you only use it for fun: it offers no real security. Here's a longer discussion about cracking ciphers by hand.


Is it safe to use file's hash as IV? I'm encrypting some files using AES in CBC mode.

I'm also using file's digest (SHA-1) to check that data is decrypted correctly (so I need to store it with file).

Is it safe to use this digest as AES's IV and store it in the header of file? Or it has security issue?

By using the file's hash as IV, you also divulge the file's hash. This allows an attacker to make an exhaustive search on the file contents. It is not difficult to imagine situations where there are only a few millions or billions of possible file contents (e.g. the file contents are an encrypted SAN or password), in which case showing the data hash is an intolerable leak.

What you could use as IV is the result of HMAC over the file, using as key the same key than for encryption (or, preferably, derive both the HMAC key and the encryption key with a suitable PRF). The result would probably be quite hard to prove secure in any way, so don't do it for production; but it seems like a promising way to achieve context-free deterministic encryption.

"Context-free" means "without any memory". Some encryption modes require a random, unpredictable IV, while others just need nonces (e.g. a counter); you can obtain the former from the latter by encrypting the nonces with a block cipher, using a specific secret key for that. A counter still requires a bit of memory, which, depending on the situation, may or may not be easy to obtain. Some embedded systems would have difficulty updating a stored counter (permanent storage update draws a bit of current, a scarce resource on passive RFID systems). Since embedded systems rarely own a reliable source of randomness, they need deterministic encryption. Context-free deterministic encryption is thus an important niche functionality. Using HMAC to compute the IV for encryption may be a way to achieve that (with the important drawback of requiring a first pass on the whole file, before obtaining the IV which is need to begin encrypting it).


Finding an x such that xP = (11,44) on an elliptic curve Given the elliptic curve

$$E:y^2 = x^3+17x+5 \mod 59$$

with point $P = (4,14)$, how do I find $x$ such that compute $x\cdot P = (11,44)$

Is there a mathematical method to compute $x$, or do I simply compute a lot  of $x$'s and hope for the best?

If it helps, I know $8P = (16,40)$

As mentioned by Thekwasti, what you want here is compute a discrete logarithm, but while it is true that in general computing discrete logarithms is "hard" (which is why they are used in cryptography), in your case the group is small enough to make even a brute force search completely feasible. So the goal of the exercise is probably to make you implement at least one of the following algorithms:

Brute force search
Shanks's "baby step, giant step"
Pollard's rho

You will normally find that they are in increasing order of efficiency (although here the group is so small that the difference might not be noticeable).


Understanding certificates for public keys with subkey I have a openpgp key with 3 subkeys:

> gpg --list-keys
<keyring-location>
-------------------------------
pub   rsa4096 2017-05-19 [SC] [expires: 2019-05-19]
      <key-id>
uid           [ultimate] <my-name> <my-email>
sub   rsa4096 2017-05-19 [E] [expires: 2019-05-19]
sub   rsa4096 2017-05-19 [S] [expires: 2019-05-19]
sub   rsa4096 2017-05-19 [A] [expires: 2019-05-19]

My goal: I want to create a certificate for my pulic key for authentication with strongswan.

Now when I export the key, I get:

> gpg  --armor --export <key-id>
-----BEGIN PGP PUBLIC KEY BLOCK-----
...
-----END PGP PUBLIC KEY BLOCK-----

My questions:

What is a public key block? Does it contain all my public keys?
How can I extract the public key of my authentication key so that I can create a certificate for it?
If I have a certificate, how can I check if it is for the authentication key?

The public key block is a structure that contains one public pgp key. However the structure does not only contain the public key, but more information such as public key algorithm, key expiration time and so on. Depending on what "key-id" you used with your export command, the public key block will contain the public key correponding to that "key-id".
It might be useful to see what information your pgp key contains so that you can extract your public key from it. You could use a site such as https://cirw.in/gpg-decoder/ to check all information contained inside your public gpg key block.
You could use your private key corresponding to your public key for which you created a certificate to sign a message (e.g. with OpenSSL). Then you could use the certificate, more specifically the public key inside that certificate, to check if the signature you created can be successfully verified. If so, you can be sure that the certificate matches your private gpg key.


MAC providing sender authentication (follow up question) I was looking at the responses posted on the following question: How is digital signature different from a message authentication code (MAC)?

I read the following comment to the first answer:

  So simply speaking, MAC cannot be used to verify sender authentication because it only protects the message integrity. Alright, thank you so much

This triggered a question, what if the key used for the MAC came from an authenticated key agreement?

Both parties would have been able to verify the public keys of each other during the key exchange. So this means that all derived keys from that key agreement are implicitly also authenticated. Meaning that the calculated MAC tags using that key provide message authentication and also provide sender authenticity. And can't seem to find something wrong with this logic.

A second question, is there a security reason why then not
to use the public and private key pair to calculate digital signatures on the messages? Instead of using the MAC?

The statement you copied from the other question is incorrect. A MAC does authenticate a message (would be a rather stupid name, otherwise). If you have verified a MAC, you can be sure that the message was sent by anyone knowing the secret key. This is slightly weaker than the authentication done by a digital signature, because there are usually more parties in possession of the key.

  This triggered a question, what if the key used for the MAC came from
  an authenticated key agreement?
  [...]

Your logic is correct. That is exactly what most secure network protocols (like TLS or SSH) do.

  A second question, is there a security reason why then not to use the
  public and private key pair to calculate digital signatures on the
  messages? Instead of using the MAC?

That has performance reasons. Public Key operations are slower, need more memory and the output size is larger, compared to their symmetric counterparts.


Voting system validation I'm developing an application to run elections. A voting system. I would like to give the ability to the voters to check later if their vote were correct computed/casted.

assumptions:

each user has its own and unique voter id (64 bytes id)
we have the birthyear of an user (i.e 1977, 1982, etc)
the user must vote in N candidates (each candidate is represented by a number. candidate_1, candidate_2, candidate_N stands for numbers like 10,33,N)
in an election you must vote in N candidates, where N is >= 2.
votes are inserted in random order (they are not sequential)

As soon as the user has voted in his N candidates, it will be stored in a DB in the following format:

sha256(sha256(voter_id | birthyear) | candidate_1 | candidate_2 | candidate_n)
the chosen candidates (a list of candidate_1, candidate_2, candidate_N)

for example

the user 12345678, borned in 1980, in a 3 candidates election voted in the candidates 10,11,33.

we would compute his signature hash as:

Digest::SHA256.hexdigest(Digest::SHA256.hexdigest("12345678|1980")+"10|11|33")

in the db it would looks like:

64d2dc73485ca4d26b6dfcd517849e9654c6b8f2b7ef386dc2055fcbec2f034b,"10|11|33"

The hash signature would be printed after his votes were casted. So he could then:

a) compute it locally and see if its matches

b) via an user gui, entering his voter_id, birthyear, candidate_1, candidate_2, candidate_n, calculate his hash and look up the DB and see if his votes were rightly computed.

Important: its not the same as Approach towards anonymous e-voting. I'm not trying to provide anonymity, but a way to the user validate if his votes were casted right.

the questions are:

a) Is that a good approach to garantee the integrity of the casted votes? is that enough?

b) why wouldnt it be enough to garantee anonymity? please assume that the votes are shuffled and inserted in random order.

c) is the birthyear an strong enough salt oder would be better the whole birthday dd-mm-yyyyy to increase the numbers of possibilites? I cannot let it up to the user decide, otherwise it would introduce a complexity/time in the human interaction with the system (think about which string, ask for help and etc).

It can guarantee the integrity, because you can not fake another voting with the same hash.
However, this only shows the ballot is casted correctly, but does not prove the ballot is correctly counted. And as you said, it can not provide anonymity, such as buying vote and coercion.


Can I switch out a private RSA Key, so that when decrypting a message, it is decrypted to a different message? Here's a task I've been struggling with:
Say I have an encrypted message $c$, and a desired plaintext $m$. How can I define a valid private RSA Key $(d,N)$, so that $c^d \bmod N = m$

Note that the key needs to be valid!
My approach was to write the modulo equation as
$y \times N + m = x \times N + c^d$ so I get $c^d-m'=(y-x) \times N$. So I can simply set some value for $d$ and try to factorize the result to get $N$, but this factorization can be extremely hard because numbers are huge. Is there a better way to approach this?

Update: This other answer (temporarily hidden on request of the organizer of a CTF) details a different approach to the problem, working for all values of $m$ and $c$, yielding valid keys, that even are plausible except for a larger-than-customary $e$. These private keys will work nicely for those RSA implementations (including OpenSSL, pycrypto, and many others) accepting values of $e$ up to about $N/2$ (which is well within PKCS#1 limits). That's what the OP was asking for, rather than the following exploration.

In both crypto Catch-The-Flags and actual security attacks, it is important to determine what makes values accepted or not. Here two things matter most:

Will something check that $c<N$ (which is often a requirement in actual uses of RSA). A comment by the OP suggests there's no such check.
What makes a private key unacceptable. Practice varies widely from most¹ to less stringent.

It happens that pycrypto (last indicated as applicable in a comment by the OP) is lenient on imported RSA keys, at least when using it's reference _slowcrypto.py code. See _importKeyDER and rsa_construct: as long as $N$, $e$, $d$, $p$ and $q$ are given, they are accepted as is. $d_p$, $d_q$, $q_\text{inv}$ are recomputed if imported from a key file or missing.

With such freedom, and $c^d\bmod N=m$ the only constraint involving $c$, if in the givens $m<c$ (which I'll assume) then we can choose $N=c-m$ and $d=1$ (with other key parameters 42). The condition $c^d\bmod N=m$ gets met, success!

However, that can fail if the RSA private key is used in CRT form (using $p$, $q$, $d_p$, $d_q$, $q_\text{inv}$), which is common². We may be able to improve on this by searching a small $k\in[1,c/m)$ dividing $c−m$ and making $N=(c−m)/k$ odd and composite (if these are requirements). For $p$ and $q$, any decomposition as $N=p\,q$ with $p>1$, $q>1$, and $\gcd(p,q)=1$ should do. We'd set $e=d=1$, passing a test $e\,d\equiv1$ for any modulus. The key import will recompute $d_p=d_q=1$ and $q_\text{inv}=q^{-1}\bmod p$ as needed. The key should now work with or without using the CRT. I do not rule out that we could get away with $p=1$ or $q=1$ (with the other equal to $N$); or that, if we got blocked by a test that $e\ge3$, it could be circumvented with $e=p\,q-p-q+2$ or $e=\lambda(N)+1$.

¹ Testing that the key was generated per FIPS 186-4 would include verifying that $N$ has exactly 1024, 2048 or 3072 bits, $N=p\,q$ with $p$ and $q$ primes each in interval $\left(2^{\left(\left\lceil\log_2(N)\right\rceil-1\right)/2},2^{\left\lceil\log_2(N)\right\rceil/2}\right)$, $e$ is odd and in $\left(2^{16},2^{256}\right)$, $d=e^{-1}\bmod\operatorname{lcm}(p-1,q-1)$, $d_p=e^{-1}\bmod(p-1)$, $d_q=e^{-1}\bmod(q-1)$, $q_\text{inv}=q^{-1}\bmod p$. For 1024-bit $N$ the standard sets some extra requirement about $p\pm1$ and $q\pm1$, but these are never tested when accepting a key (contrary to the previous ones), because that would be very compute-intensive.

² We must however suppose that the advisable and common check that no fault crept in the computation of $m$ is skipped. That's performed by verifying $c=m^e\bmod N$, and that would fail even if we set an appropriate $e$ like $e=1$ or $e=\lambda(N)+1$. That would insure $c\equiv m^e\pmod N$, but not $c=m^e\bmod N$, since $c\ge N$ with our choice of $N$.


Public key encryption and message integrity Let's say I want to send an encrypted email thus I encrypt it with the receiver's public key, so that the receiver uses its private key to decrypt it.

If someone tampers with the message in between then

what kind of tampering can be performed?
wouldn't the decryption process fail since the message ought to be malformed due to the tampering?

Does asymmetric encryption like RSA ensure message integrity without hashing the message with an HMAC? Or is hashing necessary only when utilizing symmetric encryption?

For example at initiation time of the TLS handshake when the client encrypts with the server's public key the symmetric key that's going to be used for the rest of the transaction, does it also uses hashing?

If someone tampers with the message in between a. what kind of tampering can be performed and b. wouldn't the decryption process fail since the message ought to be malformed due to the tampering?

That depends on the format. In general, yes, tampering is detected. That may even be the reason that the protocol is insecure, as it could lead to padding oracle attacks.

Note that an attacker can also simply encrypt a different message as encryption doesn't add integrity or authenticity, and the public key is commonly considered, well, public.

  c. Does asymmetric encryption like RSA ensure message integrity without hashing the message with an HMAC? or is hashing necessary only when utilizing symmetric encryption?

No. Generally the message is first signed and then encrypted. If a symmetric key is already shared the parties might as well encrypt with it - or with a key derived from it.

If a symmetric key is wrapped (encrypted) and sent, you need to verify that the secret key has been agreed upon successfully - as explained in the next section.

  For example at initiation time of the TLS handshake when the client encrypts with the server's public key the symmetric key that's going to be used for the rest of the transaction, does it also uses hashing?

No, but as the symmetric key is later used for a HMAC over the previously communicated messages, it doesn't matter if the symmetric key was changed. If it was, the authentication tag calculated using HMAC value will be incorrect and the handshake will fail.


What is a pseudo-collision attack? In the context of cryptographic hash function collisions, what exactly is a pseudo-collision attack?

E.g., pseudo-collisions are discussed here:

Preimage and Pseudo-Collision Attacks on Step-Reduced SM3 Hash Function
Converting Meet-in-the-Middle Preimage
Attack into Pseudo Collision Attack:
Application to SHA-2

Also, is that term actually well-established and used consistently?

To understand what a pseudo-collision attack is, we first need to understand how a hash function internally works:

Most hash functions are basically composed out of four functions:

An initialization function that just sets a bunch of start values for the state: $I:\emptyset\rightarrow \{0,1\}^k$
An input pre-processing function that computes some values based on the message and possibly hidden context: $P:\{0,1\}^l\rightarrow \{0,1\}^q$
A state-update function, sometimes also called "compression function" that takes the current message block, the associated pre-processing and the current state and outputs a new state: $U:\{0,1\}^l\times\{0,1\}^q\times \{0,1\}^k\rightarrow \{0,1\}^k$
An output function that takes the state and outputs the hash digest: $O:\{0,1\}^k\rightarrow \{0,1\}^o$

Now a normal collision attack takes the standard composition of these functions and tries to find a collision.
A pseudo-collision attack on the other hand just tries to find a collision on the state-update function. So an attacker is interested in finding two triples $x=(m,p,h),x'=(m',p',h')$ such that $U(x)=U(x')$ with $x\neq x'$.

The application of this is more or less clear: To show weaknesses in the core update function and give insights into possible paths to full collision attacks.
For additional discussion also see these slides (PDF).

When I originally wrote this answer I screwed the concepts up, so here you have the definition and use of a "near-collision-attack" as well as a bonus:
The term "near-collision-attack" and the associated term "near-collision" aren't as "strictly" defined as "collision-attack" and "collision" however I'd define a nearcollision-attack as follows:

  Given a hash function $H:\{0,1\}^*\rightarrow \{0,1\}^n$ find $x_1,x_2$ with $x_1\neq x_2$ such that $\Delta(H(x_1),H(x_2))$ is low but not zero. Here $\Delta(x,y)$ denotes the Hamming distance between the two input strings, i.e. the number of set bits of $x\oplus y$.

The application of these attacks is clear: Suppose you authenticate files by providing a hash for human verification over a secure channel. As humans are lazy they probably won't spot the difference (if it is small as it is here) between the computed hash and the transmitted hash in case of a pseudo-collision.
As a real-life example ask yourself: When you verify an MD5 / SHA1 hash of a file, do you actually look at all the hex digits or only at the first few and the last few?


Which block cipher mode(s) is most appropriate in these applications? I have a few questions I'm stuck on for a cryptography course I'm doing, any help would be much appreciated.

The first application is for decryption on a multicore processor. I assume any of ECB, CBC, CFB or CTR would be suitable since decryption would be faster when performed in parallel, but are any of them significantly more suitable than the others and how?

The second is where it is preferred/desired to use a processor's idle time for precomputing encryption or decryption tasks before the plaintext or ciphertext is available. Not really sure how to tackle this one.

The first application is for decryption on a multicore processor. I assume any of ECB, CBC, CFB or CTR would be suitable since decryption would be faster when performed in parallel, but are any of them significantly more suitable than the others and how?

CTR, CBC and CFB all allow parallel decryption. CTR allows you to decrypt any ciphertext block independently, while the other two allow you to decrypt a block if you know the ciphertext of both it and the previous one.

However, of those only CTR also allows parallel encryption.
ECB is insecure in most cases, so it shouldn't be used, but also supports both.

  The second is where it is preferred/desired to use a processor's idle time for precomputing encryption or decryption tasks before the plaintext or ciphertext is available. Not really sure how to tackle this one.

Like ECB, both CBC and CFB require knowing the plaintext to compute any block encryptions (beyond the first block, in the case of CFB). CTR allows you to compute the entire keystream in advance.

However, in the real world you would most likely want to use authenticated encryption. Meaning you'd want to consider authenticated cipher modes as well. Many of them use CTR internally for the encryption part, fulfilling both of the above. GCM is the most common, and also allows the authentication part to be calculated in parallel.


is the perfect secrecy of one time pad dependent on the xor randomness preserving property? Is the perfect secrecy of the one time pad dependent upon the xor "randomness preserving" property (xoring a uniformly random string with any string yields a uniformly random string)? I have seen different arguments in different sources.

For example, in this discussion, the first answer derives perfect secrecy without referring to the randomness preserving issue. The derivation starts with

$$Pr[C=c]=\sum{Pr[C=c|M=m']\cdot Pr[M=m']}
=\sum{Pr[K=m'\oplus c]}\cdot Pr[M=m']
=\sum{2^{-n}}\cdot Pr[M=m']
=2^{-n}$$

where the second equation, which seems to be the core of the proof, is based on the fact there's a unique $K$ such that $K=m' \oplus c$. Ostensibly this would work for any other logical operator that has an inverse, not necessarily xor.

On the other hand, the other answer to that question states "The main point in any security proof for the one-time pad is that xoring a plaintext with a (uniformly) random bit string yields a (uniformly) random bit string no matter what the plaintext was.". If this is indeed the main point in the proof, then this proof would not work for other operators that have an inverse but don't preserve randomness.

Who is right?

Thanks!

(Answering my own question).

One time pad retains perfect secrecy using any operator $\Delta$ showing the following property: for a plaintext $M$ and a key $K$, the cyphetexts $C =  M \Delta K$ is such that there is a the same constant number of $K$s that encrypt $M$ to $C$, for any tuple ($M$, $C$). Specifically, if the length of the key equals to the length of the plaintext, then for each pair ($M$, $C$) there is a single, unique key that encrypts $M$ to $C$.

Therefore, not only xor but also other operators, such as applying Vigenère cipher with a uniformly generated key whose length equals to the message length, are suitable for one time pad.

the "random preserving" property, i.e. the uniform distribution of $C$ given a uniform distribution of $K$ and regardless of the distribution of $M$, is indeed equivalent to the above definition: if $\Delta$ preserves randomness there is necessarily the same number of $K$s for any pair ($M$, $C$) - otherwise, the distribution of $C$ wouldn't have been uniform; and if there is a constant number of keys for any pair then necessarily all cyphetexts are generated with an equal probability.


What is the value of Q such that Q|P-1 where P is a prime number? For my crypto assignment, I'm asked to enter a prime P and generate Q such that Q|P-1

Can anyone guide me what is Q|P-1?

It means $Q$ divides $P-1$. In other words, $P-1$ is a multiple of $Q$.