Decrypting ciphertext that is missing a block In the AES encryption, suppose that the key is known. The ciphertext is also known except for a block of the same size as the key. For example, the adversary knows $k, c_0, c_1, \dots, c_{n - 1}$; They do not know the final ciphertext $c_n$.

In the worst case scenario for the attacker, how hard is it for them to successfully decrypt the ciphertext, compared with the case when the key is unknown and the ciphertext is fully known?

The details depend on the mode of operation, but for all the commonly used modes, most of the message will still be fully decryptable without any guesswork even if one block of ciphertext is missing.

For the (insecure!) ECB mode, and for the OFB and CTR modes, all you will lose is the plaintext for the missing block.  Everything else can still be decrypted in the normal manner.  This is because, in these modes, each block of ciphertext only affects the corresponding block of plaintext.  (Indeed, for the OFB and CTR modes, each bit of ciphertext only affects the corresponding bit of plaintext.)

For CBC and CFB modes, you will lose the missing block and the next one.  On the flip side, if you can guess the plaintext for either of these missing blocks, you can use that to reconstruct the other one.  If your guess is wrong, the reconstruction will be essentially random gibberish.  If the plaintext doesn't normally look completely random, that can provide a useful way to verify your guess.

(At least, this is true for CBC mode and for CFB with full-block feedback.  For the rarely used CFB-8 and CFB-1 modes, you should still be able to easily reconstruct the next block if you can guess the plaintext for the missing one, but going the other way is slightly trickier.  I believe it should be doable with a backtracking search, but it'll be a bit more complex than just the single XOR and AES decrypt operation needed for normal full-block CFB and CBC.)

The also rarely used PCBC ("propagating CBC") mode is the one notable exception here, since it was designed so that decrypting a block of ciphertext should require knowing the previous block of plaintext.  Thus, with that mode, you will only be able to directly decrypt the message up to the last block before the missing one.

However, if you can guess the plaintext for any of the later blocks, then you can still decrypt the entire message, since you can in fact run the PCBC decryption process both forwards and backwards from the guessed block.  In fact, even if you can't directly guess any of the later plaintext blocks, you can still obtain the bitwise XOR of every pair of plaintext blocks after the break in the ciphertext, which effectively reduces the PCBC mode encryption to something equivalent to a repeating key XOR cipher and allows you to apply all the well known techniques for breaking a many-time pad.

As for more modern authenticated encryption modes, those generally don't fare any better in this scenario.  Indeed, most of them are built by combining one of the classical modes (usually CTR) with a message authentication code, and thus are just as easy to decrypt in this case as CTR mode itself.  The authentication layer can even give the attacker a reliable way to verify their guess about the possible content of the missing block.

In any case, just like with the similar recent question about decrypting without the IV, the moral of the story is that modern encryption systems are designed with the assumption that the key is secret and everything else is public.  If you break that assumption by making the key available to the attacker, then the system will probably not be secure any more, not even if you try to hide some of the assumed-to-be-public information instead.


How can Whatsapp identify forwarded attachments Sometimes Whatsapp shows that an attachment was often forwarded.
How do they know this if the message is end-to-end encrypted?
Even with hybrid encryption I encrypt with my key and store my attachment on the server.
So do they hash the attachment in the client and store the hash? So they would know what attachments I forwarded and when?

The attachments are processed as follows (source is the WhatsApp's White Paper);
First time of the attachment is sent

The sender generates a 32-byte random AES-256 key, $k_1$, and another random 32-byte key $k_2$ for $\operatorname{HMAC-SHA256}$
Encrypts the attachment $a$ with this key $c_a = \operatorname{AES-CBC-256}(k_1,a)$ and append the MAC of the $c_a = \operatorname{HMAC-SHA256}(k_2)$ to it.
The sender uploads this to the server in a blob store.
The sender encrypts the $k_1,k_2$, and SHA256 hash of the encrypted blob and URL of the blob to the receiver.
The receiver decrypts the message, receives the encrypted blob, verifies the SHA256 of it, verifies the MAC then decrypts it.

This is a media caching technique.
The attachment is forwarded
The receiver wants to forward the message;

Encrypt the URL and the key $k_1,k_2$, and SHA256 hash of the attachment that is received from the sender and forwards to someone else.

How can Whatsapp identify forwarded attachments

Simply add a "forwarded" tag into the message that contains the  $k_1,k_2$, and SHA25 of the attachment. Even forwarding has a counter to limit the fan out and WhatsApp doesn't know about it.

So do they hash the attachment in the client and store the hash?  So they would know what attachments I forwarded and when?

Not because of it, they don't the internal of the messages, however, the blob has stored in the WhatsApp server contains enough information to execute a traffic analysis if they want to execute.

Store this information; who uploaded the blob; when the blob is uploaded.
Store who wants to access this blob and when.

Now, the attacker can make graphs.
This is traffic analysis doesn't expose the message, however, if one of the receivers is breached the circulated attachment can give information about others.


What is the format of the TLS extension field? In the TLS 1.2 protocol, the client may send extensions. My question is: what is the format of this field? is it a list?

In TLS 1.2 client hello, the standard says:

  extensions
        Clients MAY request extended functionality from servers by sending
        data in the extensions field.  The actual "Extension" format is
        defined in Section 7.4.1.4.

At the server hello, the standard explicitly says it is a list. But I am not sure if this implies that the client also sends the extensions as a list:

  extensions A list of extensions.  Note that only extensions offered by
  the client can appear in the server's list.

I assume the same format is used in tLS 1.3 as well.

Section 7.4.1.2 of RFC 5246 defines the following ClientHello:

  struct {
      ProtocolVersion client_version;
      Random random;
      SessionID session_id;
      CipherSuite cipher_suites<2..2^16-2>;
      CompressionMethod compression_methods<1..2^8-1>;
      select (extensions_present) {
          case false:
              struct {};
          case true:
              Extension extensions<0..2^16-1>;
      };
  } ClientHello;

As you can see, you can add up to $2^{16}=65536$ bytes of extensions to your client hello in a list format as per section 4.3.


Does the position of the salt improve its effectiveness when hashing? Seems most documentation I have read suggests the salt should prefix the value to be hashed. Is this just for consistency, or is the salt more effective when prefixed?

If the hash function is a random oracle, then the salt can go wherever you wish, it will do its job.

On the other hand, there is, arguably, no such thing as a random oracle. On an existing, real, tangible hash function, details on how you input things may or may not trigger slight structural weaknesses in the function, which could impair the role of the salt, which is to prevent an attacker from doing exhaustive searches ("dictionary attacks") in a parallel way (time-wise or space-wise). In particular, on Merkle-Damgård hash functions (such as MD5, SHA-1 or SHA-256), the so-called "length extension attack" may be relevant.

So this is a matter of some delicacy. It seems best, generally speaking, to use constructions which have benefitted from wide scrutiny by many people. Salts are from the password-hashing business, and known good constructions for transforming passwords into keys are PBKDF2 and bcrypt.


Why is ethereum not using threshold signatures like dfinity for randomness? What's the drawback? So Ethereum goes for RANDAO. The disadvantage with RANDAO is that the last validator in the commit-reveal scheme is able to hold his contributed value back and thereby influence the random outcome. Ethereum is trying to overcome this by using verifiable delay functions.

Why all that hassle?
Why not just go for threshold signatures like Dfinity?
What's the drawback?

Some link to a statement from Vitalik Buterin on this would be highly appreciated. Otherwise, if you can explain it it's also fine.

This post is a little old considering the current conversations going on about the various approaches to generate secure, safe, live and unbiased randomness in Ethereum 2.0. However for a better update on the ongoing conversations, please let me share the latest progress in this discussion.
Ethereum 2.0 is proposing a combination of RANDAO ( biased entropy) + VDF (unbiased entropy) now as a choice for the source of randomness in the beacon chain. Justin Drake has written the following construction in the Ethereum Research forum.

Assume a global clock and split time into contiguous 8-second blocks and 128-slot epochs. Each epoch produces 32 bytes of (biasable) entropy to which correspond 32 bytes of (unbiasable) randomness In a recursive fashion, the beacon chain proposers of epoch (one per slot) are sampled using past randomness for some suitable constant.

A few researchers in the discussion forum have opined that it will have the following advantages over the threshold signature scheme of DFNITY.

The threshold relay scheme from DFNITY stands out as not being
biasable. Unfortunately, the beacon can stall if even a minority (e.g.
15% 1) of honest players go offline.
As indicated by @denett this does not work because the sampling process will weaken your honesty assumption. (Dfinity’s sampling weakens the global 2/3 honesty to 1/2 local honesty.) Sampling is required because the Distributed Key Generation (DKG) scales quadratically with the number of participants, and in practice you can’t get much more than 1,000 participants.
Another thing to consider is that there are two ways in which the
Dfinity beacon can fail. Citing the whitepaper: “We treat the two
failures (predicting and aborting) equally”. By improving liveness you
make the readomness beacon easier to predict.
Finally, the RANDAO + VDF approach allows for arbitrarily low liveness
assumptions. (For example, we could have a 1% liveness assumption by
making the RANDAO epoch longer.)

I had relentless participated in the Starkware Veedo Streak hackathon and used the VDF based Randomness through Beacon contracts deployed in TestNet and MainNet. It looks like the VDF approach is gaining traction in the Ethereum Research community.


DES Key Schedule Algorithm Reading through the DES Specification it says that the keys are permuted with PC-1 initially and then shifted left both $C$ and $D$. However, before it gets permuted again through PC-2 it does not mention how $C$ and $D$ are put together before going through PC-2.

Is it assumed that $C$ is the lower half of the input to PC-2 with the higher half being $D$ (this comes from it saying that they are $CD$), or are they multiplied together/some other operation is used?

CD

CD is collectively referring to the C and D Registers.  Their use and operation while simultaneous is independent.  C and D are concatenated together to specify PC2.

Permuted Choice 2

PC2 is a selection permutation.  You might notice that the first 24 bits of the selected Key are from the C Register (CD(1 to 28)) and the second 24 bits are from the D register (CD(29 to 56)).  The order of the selected Key bits in each have is non-linear.

The left portion of the table is recognizable as PC2 from the Digital Encryption Standard.

Permuted Choice 1

To demonstrate the how C and D Registers are concatenated we look to PC1.

The above table shows how PC1 maps a 64 bit input to the two 28 bit C and D registers from an 8 bit interface where the LSB of each input byte is a parity bit and the upper 7 bits are used as key bits loaded into the C and D Registers.  Once the C and D Registers are loaded they are independently shifted (recirculated) by either 1 position or 2 positions to distinguish each round key from it's neighbors.  Shift direction is in the opposite direction for encryption and decryption, reversing the key schedule order.

C and D operated simultaneously

The following table plotting selected Key bits versus round keys for encryption is taken from the Carl Meyers and Stephen Metyas book Cryptography, A New Dimension in Computer Security, subtitled 'A Guide for the Design and Implementation of Secure Systems', Wiley Interscience, 1982, ISBN-0-471- 04892-5.

It's generated by this answer's author from a program keytab (keytab.c, executed as keytab -s).  It demonstrates that the C and D blocks are independent that the first 24 bits of selected key are from the C Register and the last 24 bits of selected key are from the D Register.

The KS column and Bit rows demonstrate the round index and selected key bits of CD respectively.  The table is formatted to a) show that C and D recirculate independently and b) to fit in an 80 column display.

  Bit  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
KS
   1  15 18 12 25  2  6  4  1 16  7 22 11 24 20 13  5 27  9 17  8 28 21 14  3
   2  16 19 13 26  3  7  5  2 17  8 23 12 25 21 14  6 28 10 18  9  1 22 15  4
   3  18 21 15 28  5  9  7  4 19 10 25 14 27 23 16  8  2 12 20 11  3 24 17  6
   4  20 23 17  2  7 11  9  6 21 12 27 16  1 25 18 10  4 14 22 13  5 26 19  8
   5  22 25 19  4  9 13 11  8 23 14  1 18  3 27 20 12  6 16 24 15  7 28 21 10
   6  24 27 21  6 11 15 13 10 25 16  3 20  5  1 22 14  8 18 26 17  9  2 23 12
   7  26  1 23  8 13 17 15 12 27 18  5 22  7  3 24 16 10 20 28 19 11  4 25 14
   8  28  3 25 10 15 19 17 14  1 20  7 24  9  5 26 18 12 22  2 21 13  6 27 16
   9   1  4 26 11 16 20 18 15  2 21  8 25 10  6 27 19 13 23  3 22 14  7 28 17
  10   3  6 28 13 18 22 20 17  4 23 10 27 12  8  1 21 15 25  5 24 16  9  2 19
  11   5  8  2 15 20 24 22 19  6 25 12  1 14 10  3 23 17 27  7 26 18 11  4 21
  12   7 10  4 17 22 26 24 21  8 27 14  3 16 12  5 25 19  1  9 28 20 13  6 23
  13   9 12  6 19 24 28 26 23 10  1 16  5 18 14  7 27 21  3 11  2 22 15  8 25
  14  11 14  8 21 26  2 28 25 12  3 18  7 20 16  9  1 23  5 13  4 24 17 10 27
  15  13 16 10 23 28  4  2 27 14  5 20  9 22 18 11  3 25  7 15  6 26 19 12  1
  16  14 17 11 24  1  5  3 28 15  6 21 10 23 19 12  4 26  8 16  7 27 20 13  2

  Bit 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48
KS
   1  42 53 32 38 48 56 31 41 52 46 34 49 45 50 40 29 35 54 47 43 51 37 30 33
   2  43 54 33 39 49 29 32 42 53 47 35 50 46 51 41 30 36 55 48 44 52 38 31 34
   3  45 56 35 41 51 31 34 44 55 49 37 52 48 53 43 32 38 29 50 46 54 40 33 36
   4  47 30 37 43 53 33 36 46 29 51 39 54 50 55 45 34 40 31 52 48 56 42 35 38
   5  49 32 39 45 55 35 38 48 31 53 41 56 52 29 47 36 42 33 54 50 30 44 37 40
   6  51 34 41 47 29 37 40 50 33 55 43 30 54 31 49 38 44 35 56 52 32 46 39 42
   7  53 36 43 49 31 39 42 52 35 29 45 32 56 33 51 40 46 37 30 54 34 48 41 44
   8  55 38 45 51 33 41 44 54 37 31 47 34 30 35 53 42 48 39 32 56 36 50 43 46
   9  56 39 46 52 34 42 45 55 38 32 48 35 31 36 54 43 49 40 33 29 37 51 44 47
  10  30 41 48 54 36 44 47 29 40 34 50 37 33 38 56 45 51 42 35 31 39 53 46 49
  11  32 43 50 56 38 46 49 31 42 36 52 39 35 40 30 47 53 44 37 33 41 55 48 51
  12  34 45 52 30 40 48 51 33 44 38 54 41 37 42 32 49 55 46 39 35 43 29 50 53
  13  36 47 54 32 42 50 53 35 46 40 56 43 39 44 34 51 29 48 41 37 45 31 52 55
  14  38 49 56 34 44 52 55 37 48 42 30 45 41 46 36 53 31 50 43 39 47 33 54 29
  15  40 51 30 36 46 54 29 39 50 44 32 47 43 48 38 55 33 52 45 41 49 35 56 31
  16  41 52 31 37 47 55 30 40 51 45 33 48 44 49 39 56 34 53 46 42 50 36 29 32

You might note that KS16 shows the values for Permuted Choice 2 from the Digital Encryption Standard. It says that decryption can occur without being preceded by a shift operation should you actually use recirculating shift registers to hold C and D registers.  The above table demonstrates simultaneous operation.

C and D used independently

The following is a description of the inputs to each S Box in the round function f(R,K), expressed in E(R) and Ks bits.

Each six bits of KS are applied to each of eight S Boxes after XOR with the matching E(R) permutation bits.  The header row shows the Column Address bits (CA) and Row Address bits (RA) applied to each S Box.

f(R,K) can actually be devolved into operations associated with a nybble register of R, borrowing Row Address R bits from adjacent nybbles via the E permutation.  C Register selected key outputs are applied to S Boxes 1 - 4, while D Register selected key outputs are applied to S Boxes 5 - 8.

DES is hardware

You shouldn't be surprised we can't describe DES without resorting to hardware terms.  There's a paper by Miles E. Smid and Dennis K. Branstad of the National Institute of Standards and Technology (NIST) entitled The Data Encryption Standard Past and Future, first appearing in Proceedings of the IEEE, vol. 76, no. 5, pp. 550-559, May 1988 (and not copyright eligible as a a U.S. government work), which makes the distinction between Basic standards, Interoperability standards, Interface standards and Implementation standards and points out that the DES is an interoperability standard.  It describes how to interconnect an 8 bit interface to the Initial Permutation, Inverse Initial Permutation and Permuted Choice 1 as well describing which bits are association in time ordered hardware operations.

The Digital Encryption Algorithm described in FIPS Pub 46 (-1, -2 and -3)
describes the hardware implementing IBM's block cipher commonly known as DES and found in U.S. patents 3,958,081 and 3,962,539. The original implementations where bounded by chip count using MSI (Medium Scale Integeration) devices.  It's easily possible today to implement shift registers with a shift of distance of one or two, or use a schedule key register file as a look up, or some other 'faster' scheme.


Schnorr Ring Signatures - wrong hash results I don't know if I've placed the question right, It is half maths, half programming.
I'm writing Schnorr Ring Signatures on Elliptic Curves in Java and I have a problem. I've found scheme on integers and translated it to elliptic curves.

In point 3 on page 11

$R_s = g^a \prod_{i \neq s}(y_i^{-H(m, R_i)}) \ mod \ p$

and in my elliptic curve version

$R_s = aG + \sum_{i\neq s}(Y_i*-H(m,R_i))$

where $G$ is a generator, $Y_i$ is a public key of i-th user, $m$ is a message and $R_i$ is $a_iG$ where $a_i$ is random.

I have

basepoint $G$
cofactor $h$ to the order of $G$
order $n$ of $G$
points $A$ and $B$

My question is how to perform a modular inverse of $H(m,R_i)$. In Java I have a modInverse method on BigIntegers but I have to know value of $p$. How to find value of $p$? Or how to calculate $-H(m,R_i)$?

EDIT:
OK, thakns. I've found $p$ value. But still I'm getting wrong results. If someone would be so nice to look at it here is my sample code. Thanks in advance for help

If $g^a$ in the modular version translates to $aG$ or $a*G$ in the elliptic curve version, then $y_i^{-H(m, R_i)}$ should translate to
$$\begin{align*}
(-H(m, R_i))*Y_i&=-(H(m, R_i)*Y_i)&\text{(1)}&\text{ or equivalently}\\
&=H(m, R_i)*(-Y_i)&\text{(2)}&\text{ or equivalently}\\
&=((-H(m, R_i))\bmod n)*Y_i&\text{(3)}&\\
\end{align*}$$

The form (1) leads to an expression requiring one point subtraction or inversion:
$$R_s=a*G-\sum_{i\neq s}(H(m,R_i)*Y_i)$$

The form (3) leads to an expression that requires none:
$$R_s=a*G+\sum_{i\neq s}(((-H(m,R_i))\bmod n)*Y_i)$$

Note: By definition, $u\bmod n$ is the uniquely defined $v$ with $0\le v<n$ and $u-v$ a multiple of $n$. When $u\ge0$, $(-u)\bmod n$ can be computed as $n-1-r$, where $r$ is the remainder of the division of $(n-1+u)$ by $n$.


Maximum allowable correlation for a random sequence to be useful? This question is inspired by a RNG question and some of the comments in the one of the answers.  I have been designing random number generators in hardware recently and my results are significantly better than what I get from /dev/random and /dev/urandom.  I took a sample of 10000 results from /dev/random and /dev/urandom and the results are as follows:

I ran this a few dozen times and the results are about the same with /dev/random being better than /dev/urandom, but that's not the crux of my curiosity.

Mathematically, of course, we want a completely decorrelated sequence of numbers for a random set. My question is if there is a maximum value for correlation in a set of random numbers that is acceptable?  From the hardware standpoint, I can save a lot of power if I have slightly less random numbers and this is a very appealing idea for me.  I don't know if it matters, but I use my random number generator for a ECC engine.

Update
It seems that my /dev/random and /dev/urandom differences were outputs from the same device, but just with less entropy. My working theory is that the second read from the device has less entropy, but more than the OS minimum requirement. However, my question on the maximum correlation is still how much is the maximum acceptable correlation in a series of "random" numbers.

There is no limit as to the amount of correlation you can have from an entropy source for it to be useful, but correlation then places a restriction on how you extract the entropy.

The restriction is this:  you have to individually process an entropy block of a size that exceeds the length of correlation.  Thus no correlation between blocks.  For a Geiger tube you might have a slight settlement time after each reading that might be of length (n + 10).  That means you have to deal with blocks of readings greater than 10.  I use a web cam that outputs 25KB images, so I have to treat that as a full 25KB block (n+25K) to extract the entropy.  If I try to process the image on a byte by byte basis, I fall foul of the JPEG file format that envelops the true entropy within the image.

Correlation is  impossible to remove programmatically as that requires a complete theoretic model of the underlying physics of the source.  My suggestion is to side step it and consume entropy in blocks greater than any possible length of auto correlation.  If you're reading noise it might only be at most (n+2) anyway.

From your blog post that initiated all this:-

  /dev/urandom is a pseudo random number generator, a PRNG, while /dev/random is a “true” random number generator.

I would argue that both random and urandom are pseudo random number generators, and you are just comparing like with like and getting differing results!  /dev/random breaks my no more entropy out than in rule from this post hence I think that it's not a TRNG at all.


How can I figure out a hash algorithm? This may be trivial, and may be impossible... this is outside my field but willing to learn.

I have a hardware device that accepts a network MAC address (6 bytes of data) like this:
38-60-77-EC-1D-33

and produces a 2-byte hash, like this:
F0-9B

The same address always produces the same hash, and I can test any address I want, but only by hand. I have tried a handful of addresses to see if it's just a linear value, but it's not. This may simply be a checksum - there's no obvious security application, it's just a hardware handshake.

... is it going to be possible to reverse-engineer this? If so, how should I go about it?

This is going to be hard, isn't it.

Edit: Here are some samples:

00:00:00:00:00:00   684C
00:00:00:00:00:01   1717
00:00:00:00:00:02   96FA
00:00:00:00:00:03   E9A1
00:00:00:00:00:04   9520
00:00:00:00:00:05   EA7B
00:00:00:00:00:06   6B96
00:00:00:00:00:07   14CD
00:00:00:00:00:08   9294
00:00:00:00:00:09   EDCF

01:00:00:00:00:00   DF52
02:00:00:00:00:00   1BC7
00:01:00:00:00:00   BB1B
00:00:01:00:00:00   6434

Edit #2:
There is clearly a pattern. I've run 50 strategic numbers and so far I've figured out that:

The last digit repeats a pattern every 16 (F) numbers where every number appears exactly once. The digits change after 256 (FF) numbers but still repeat in groups of 16.
Also in each group of 16 numbers, the first digit is one of only 4 numbers. Each group of 16 (so far) uses a different 4 numbers, but the order they appear is perfectly consistent.

I think at this point it's just going to be "educated" brute force, but I'm much more optimistic than I was 4 hours ago. I've tried a few online checksum calculators, but if this sounds like a known algorithm I'd appreciate the help, and I'll keep hacking away...

This function has all appearance of being affine (or loosely speaking: linear), in the sense that has in cryptanalysis:
$$\forall (x,y,z),\;f(x\oplus y\oplus z)=f(x)\oplus f(y)\oplus f(z)$$
In other words: if the exclusive-OR of the inputs in any 4 lines is zero (e.g. the first 4 lines), then the XOR of their output is zero.

It follows that we can compute the output for any input $x$, as
$$f(x)=f(0)\oplus\left(\bigoplus_{j\text{ with bit }j\text{ set in }x}\big(f(2^j)\oplus f(0)\big)\right)$$
where $f(2^j)$ is the output for input the 48-bit bitstring with only bit $j$ set. A similar equation can be derived without guesswork from any set of input/output pairs with one more elements than there are input bits, and all the inputs but one linearly independent.

This also gives the equation for any output bit as a function of the input bits, as a chain of exclusive-OR of input bits and a constant bit.

Code implementing this is a three-liner with a loop on the 48 input bits, plus a table of 48 words of 16 bits; that makes the whole thing less than 200 bytes of compiled code, running under a microsecond on a PC.

Further analysis could perhaps reveal more regularity; like, this could be a truncated CRC of the input bits in some order. That guesswork could be necessary if you do not obtain enough input (in particular, if some input bit does not change in any of the available input/output pairs, the only way to guess its influence on output is to find some regularity in the influence of those inputs bits that vary). That would also allow making the code shorter, faster, and with a simpler specification.

Note: I decided to answer the question even though it contains a dump of plaintext-ciphertext pairs (usually a no-no on CSE), because it illustrates well a common (reverse)-engineering problem: making something compatible with a deployed unknown function, on the sole basis of examples, when that function turns out to be affine, as does any function written using only bitwise eXclusive-OR, shifts and rotations. The technique I describe works for many functions found in the field; in particular anything worth the name CRC, including countless failed attempts to implement some standard or academically proper CRC, which ended up in some ugly proprietary mess.


$m^b = z^b \pmod{n}$ - single solution $m = z$? If i have the following equation:

$$m^b = z^b \pmod{n}$$

Where all numbers are taken from the multiplicative group $\mathbb{Z}_n^*$.

Suppose I know the values $z$ and $b$. Can I state that $z = m$, or at least that it is a possible solution?

Is it the only solution?

Is it the only solution?

It will be iff $b$ and $\phi(n)$ are relatively prime.

If $b$ is relatively prime to $\phi(n)$, then the operation $x \rightarrow x^b \bmod n$ is a permutation of the set $\mathbb{Z}_n^*$, hence there will be exactly one solution to the equation $m^b \equiv z^b \pmod n$ (and since we know that $m \equiv z$ must be a solution, it must be the only one.

If $b$ is not relatively prime to $\phi(n)$, then there must be a nontrivial solution to $c^b \equiv 1 \pmod n$ (where nontrivial means "other than 1"); in fact, there will be at least $\gcd(b, \phi(n))-1$ such nontrivial solutions.  Values $m = z \cdot c^k \bmod n$ will be the other solutions to the equation.

As for finding these other solutions (which, as above, is equivalent to the problem of finding the nontrivial roots of 1), it's straight-forward if you know the factorization of $n$ (which is equivalent to knowing the value of $\phi(n)$; this includes the case of $n$ being prime.

First, we set $d = \gcd(b, \phi(n))$ and $e = b / d$ (and so $b = d \cdot e$, with $d$ being a factor of $\phi(n)$, and $e$ being relatively prime to $\phi(n)$.

Then, select a random value $r \in \mathbb{Z}_n^*$ and compute $s = r^{\phi(n)/d} \bmod n $; if $s$ happens to be 1, then go back and try another random number.

If $s \neq 1$, then set $c = s^{e^{-1} \bmod {\phi(n)}}$; that's one value of $c$

Now, if $d$ happens to be composite, then you might need to go through this procedure multiple times to find all the possible values of $c$; if $d$ is prime, then one value is sufficient (and the other roots of 1 are $c^k$ for $k \in \{2, …, d-1\}$

On the other hand, if you don't know the factorization of $n$, this is sometimes a hard problem, and sometimes not.  A case where this is not a hard problem; $b = 2$, which has $c = n-1$ as an easy-to-find solution.


How to provide partial confidentiality and full integrity for a protocol message? I want to provide confidentiality and integrity for a protocol. I don't want to encrypt the entire protocol message. I do not want to encrypt the header and timestamp of the protocol message, but I want to have the integrity for the entire protocol message. Thus I do the following:

1- encrypt the message except for the header and timestamp by using CBC.
2- digest the entire message (header, timestamp and encrypted message) by using HMAC.

Is that good practice? if No, what is the best practice?

Basically what you want is a authenticated encryption with associated data (AEAD) encryption scheme, of which there are several already available in various libraries.  So just see what is available on your system and use one of them.


Why is (gy, gx) signed in STS (station-to-station)? My question relates to the station-to-station protocol as described in https://en.wikipedia.org/wiki/Station-to-Station_protocol [1] and http://cacr.uwaterloo.ca/hac/ [2] p 519.

(1) Alice → Bob : gx
(2) Alice ← Bob : gy, EK(SB(gy, gx))
(3) Alice → Bob : EK(SA(gx, gy))

I fail to understand the reasons behind why Bob signs gy+gx (concatenated) and Alice signs gx+gy. [1, 2] say the order of gx and gy is important. Why? And why sign gy+gx? Are there variants of what is signed? A random challenge could be included?

The 1992 paper http://people.scs.carleton.ca/~paulv/papers/sts-final.pdf by Diffie et al answers the question. It has an example of an insecure variant of the protocol that uses signatures of random challenges. Furthermore, the section "Signing only one’s own exponential" considers a variant where Alice signs only gx. According to the paper, there is an attack on this variant when RSA signatures are used. And it seems open to replay attacks (see DuBuisson's answer).

The section "Signing only the other party’s exponential" considers the variant where Alice signs only gy. For this case the authors of the paper say: "we know of no general attack which applies to this case, but there are some concerns". One concern is that "it is imprudent to sign arbitrary text supplied by a potential adversary".


Point addition in NaCl/libsodium (Curve25519) In NaCl and libsodium, the crypto_scalarmult function implements the operation $Q = kP$ (scalar/point multiplication). There doesn't seem to be a function for point addition $K = P + Q$ though.

Something like point addition must be implemented somewhere I think, as part of the implementation of scalar multiplication. It would be useful to be able to access this for developing some protocols on top of Curve25519.

Is it deliberate that point addition isn't mentioned anywhere in the API or documentation? (Don't the authors want people implementing research-level protocols using their library?)
crypto_scalarmult delegates to crypto_scalarmult_curve25519 declared (in libsodium) in crypto_scalarmult_curve25519.h but I can't seem to find the definition in a .c file anywhere (in the latest version on GitHub)?
Is there a safe way to implement, or reuse an internal implementation, of point addition in libsodium?

Recent versions of libsodium have crypto_core_ed25519_add() and more: https://download.libsodium.org/doc/advanced/point-arithmetic


Fortuna: why are source ID and data length added together with entropy data into the pools Section 9.5.6 of Cryptography Engineering states that

  The concatenation [of source number, length of data, and data itself] is then appended to the pool.

Why are we including source number and data length? The source number is fixed for each source, the length of data is constant for many sources, so aren't we contaminating the pool with low entropy data?

You can't contaminate the pool with low entropy data. Hash functions "extract" up to the output size or the hash - slightly less, because of collisions.

The source number makes the output different for different sorces even if the input is the same.

The length is needed because else we could not differate two small inputs from one large input with special patterns. This depends on the usage of the hash function.


How to choose constants in a cryptographic function? A number of cryptographic functions have constants built in. For example, the constants used in RFC 2104 for HMAC, or the constants used in s-boxes (e.g., DES and AES), or MD5.  In general, how are constants such as these generated so as not to arouse suspicion of tampering or weakening?

There are some approaches.

In many algorithms it for the security doesn't really matter what constant is used, as long as it is not too simple, like initialization vectors for hash functions. (And of course, we need to use always the same number.) Then mathematical constants like binary expansions of irrational numbers like $\sqrt{2}$ (or roots of other numbers), $e$, $\pi$ can be used, to show that one didn't select the numbers to create a back door. This is known as a nothing up my sleeve number, the linked Wikipedia article contains some more examples.
The padding constants for HMAC, 0x36 for ipad and 0x5C for opad, are repeated (for the hash function's block size) and XORed with the key to generate the prefixes for the two hashing steps. 0x36 = 0b00110110 and 0x5C = 0b01011100 - these two values are about "as different as possible", to avoid any attacks which rely on a similar hash state after the key block for inner and outer hash. This is mainly a heuristic, as far as I understand.
In the DES S-boxes, the constants were randomly generated and then tested for resistance against differential cryptanalysis. As differential cryptanalysis was not yet known officially, and NSA didn't explain what they did (one only could see that they gave it back with other S-boxes), there was quite some suspicion that they put in a backdoor, while they actually made the algorithm harder to break.
In AES, the S-boxes are an implementation of a simple mathematical function (inversion in $\mathbb F_{2^8}$, followed by a linear transformation). One wouldn't need an S-box here, it just helps to efficiently implement it.
In the hash function Skein (one of the SHA-3 candidates), the initialization vector (initial state of the iteration) is not a fixed arbitrary number, but is gained by hashing a "configuration vector" (where we use 0 as init state). If one uses Skein only in common uses (e.g. a simple hash), i.e. always with the same configuration, one can hardcode the resulting hash state into the implementation instead of re-running it each time.


How to use "mod" related words in technical paper？ Modular reduction is a widely used arithmetic operation. I found many "mod" related words such as

modulo
modulus
modular

Can anyone explains the difference among these words?  Please give examples or idioms.

A modular operation is an operation done modulo some modulus.

"modular" is an adjective: modular inverse, modular operation, modular reduction, ...
"modulo" is indeed the Latin ablative of modulus, and that makes it an adverb: I walk modulo $n$, just like I walk fast.
"modulus" is a noun: the number $n$ is the modulus that you would use in some system.


AES with other SBoxes I'm not a cryptologist, just an interested engineer (& now retired).
I used to design hardware with AES en/decryption blocks & generate test vectors using my own Tcl script using the embedded aes function.
However, I was wondering if modifying AES to use more than 1 SBox (& inverse), it would be "more secure", or is that not the case?
I've found 1108 SBoxes that meet the original criteria (out of 256! possible combinations). My view would be to have a short table to indicate which SBox to use for each round of 14 (assuming 256 key).  I realise this would complicate h/w a bit, but not be very complicated to modify a C program.
Initially just using 2 SBoxes, the original & one other, but easily expandable to use 3,4.. etc in software.
Just after thoughts really.

Honestly, it would be more secure, but not by much, and that is assuming you are using finite field inversion s-boxes.
A better use of multiple 8-bit s-boxes would be to make them key dependent, however in software that can have the unfortunate side effect of creating another side channel to leak information about the key.
If you want something based on the AES design but with small modifications that make it more secure, what you want is not more s-boxes, but a better s-box with more algebraic complexity. In terms of round design that is probably the only modification you can make before it strays too much from the original design.
The other place to look is the key schedule, which is very simple and fast. This is both beneficial and detrimental, as it is probably the weakest point of the cipher, but makes applications requiring key changes usable. Think a wifi chip that needs a different key for each connected device and needs to constantly switch keys to communicate with them. It can also "roll" to save memory on embedded systems, but this means that round subkeys can be used to recover the key.
From a software only perspective, security can be improved with changes to the key schedule, slowing it down and generating the subkeys using a one way function with less linearity.


Does including the size of the hashed data improve security over just the hash Trying to settle a discussion at work. We are mostly concerned with pre-image resistance.

Suppose we have a common secure hash function $H$ (e.g. SHA-1/SHA-2) and some message $M$ we want to hash. The message has length $M_L$. For the message we provide the digest $D$ and the length of data digested $D_L$.

With regards to preimage-resistance, for which common hash functions is it more secure to check that

$H(M) = D$ $and$ $M_L = D_L$

rather than just checking

$H(M) = D$

?

First the obvious; checking $M_L=D_L$:

is unnecessary from a security standpoint IF $H$ really is secure, by definition of that; but who knows what's really secure?
can't harm preimage resistance (first or/and second), nor collision resistance;
can greatly increase speed, if the hash is computed only after checking $M_L=D_L$; that's a common reason to perform this test in file de-duplication;
can harm the conceivable objective of hiding $D_L$ in some attack scenarios (such as timing or other side-channel attack);
harms even so slightly a common objective: simplicity.

It is possible to construct a devious $H$ that is collision resistant and second preimage resistant only if it is also checked $M_L=D_L$; e.g., a variant of SHA-256 that matches the original for messages of length $l\ge255$ bits; and for shorter messages outputs the original message, a one bit, and $255-l$ zero bit(s). That can be improved to a hash that is very secure from the standpoint of second preimage resistance if $M_L=D_L$ is checked, and less secure (according to some parameter) otherwise. That's indicative checking $M_L=D_L$ could help security for some otherwise insecure hashes.

If we take MD5 as an example: we know how to create collisions with little effort (including for messages with different and arbitrary beginning), but that's only if these messages have exactly the same length. Otherwise, the best known attack is brute force (feasible, but never performed publicly as of today for being too expensive). However that applies to collision-resistance, not to the question's preimage resistance (neither first nor second). Thus, in the case of MD5, we know that adding a check that $M_L=D_L$ does not significantly improves collision resistance, but MD5 remains preimage resistant without that check.

Definitions used:

first preimage resistance: given some arbitrary value the size of a hash, it is difficult to find a message with that hash.
second preimage resistance: given some arbitrary message, it is difficult to find a different message with the same hash.
collision resistance: it is difficult to find two distinct messages with the same hash.


What is RSA key normalization? How can I understand the term RSA key normalization? What exactly is done in the process??
Please explain.

RSA key normalization is merely the convention that when comparing public keys we view them as two numbers where the first number is the public exponent and the second is the public modulus. Now in the case of RSA if you're given the public key as two numbers then the big composite one is the modulus and the smaller one which is often 65537 is the exponent so it's pretty obvious which is which.

The need for normalization is more obvious with DSA keys which involve four numbers of which two (the generator and the public value) would be impossible to distinguish if $h$ was chosen at random when the generator $g=h^{(p–1)/q)}$ was calculated). In all cases with DSA if you're just given the four parameters in any order you have to do a bit of extra calculation to make sense of it and normalization takes care of the whole issue.


Why only non-prime order fields have small subgroup attacks? Why don't prime-order curves have small subgroup attacks?

It seems that I can choose a Generator such that it has a small order, maybe 2 points, and so an attack could generate all of the points in that subgroup and figure out the scalar that exponentiated it.

Why only non-primes this is possible? Do prime fields have subgroups of a certain size, that ensures this?

Also is it correct to say "prime-ordered curves" ? It is the Field that the curve is defined over that has prime order, so I feel like i'm saying it wrong.

In Group theory, it is known that if $G$ is a finite group and $q$ is a prime number dividing the order of $G$ (the number of elements in $G$), then $G$ contains an element of order $q$ (Cauchy's theorem). And the order-$q$ element generates an order $q$ subgroup.

Thus if a group $G$'s order $N$ is not a prime number, then $N$ can be factored and $q_1,\cdots,q_n$ are the prime factors of $N$. For each $q_i$, there must exist a subgroup of order $q_i$. When $q_i$ is small, the subgroup is small. Hence small subgroup attack may be possible.

If a group $G$'s order is a prime number $p$, then by the Lagrange's theorem, the order of every subgroup $H$ of $G$ divides the order of $G$. Now $p$ has only two factors $1$ and $p$, thus $G$ can have two only subgroups: the trivial subgroup containing the identity $\{1\}$, and $G$ itself. There is no other small order sub-groups.

You also need to distinguish the finite field $F_p$ and the curve over the finite field $F_p$. They are two different things. The order of $F_p$ is the $p$ (elements are integers from 0 to $p-1$, inclusive), and the order of the curve over the finite field $F_p$ is the number of points on the curve and is bounded by the Hasse theorem $|order(E(F_p)) - p-1|\le 2\sqrt{p}$. A curve can be prime-ordered (or we can use a prime-ordered subgroup of all the points on the curve if the curve order is composite), but it is not simply because it is over a prime field.


Average/approximate difference in value between valid consecutive $x$ coordinates in ECC? From my basic understanding not all values of $x$ coordinates can satisfy a given elliptic curve equation, i.e. some $x$ coordinate values are not valid points on the curve because $x^3+ax+b$ is not a square.

Therefore, I would like to know what the average/approximate difference $d$ in value between any two valid consecutive $x$-coordinate integers is; if e.g. $x_1$ and $x_2$ are two consecutive valid $x$ coordinate integers on a given curve then in general, what is average/approximate difference value $d = x_2-x_1$?

Here's a justification for the estimate in CodesinChaos' comment.

Helmut Hasse proved in his 1936 series of papers "Zur Theorie der abstrakten elliptischen Funktionenkörper" that any elliptic curve $E$ over a finite field $\mathbb F_q$ satisfies the inequality
$$ \lvert q+1-\#E(\mathbb F_q)\rvert\leq2\sqrt q \text, $$

that is, the number of points is (very) roughly approximated by $q+1$. Since there are almost always (except when $x^3+ax+b=0$) precisely zero or two points corresponding to a given $x$ coordinate, this implies that the points on the curve assume about $(q+1)/2$ different $x$ coordinates. Therefore, the average distance between two "consecutive" (strictly speaking, this is not meaningful without a partial order on $\mathbb F_q$) valid $x$ coordinates is close to $\frac{q+1}{(q+1)/2}=2$.


Is Finite Field Multiplication Distributive? Moving Affine Transform in AES In AES the output of the SubBytes step is equal to:

$a_{0-15} = d*c_{0-15}^{-1}+b$

where $d$ is a constant 8x8 matrix and b is a constant 8x1 matrix both in $GF(2)$. The inversion is done in $GF(2^8)$.

After ShiftRows the output column of each MixColumns can be expressed in terms of four select $a$ values.

$m_0 =  2a_0+ 3a_1 + a_2 + a_3$

$m_1 =  a_0 + 2a_1 + 3a_2 + a_3$

$m_2 =  a_0 + a_1 + 2a_2 + 3a_3$

$m_3 =  3a_0 + a_1 + a_2 + 2*a_3$

Is there any reason that you can't take $m_0$ for instance and write it as:

$\begin{align*}
m_0 =& 2(da_0+b) + 3(da_1+b) + (da_2+b) + (da_3+b)\\
=& 2da_0+2b + 3da_1+3b + da_2+b + da_3+b\\
=& d(2a_0+3a_1+a_2+a_3)+b\\
\end{align*}
$

This would be the MixColumns operation followed by the affine transform.

From the above question $m = da_0$

At the bit level:

$m\oplus b = [m_7 \oplus b_7 , m_6 \oplus b_6 , m_5 \oplus b_5 , .... , m_0 \oplus b_0 ]$

$
\begin{align*}
2(m\oplus b) =& \operatorname{xtime}(2(m\oplus b)) = \\
=& [m_6 \oplus  b_6 , m_5\oplus b_5 , m_4\oplus b_4, m_3\oplus b_3 \oplus (m_7\oplus b_7), m_2\oplus b_2 \oplus (m_7\oplus b_7) ,\\& m_1\oplus  b_1,m_0
\oplus b_0 \oplus (m_7\oplus b_7),m_7\oplus b_7]\\
\end{align*}
$

Where the multiplication by $02$ is denoted $\operatorname{xtime}(x)$.

$
\begin{align*}
2m =\;& [m_6 ,m_5,m_4,m_3\oplus m_7,m_2\oplus m_7,m_1,m_0\oplus m_7,m_7]\\
2b =\;& [b_6 ,b_5,b_4,b_3\oplus b_7,b_2\oplus b_7,b_1,b_0\oplus m_7,m_7]\\
\end{align*}
$

It follows that:

$2m\oplus 2b = 2(m\oplus b)$

because they result in the same formula at the bit level. You can see a similar result for multiplication by 3.

However, the question also assumes that it is possible to convert $2da_0 \oplus  3da_1 \oplus  da_2 \oplus  da_3$ to $d(2a_0\oplus 3da_1 \oplus  da_2 \oplus  da_3)$ this is not possible because it would require the original to be written as $d2a_0 \oplus  d3a_1 \oplus  da_2 \oplus  da_3$ but matrix multiplication is not  commutative.


Can wiping a disk writing zeros on an encrypted device be a weak point? Can cryptsetup suggestion of wiping a disk before encryption with zeros written to an encryted device as described in question 2.19 as the recommended method on the CryptsetupFAQ (the part that starts with "For device set-up, do the following:" (which ends writing the encrypted random looking represantation of zeros) be a weak point as an attacker, knowing that the device is encrypted with LUKS, could suppose that the end of the disk is just zeros. With this information could he more easily find the key used on the initial wipping and, with this info, isolate the part of the disk that actually has relevant encrypted information?

The output of an encrypted stream of zeros is absolutely indistinguishable from random data.

What you do is not write zeros to the block device for the drive, but for the encrypted mapping. That is, instead of writing zeros to /dev/sdx, you write to /dev/mapper/sdx_crypt. This results in the contents on the actual drive being completely randomized. Even though an attacker may know that zeros were encrypted, they would be no closer to finding the key than before. If they were, it would mean the underlying cipher is vulnerable to a known plaintext attack, and none of the supported LUKS ciphers (AES, Twofish, Serpent, etc.) are. In fact, any symmetric cipher that was badly vulnerable to a known plaintext attack would be considered fatally broken, and would be either revised or discarded.

To prove a point, you can see that many high-quality cryptographic random number generators work by encrypting a counter with a block cipher. An attacker knows exactly what was encrypted by the block cipher. They know that the nth block of output is an encryption of integer n itself, yet it doesn't make it possible for them to predict any of the output or retrieve the key. Ciphers are stronger than you think.


How does the certificate trust model work in detail? How does the whole achitecture between the certificate authority (e.g VeriSign) and its clients (e.g foo.com) work.

How does my browser know that foo.com hasn't created its own certificate, wrote "VeriSign" as issuer, signed it with its own private key and wrote the corresponding public key into the certificate?

Where is the part in the certificate from foo.com (issued by
VeriSign) that creates the link to its certificate authority? I guess it's certainly not the literal of the issuer (VeriSign).

All the explanations I've got stopped at this point and just stated "the browser checks that it is issued by VeriSign". How does it check that? Is there an algorithm used which allows the clients certificate (e.g foo.com) also to be verified with the public key from the VeriSign and result in the same hash?

certificate from foo.com => client uses the public key from foo.com => receives hash x
certificate from foo.com => client uses the public key from the preinstalled VeriSign root certificate) => same hash x

How are those two certificates interrelated with each other?

A X.509 certificate contains the following information:

The name of the subject the certificate belongs to.
The public key of the subject. This public key corresponds to a private key. The subject is assumed to have exclusive access to this private key.
A reference to the issuer of the certificate (e.g. VeriSign or some other certificate authority). For a self-signed certificate, the issuer will be identical to the subject.
Some more fields, such as the validity period of the certificate, extensions that specify how the subject public key is supposed to be used, and various information the issuer decided to associate with the certificate.
A digital signature of the DER encoding of all of the above information.

If the RSA PKCS#1-v1.5 signature algorithm is used, the DER encoding is hashed using a specified digest algorithm, that digest is PKCS#1-v1.5 signature encoded, and a RSA private key operations is performed on that encoding using the issuer private key.

Server side, the server will obtain a server certificate by generating a key pair, keeping the private key strictly private, and sending its subject name together with the public key to a certificate authority. The certificate authority verifies that the entity that sent the public key also is properly identified by the subject name that was provided. If verified OK, the issuer issues a server certificate.

When a client connects using TLS (e.g. HTTPS), the server will send the server certificate as part of the initial handshake messages, and use the corresponding private key to generate or decode some part of the handshake (e.g. sign an ephemeral public key, or decrypt a key transport message), in such way that only an entity in possession of the private key, would be able to complete the handshake and end up with the same shared key as the client.

Client side, the browser will have a list of self signed root CA certificates corresponding to the certificate authorities the browser manufacturer has decided the client user should trust for server authentication.

When the client gets the server certificate handshake message, it typically verifies the digital signature (using the public key from the issuer certificate), and that the subject name of the certificate matches the domain part of the URI it is attempting to connect to. Additional verification, such as offline verification of the certificate validity period, and online or offline verification of the revocation status of the certificate, is also recommended.

If the server certificate checks out, the client extracts the public key from the certificate and uses it for completing the handshake. If the handshake completes OK and a shared secret integrity key gets generated, the information sent by the server from thereon will be authenticated to the client.


Fast MAC for 64-bit inputs I am looking for a fast MAC (~few machine instructions) to be used for hash tables with 64-bit public inputs.  I can't use SipHash as the hash function will be inlined in too many places and so the code size of SipHash is too large.  The sole use of the MAC value will be in hash tables.  I want to avoid hash collision DoS.

I'll precisely define the problem, and propose a solution based on AES-128, requiring about 13 instructions on many modern CPUs for something academically secure in a model where the hashes leak, down to about 8 instructions if we trust my intuition that we can in practice reduce the number of rounds in a model where only the number of collisions leaks.

It is asked a function changing a 64-bit input $m$ into an hash suitable as primary index in a hash table, avoiding malicious choice of $m$ intentionally causing collision at that stage (we ignore later collision resolution). The number $n$ of hash table entries is a public parameter, with $\log_2(n)\ll64$, perhaps $\log_2(n)\approx24$ (good for 16 million entries in the table). The function will also have a secret key parameter $k$. We'll note $h=f_{(n,k)}(m)$ where $f_{(n,k)}$ is the desired function, $m$ is the 64-bit input, and $h$ is the hash output, with $0\le h<n$. Evaluation of $f_{(n,k)}$ for additional values of $m$ must be fast, and compact (it is duplicated many times to avoid function call overhead).

The minimum desired security property, handling counting of collisions by timing measurement, is that an adversary not knowing $k$ (because it was chosen randomly at hash table creation, and not revealed) and able to choose up to $n$ distinct $m_u$, can can not cause significantly more collisions than for a random choice of function $f$, with knowledge when choosing $m_u$ of the number of collisions for each $v<u$, that is of the number of $w<v$ with $f_{(n,k)}(m_v)=f_{(n,k)}(m_w)$.

A simpler and stronger security property, handling the case where the results of an in-order hashtable traversal are leaked, would be that the adversary can not distinguish $f_{(n,k)}(m_u)$ from random, including in an interactive setup where the adversary chooses $m_u$ with knowledge of $f_{(n,k)}(m_v)$ for each $v<u$.

The stronger security property is met by any MAC reduced modulo $n$; that however is neither fast nor compact if we chose, say, HMAC-SHA-256. But if there is hardware support, a good option, also secure with cryptographic certainty under the stronger security property, is to built the MAC around AES-128:

pad $m$ to 128-bit (e.g. with zeroes)
apply AES-128 encryption with key $k$
reduce result modulo $n$.

Note: that works fine for $m$ of any fixed size up to 128 bits, or $m$ of variable size up to 127 bits with some injective padding to 128 bits.

For even more speed at the expense of academically recognized security, we can arguably reduce the number of AES rounds, from 10 down to some debatable minimum, perhaps 5 if we are content with the minimum desired security property handling timing attacks only (I would not consider 4 without extra precautions, see note below). That's not conservative; but getting to know only the collisions rather than the AES ciphertext, for a limited number of queries, make things hard for the adversary.

If the CPU has the AES NI instruction set, $r\le10$ AES-128 rounds cost $r+1$ instructions (one initial pxor, $\max(r,9)$ aesenc, and when $r=10$ one aesenclast) which can each reference a pre-computed AES 128-bit subkey stored in memory at initialization of the hash table.

For simplicity and speed, and when $n\ll64$, the reduction modulo $n$ can be made over only half of the AES result, with only minor security impact (entries at the end of the tables will be slightly less hit). Modern 64-bit CPUs compute the remainder of the division of a 64-bit quantity by a 32-bit quantity with a single instruction.

Note: when we push things towards speed and heavily venture in the round reduction route, it seems worthwhile to slightly bend the problem definition by choosing $n$ odd (or better $(n\bmod8)\in\{3,5\}$), which allows the reduction step modulo $n$ to add some final diffusion; and, assuming we can keep the exact choice of $n$ secret (including: the adversary can not reliably measure our allocated memory), choose $n$ random in a small public interval (like from the targeted $n$ to 105% of that), in order to make that extra step keyed.

If we want something that can be coded in portable C, or without aesenc, we'll want to replace AES with some other primitive, likely of the ARX variety; considerations impacting its choice include compiler support for wide wordsize and fast rotation.


Does double hashing increase resistant against first preimage attacks? Let's take Bitcoin as an example. Bitcoin uses SHA256, which can be vulnerable to collision and preimage attacks - although this is extremely unlikely to happen in the near-future.

However, let's say an evil genius figures out how to compromise Bitcoin by developing a way to perform a first preimage attack against SHA256 (in other words, he finds an input that hashes to a specific output; i.e., given y, he finds an x such that h(x) = y). But Bitcoin uses double hashing, rather than just hashing once.

Therefore, my question is this: does double-hashing increase the resistance of SHA256 against a first preimage attack?

Define $g(x)=h(h(x)).$ If the original preimage attack has complexity $C,$ and success probability $p$ then depending on what kind of structural properties of SHA256 it uses, you should be able to use the same principle and have complexity $2C=O(C)$ at the cost of reduced success probability $p^2.$

After all the preimage of $y$ under $g$ is just the preimage of the preimage of $y$ under $h,$ and if the original attack works it should not depend on some deep properties of $x$ but only the properties of the hash function $h$.

In particular, it should work to find the preimage of $z=h^{-1}(y)$ when you apply it to $z.$

It's up to you whether you call this an "improvement" or not. It's very marginal if we operate in a regime where success probability is nearly $1.$

There is the convention in computer science that a randomized algorithm is deemed to be successful if its success probability $p$ obeys $p\geq 2/3,$ so you can read the above comment in this light.

CoDomain Issue: As in the comments, we can only use the preimage $h^{-1}(y)$ as input to the next stage if it falls into the hash output space. This is more tricky; if we assume $h$ behaves like a random function on its codomain then each output $y$ will have no preimages with probability roughly $e^{-1},$ and otherwise an average of $1/(1-e^{-1})$ preimages with the highest possible number likely to be around $\log(n)/\log\log(n)$ where $n=2^{256}.$ So the complexity of a preimage attack restricted to the codomain will be comparable to the regularly assumed complexity of an arbitrary preimage attack under the random oracle model which is that to be successful with probability $q$ you need to try $q n$ random inputs.

See the report (search on http://cacr.uwaterloo.ca/): Stinson, D.R., Some Observations on the Theory of Cryptographic Hash Functions CACR Research Report, September 12, 2002.


Is there a public-key cryptography method that enables public keys to be much smaller than private keys? Does a public key cryptography method that enables the public key to be orders of magnitude smaller than the private key exist?

Yes. Hash based signature schemes are a prime example. The private/secret key of a Merkle tree is the whole list of leaves, while the public key is the root hash.

In practice the leaves are not usually all stored, but derived from a shorter key. Even then it may be useful to store e.g. $O(h)$ hashes to accelerate signing, where $h$ is the tree height. With CMSS (pdf) $T$ levels of trees are generated and the signer stores the verification keys for the active tree at each level, which is about $T$ times as much data as the public key.


Okay to use OpenSSL to encrypt then sign a message? I am planning on encrypting a message then signing the message so the recipient can authenticate the source. Reading this article has me concerned that I'm doing something wrong.

My current plan is to use OpenSSL to do the following:

Create a random key
Use key to encrypt message with a block cypher
Encrypt key with recipient's public RSA key
tar the encrypted message and encrypted key
sign the encrypted package using openssl dgst
tar the signature and encrypted package for delivery

Is there anything wrong with this approach?

This is being used for transferring firmware for an embedded device. The firmware includes an entire filesystem, including a private key. It needs to be encrypted so the private key is not exposed, and it needs to be authenticated so that a third party cannot install their own firmware and have access to the device (and the private key within).

I see a few issues with this approach:

First, since you're signing the ciphertext and sending the signature in plain, anyone who has your public key can verify that you did, in fact, sign that message, even if they won't be able to actually decrypt it.  This may or may not be something you want.
More importantly, anyone who intercepts the message can strip your signature and substitute their own (or, if the protocol allows it, leave the message unsigned).
Further, if the symmetric cipher used to encrypt the actual message is malleable (as e.g. many common non-authenticating block cipher modes are, at least to some extent), the interceptor might also be able to modify the message before re-signing it, for example replacing an embedded copy of your name or public key with their own.

The obvious solution to these problems is to follow the advice in the article you linked to:

Combine (e.g. tar) the plaintext and the public key of the recipient.
Sign the combined plaintext and recipient's public key.
Combine (e.g. tar) the signature and the signed message.
Generate a random key and encrypt the combined message and signature with a symmetric cipher using that key.
Encrypt the random key with the recipient's public key.
Combine the encrypted message from step 4 and the encrypted key from step 5.

I've followed your example above in keeping the symmetric and asymmetric encryption steps (4 and 5) separate — I'm not familiar with the OpenSSL tools, but many public key crypto implementations provide a way to do both in one step, since it's the only practical way to encrypt large messages with asymmetric crypto.  Similarly, the signing step typically involves first hashing the message and then signing the hash, but I haven't explicitly separated those steps since you didn't either.

Ps. It would also be possible (and perhaps preferable) to use key encapsulation (KEM) in steps 4 and 5, if your crypto toolchain supports it.  Basically, instead of generating a random symmetric key and then encrypting it with the recipient's public key (which generally involves padding and other complex details), you generate a random chunk of data within the message space of the asymmetric cipher (e.g. a random number less than the modulus, for RSA), encrypt it using the plain "textbook" version of the asymmetric cipher (with no padding or other complications), and also hash it to obtain the key for the symmetric cipher.  The recipient then decrypts the random data with their private key and hashes it to obtain the symmetric key.  The advantage of KEM is mainly one of simplicity, though, so if you're already working with a toolchain that supports normal asymmetric encryption with padding, but not KEM, then it's probably not worth it.


ECDSA - point order criterion i am creating some primitive demostration for ECDSA over small curve (p < 229). But my implementation have some weird issues. Verify process return false even if the signature is correct. Because I am testing it for some time, trying to find problem I discovered that verify work only if point order is prime.

So my question is, is there some condition for point order? And what about point with non prime order? Don't use?

I have been reading some papers about ECDSA, but I didn' t find anything about that.

Without more details, I can't be certain what's going on with your implementation.  However, here is one thing that can certainly cause it to fail sometimes if $n$ is composite: the ECDSA verifier needs to compute $s^{-1} \bmod n$ (where $s$ is effectively a random number between 1 and $n-1$).  If $n$ is composite, then $s$ might not be relatively prime to $n$; if it is not, then $s^{-1}$ won't exist (because there's no number $t$ such that $s \cdot t = 1 \mod n$).  If this happens during the verification, then either your modular inversion routine (which computes $s^{-1} \bmod n$) will fail, or it will claim to succeed, and return some incorrect value (which will cause later calculations to fail).

If the order of your generator is composite, you'll run into a second problem; it'll be easier to break.  ECDSA can be broken if you can solve the 'discrete log' problem; that is, given the generator $G$ and a point $Q$, you can compute the value $d$ such that $Q = dG$.  Now, if the order of the generator $G$ is composite (say, $pq$), then an attacker could compute $pG$, $qG$, $pQ$, $qQ$, and solve these two discrete log problems $pQ = d_p(pG)$ and $qQ = d_q(qG)$, and given the values $d_p, d_q$, reconstruct $d$.  Solving these two discrete log problems would be considerably easier than solving the single discrete log problem (because the orders of the points involved are smaller); and hence we've just made things easier for the attacker.

Because generators with composite order can cause the verify to fail, and because they're cryptographically weaker, we always use generators with prime order.


Isn't the deterministic property of (EC)DSA a security problem? From what I read in Wikipedia's article "Elliptic Curve DSA ~ Security", the "deterministic" generation of $k$ can help prevent certain type of attacks (such as the one happened to Sony).

However, wouldn't the deterministic property be predictable as compared with "probabilistic encryption"? To me, it seems like RSA does use padding to make it non-deterministic. From a security point of view of, wouldn't that be undesirable?

We are talking about signatures here, not encryption. The two activities are quite different. In the case of signatures, there is nothing secret except the private key, whereas in the case of encryption, both the private key and the message to encrypt should remain confidential (you encrypt the data precisely because you want to keep it confidential).

Asymmetric encryption requires some randomization because if it was deterministic, then an attacker could make an exhaustive search on the data itself. In the case of signatures, there is no confidential data on which the attacker may want to run such a brute force attack (indeed, no confidential data at all), so this specific issue does not apply.

Indeed, the "old" padding for RSA signatures (EMSA-PKCS1-v1_5, more usually known as "PKCS#1 v1.5") is deterministic, and, as yet, unbroken. The newer version (EMSA-PSS) is randomized, but, as PKCS#1 puts it:

  RSASSA-PSS is different from other RSA-based signature schemes in
     that it is probabilistic rather than deterministic, incorporating a
     randomly generated salt value.  The salt value enhances the security
     of the scheme by affording a "tighter" security proof than
     deterministic alternatives such as Full Domain Hashing (FDH); see [4]
     for discussion.  However, the randomness is not critical to security.
     In situations where random generation is not possible, a fixed value
     or a sequence number could be employed instead, with the resulting
     provable security similar to that of FDH [12].

(Emphasis is mine.)

In the case of (EC)DSA, the $k$ value has some specific requirements which do not have a counterpart in RSA; namely, from the point of view of any attacker, $k$ should be as if it was generated randomly and uniformly in the $1..q-1$ range, where $q$ is the order of the subgroup in which the algorithm is applied, with one optimization: it is permitted to reuse the same $k$ value as a previous signature, provided that all the inputs are the same (same private key, same input message). We can see that this "optimization" is safe if we consider the following attack model:

The attacker is given access to a black box which computes the signature on messages that the attacker chooses, using a private key $x$ that the attacker does not know.
The attacker may submit $n$ signature requests to the box ($n$ messages $m_i$), thus resulting in $n$ corresponding signatures ($s_i$).
The attacker's goal is to make a forgery: a new message $m$, distinct from all the $m_i$, and a corresponding signature $s$.

The "optimization" is then modelled as a filter/cache on the box, which remembers past requests from the attacker; if a request is made for a message which was already seen ($m_j = m_i$ for $j \gt i$), then the filter blocks the request, and returns the previous signature instead of making the box work again (i.e. it forces $s_j = s_i$). In the model above, this is a restriction on the attacker, so this can only strengthen the algorithm, not weaken it.

This model actually explains why, in all generality, derandomization is safe for signature algorithms: any random value used in the course of the algorithm can be replaced with a deterministically generated value, provided that the generation system takes as input both the message and the private key, and acts as a random oracle. This is exactly what RFC 6979 does. (Of course, random oracles are more easily talked about than incarnated; e.g. see this. RFC 6979 uses HMAC-DRBG as a "practical random oracle".)


Is the one-more discrete log problem hard in the Generic Group Model? In the Generic Group Model (GGM), a concrete cyclic group of (known) order $n$ is replaced with an idealized version: a random encoding for group elements is chosen, and the adversary only gets access to the encoded form of any input group elements (such as the generator/public key/...), and an oracle to apply the group operation on them. The encoding is unique, so group elements can be tested for equality. It can be seen as the analogue of the Random Oracle Model for groups instead of hashes.
It is well-known that the discrete logarithm problem is hard in the GGM: Shoup showed that any generic algorithm needs $\Omega(\sqrt{p})$ group operations, where $p$ is the largest prime factor of $n$.
My question is whether the one-more discrete logarithm problem (OMDL) is also hard in the GGM. To break OMDL, an adversary is given $k+1$ random group elements, can make $k$ queries to a DL oracle, and must then succeed in finding the discrete logarithm of all $k+1$ inputs.

Yes, this was shown in a recent work of Coretti et al [CDG].  Loosely speaking, the lower bound states that an adversary that makes at most $T$ queries to the GGM oracle succeeds with probability at most $T^2/N$, where $N$ is the size of the group. They in fact consider a stronger model where the adversary is allowed arbitrary pre-computation in the GGM. See §5 for more precise statements and Table 2 for a summary of their results.
[CDG]: Coretti, Dodis and Guo, Non-Uniform Bounds in the Random-Permutation, Ideal-Cipher, and Generic-Group Models, Crypto'18


Could time lock encryption be implemented through indistinguishable obfuscation? In the paper "How to build time-lock encryption", the authors give a theoretical solution to build time-lock encryption using multi-linear based witness encryption and blockchain. However, an instantiation of the construction is unfeasible to build because of the inefficiency of multi-linear maps.

So, if witness encryption based on multi-linear maps can't provide the efficiency required for the time-lock encryption, what alternatives are there? There are witness encryption schemes built from indistinguishable obfuscation, could time-lock encryption also be implemented using that?

Time-lock puzzles can be built from indistinguishability obfuscation through succinct randomised encodings: see the work of Bitansky et al. [BGJ+,BGL+] for more details.

[BGJ+]: Bitansky et al. Time-Lock Puzzles from Randomized Encodings. ITCS'16

[BGL+]: Bitansky et al. Succinct Randomized Encodings and their Applications. STOC'15


Is it hard to compute $g^{ab}$ when given $(g, g^a, g^b, \frac{a}{b})$? We know that the CDH problem, computing  $g^{ab}$ from given $(g, g^a, g^b)\in\mathbb Z_p^3$, is hard. Is it still hard with an auxilary information $\frac{a}{b}\bmod q$ (where both $p$ and $q$ are large primes with $q|p-1$, and $g$ is a generator with order $q$) ?

It is indeed a hard problem - in fact, it is at least as hard as the square Diffie-Hellman problem (SDH), which states that given $(g,g^a)$, it is infeasible to compute $g^{a^2}$. It is a standard and well-studied assumption, and it can be reduced to CDH (correcting a previous version of this answer where I said it does not - I was confusing with the decisional version for which no such reduction is known).
Intuition: intuitively, SDH is exactly a CDH instance together with the constraint $a/b=1$. Hence, it is a particular case of the problem you consider, where $a/b$ is known.
Reduction: given an algorithm $A$ solving your problem, here is how you solve an SDH instance: on input $g,g^a$, pick a random exponent $\lambda$, and compute $g^{\lambda^{-1}a^2} \gets  A(g,g^a,g^{\lambda^{-1}a},\lambda)$. I let you check that the input to $A$ is indeed distributed as a random instance of your problem. Then, compute $(g^{\lambda^{-1}a^2})^{\lambda} = g^{a^2}$.
For the reduction from SDH to CDH, it's a standard one; the trick is to use the identity $(x+y)\cdot (x-y) = x^2-y^2$. Setting $x = (a+b)/2$ and $y = (a-b)/2$ gives $ab = ((a+b)^2-(a-b)^2)/4$, from which the reduction to CDH is straightforward, with two calls to an SDH oracle.


how many blocks are encrypted at a time in DES Algorithm? I know that block ciphers encrypts data in the shape of specified blocks and DES also belong to block cipher family. I totally understand the procedure of DES, but I am confused that is DES take all the blocks of 64 bits of any plaint text and apply the process to all of blocks at a time or it encrypts first blocks then 2nd and 3rd and so on..
can anyone explain it Please??

This is in fact a question about modes of operation, as mentioned in a comment.

The basic operation of DES itself only defines the block cipher, and the encryption of a block.  The encryption of multiple blocks with a single key is managed by the further application of a mode of operation.

Some modes of operation, like ECB, or CTR, are parallelizable.  In this modes, the encryption of multiple blocks can be done independently, and so the blocks can be split apart and encrypted simultaneously.

Other modes of operation, like CBC, are sequential.  In the case of CBC, each successive block requires the previous block to have been encrypted before encryption of the next block can begin.

There is a further consideration of implementation.  Even a paralleizable mode, like ECB does not need to be implemented in a parallelizable way.  Indeed, the simplest implementation is to continue to simply encrypt a single block at a time, so even a mode that may theoretically support encrypting multiple block simultaneously may very likely only encrypt a single block at a time in practice.

So, mode and implementation will determine how many blocks can be encrypted in parallel, not DES itself.  In the real world, you're relatively unlikely to come across actual implementations that encrypt more than a single block at a time.


Man-in-the-middle attack on Diffie-Hellman with shared public keys? Is it correct to say if the public key is known to all users beforehand,  Diffie-Hellman key exchange is not vulnerable to man in the middle attack?

Sample key exchange ( assuming all users public key is known ) :

\begin{align}
  A \rightarrow B &: Y_b^{N_a} \\
  B  \rightarrow A &: Y_a^{N_b}  \\
Shared Key  &= g^{N_a+N_b}
\end{align}

Where $N_a$ is random int generated by $A$
and $Y_a$ = $g^{S_a}$ where $S$ is the secret key generated by $A$.

Yes, for sure, you can perform what is called ephemeral-static Diffie-Hellman or static-static Diffie-Hellman where one or two parties are authenticated respectively.

Multiple schemes have been described in NIST SP 56A: Recommendation for Pair-Wise Key Establishment Schemes Using Discrete Logarithm Cryptography, sections 6.2 and 6.3.

You would of course need an additional (random) nonce if you use two static public/private key pairs. Otherwise there are no variable values in the equation and you would always generate the same session keys.

If you want to have a view of ephemeral-static Diffie Hellman then you don't have to look further than TLS 1.2, any ciphersuite that starts with DH or ECDH (without the E after it). They are not used much, generally ephemeral-ephemeral Diffie-Hellman is used with a separate authentication using RSA or ECDSA signatures. Certificates with a DH or ECDH public key are very rare indeed.

Key pair generation creates both the public and private keys and takes place on the machine of the owner of the key pair. Generally the private key should not leave this machine, except for backup purposes.

I'm not sure your sample algorithm complies with DH as specified in this standard document.


Is this a secure PRG or not? I've seen this question! from 2 years ago:

  Given $F$ is a $PRF$, we define $G$ for an input $x\in\{0,1\}^n$ as follows:

  $$G(x) = F_k(x) \oplus F_k(x \oplus 1^s)$$

The question was if $G$ is a $PRG$. I edited the question a bit to fit the answers given back then. The answers stated this isn't a $PRG$ because
$$G(x\oplus 1^n)=F_k(x\oplus 1^n)\oplus F_k(x\oplus 1^n \oplus 1^n)=F_k(x\oplus 1^n)\oplus F_k(x)=G(x)$$Now because $x$, the seed, must be random and because the adversary cannot affect the seed in any way. Why wouldn't this be a $PRG$?

For a random uniformly selected $x$ shouldn't the output of $F_k$ on input $x$ and $x\oplus 1^n$ be pseudorandom and thus $F_k(x) \oplus F_k(x \oplus 1^s)$ is also pseudorandom?

I believe you misunderstood the linked question and probably the definition of PRG.

PRG maps a key $K$ (also called seed) of bit length $l$ into a bit sequence $x\in\{0,1\}^n$ of bit length $n$. PRG is secure if the generated bit sequence $x$ is computationally indistinguishable from truly random.

What the answer to the linked question has shown is that the given PRG's output is easily distinguishable from random because two bits in fixed positions of the PRG's output are equal for any key $K$.

PS: Probably the questions like the linked one implicitly assume the following construction that creates PRG from PRF:

Suppose we have a PRF $F:K\times D \to R$ which map keys $K=\{0,1\}^l$ and domain $D=\{0,1\}^n$ into range $R=\{0,1\}^m$. Now, we can build a PRG $G: K\to \{0,1\}^{n+m}$:

$$G(k)[x]=F(k,x)$$

Note that $x$ is an argument of $F$ but not of $G$; on the LHS $x\in\{0,1\}^n$ denotes a position of a bit sequence of length $m$ in PRG output.

In the simplest case $m=1$, that is PRF $F$ outputs just one bit: $R=\{0,1\}$, and $x\in\{0,1\}^n$ denotes bit position in $G$ output.


How to solve rubix-cube like symmetric encryption So for a project at University I wrote a symmetric encryption system that was very similar to how a rubix cube would work. I had each byte of my data mapped to a element in a grid, with 6 grids in total (forming a cube), and the grids had a relationship where you could apply a swap function to each row/column and it would swap the same 4 lines in the grids on the same direction. It could encrypt up to 4 mb of data (64 x 64 grid)  at a time and used the set of moves used  in the process as the key (face 1 line 27 swap left etc.)

The catch with the system was that I haven't solved a rubix cube myleself... ever. So I managed to create a jumbled mess of my initial data and when I tried to decipher it (doing the opposite direction swap, from last swap to the first) It would remain a jumbled mess.

Due to a busted hard drive I can't show you the code I wrote for it anymore (it was in java) but I intended to try and recreate the project in my spare time And I would like to see what I could do to prevent creating a data shredder again.

Help would be greatly appreciated, I will provide additional clarifications if necessary.

EDIT: The question was Is this the correct way to solve a rubix cube (reversing the moves)? and if not what would the correct way be?

The system had more stages to it beyond this transposition stage but they were not made by and therefore worked fine :)

Is this the correct way to solve a rubix cube (reversing the moves)?

This isn't really a question about cryptography, and might be better suited for a math or even puzzling stackexchange site.

That being said, while reversing the moves is a way, and is probably the way that you would use to undo the transpositions of your cipher considering you use the ordering of moves as your key, that does not necessarily mean that given an actual Rubik's cube the solution is to invert the moves that shuffled it from the initial position.

  If not, what would the correct way be?

There apparently exist optimal algorithms for solving a traditional 3x3x3 cube in 20 steps. These don't appear to assume that you are inverting the steps that shuffled the cube. Your setup may be larger, but that still doesn't bode well for using the shuffling as some kind of cryptographic hardness assumption.


Algorithm for factoring a number $n$ of a specific form given $n$ and $\varphi(n)$ Given the natural number $n$, which is in the form $p^2 \cdot q^2$ with $p$,$q$ prime numbers. Also $\varphi(n)$ is given. Describe a fast algorithm (polynomial time) that calculates $p$ and $q$. Apply your algorithm to calculate $p$ and $q$ when $n=34969$ and $\varphi(n)=29920$.

I found this problem on a mathematical competition on cryptography. I  tried to find a solution alone and on the internet and I didn't succeed anywhere, can we find a solution?

The (in my opinion) simplest way to proceed about this is:
First compute the square root $m:=\sqrt n$ of $n$ in $\mathbb N$; this can, for instance, be done in time $\mathcal O(\log^3n)$ using a binary search.

The next step is to compute $\varphi(m)$ from $\varphi(n)$: by the properties of $\varphi$ we have
$$\varphi(n) = (p-1)p(q-1)q=\varphi(m)\cdot m \text,$$
hence $\varphi(m)=\varphi(n)/m$.

Now you can apply the standard method to compute $p$ and $q$ from $m$ and $\varphi(m)$, as described in Dan Boneh's paper (proof of fact 1). Note that in the linked paper, one is assumed to be given a tuple $(m,e,d)$ with $ed\equiv1\pmod{\varphi(m)}$, but that's not actually necessary: choosing $k$ as any non-zero multiple of $\varphi(m)$ is sufficient.


Hashing login and password? For a login the user credentials are typically some form of "username" and a matching "password".

The password is (hopefully) stored as a hash in the database.

But what about the username?

Is the username stored as a plaintext in the database?

Would it be a good idea to hash both the username and the password?

If username was treated as the password should be, like salad (salt, pepper, hash, toss / en Français saler, poivrer, hacher, touiller), then

If there is salt, it can't be directly inferred from username. And the alternatives are getting rid of salt (allowing pre-computation and rainbow tables), or test all users (which is going to be prohibitively costly for more than a few users).
If the username doubles as storage of the email, then we can no longer readily send an email to all users. And if we can send such general email, there is the risk that likely usernames can be inferred from email.
Username is even more guessable than password, and (unless treated as an extension of password) if can be found even more easily.

For these reasons, it is typically functionally unacceptable to apply a password hash to username.


What's the functional difference between fountain codes and polynomial secret sharing? Fountain codes, as I understand it, allow for the reconstruction of a set of data (e.g. a 64-bit word), by sending (without corruption or failure) chunks of data generated using a probabilistic function, with the benefit that due to an unlimited supply of chunks being sent over an unreliable channel, as long as the threshold of successfully send chunks are received (e.g. more than 64-bits of encoded data), the client can reconstruct the data without having knowledge of packet loss.

Polynomial secret sharing splits a piece of data into multiple shares, such that if the minimum threshold of shares is provided, the data can be reconstructed. An unlimited amount of shares can be generated. This could be used, for example, to split a secret to multiple locations to provide redundancy and/or security.

The actual implementations of these algorithms are different, but how are they functionally different? Why can't one be interchanged for another?

Consider what happens when we construct Shamir's secret sharing scheme for a secret $s$ and a reconstruction threshold $t=4$.  Our polynomial will be of degree $t - 1$ with $a_i$ being random coefficients:

$$
f(x) = s + a_1x + a_2x^2 + a_3x^3
$$

The shares for the $n$ players are given by $f(1), f(2), \dots f(n)$.  Any $t \ge 4$ of the players can reconstruct the polynomial $f(x)$ and can  recover the secret as $s = f(0)$, but any $t < 4$ of the players do not have enough information and thus learn nothing about the secret $s$.

We can use this exact same technique as a fountain code through nothing more than a change in perspective.  Instead of a secret $s$, we have a message $m$:

$$
g(x) = m + a_1x + a_2x^2 + a_3x^3
$$

And instead of giving each player $n$ the share $f(n)$, we broadcast a series of blocks $g(1), g(2), \dots$ to the players.  Once a player has received $t \ge 4$ message blocks, they have enough information to reconstruct the polynomial $g(x)$ and can recover the original message as $m = g(0)$.  By choosing a large enough finite field, it is possible to generate a very large number of unique message blocks.

Practical fountain codes are usually based on low-density parity codes for reasons of efficiency, but I hope this example helps to show that in many ways error-correcting codes and secret-sharing schemes are merely two interpretations of the same underlying concept.


how to compute IV with AES CTR if key, plaintext and ciphertext are known? Given $E_k$, which a block-cipher using the (known) key $k$, and a plaintext-ciphertext pair $(p,c)$ where $c$ is the encryption of $p$ using CTR mode, can the initialization vector be recovered using $IV = E_k^{-1}(c \oplus p)$?

Correct.

Note that normally we use the term nonce rather than IV, because the only requirement for the nonce is that it never be repeated, while an IV (e.g., for CBC) must additionally be unpredictable in advance.  Also usually you encrypt multiple 128-blocks in a single message by using E(nonce || 0, K), E(nonce || 1, K), E(nonce || 2, K), etc., as the pad, so you might get a nonce and a block counter.


A good book on lattices I have recently started studying lattices. The book that I am following is "Complexity of lattice problem by Shafi Goldwasser and Daniele micciancio" but it is too much inclined towards computational complexity and problems.

Can someone refer a good book from cypto perspectives and easy to understand and grasp the concepts?

I recommend Chris Peikert's survey, called A Decade of Lattice Cryptography.


Function to derive an integer from a given password I need to get an int, derived by a given password, to feed it to a deterministic PRNG as a seed. The derived int should not give away any clues about the password.

How can I achieve this without getting too many collisions? (Because the integers are derived from a string that is much larger, I suspect that there will be many possible collisions, yet I want to minimize the chance of their occurrence.)

I have tried a few solutions and my current function strikes me as being too kludgy.

Here is the pseudocode of what I am doing right now:

password := getPasswordFromUser()
salt_len := 16
salt := getRandomBytes(salt_len)
// the password and salt is then put through a Key Derivation
// function. The key will be used for encryption.

// Here comes the part I have trouble with; to "randomize" the
// order in which the data will be stored, I am using a deterministic
// PRNG, which is seeded as follows:

// Create a long string that contains the password:
orderPasswd := password + "abcdefghijklmnopqrstuvwxyz" +
    "1234567890ABCDEFGHIJKLMNOPQRSTUVWXYZ.,;:#+!§$%&/()=?"
// Create a sha256 sum of this string, feed it to the
// deterministic PRNG as seed and shuffle the string:
orderPwHash := sha256sum(orderPasswd)
// derive an int from the hash by converting it
orderPwSeed := int64(binary.BigEndian.Uint64(orderPwHash))
// shuffle orderPasswd using the Fisher-Yates shuffle algorithm
orderPasswd = shuffle(orderPasswd, orderPwSeed)
// Put orderPasswd through the KDF, hash the key and shuffle
// the order with an integer derived from the hash:
orderKey := getKey(string(orderPasswd[salt_len:]),
            orderPasswd[:salt_len])
orderKeyHash := sha256sum(orderKey)

// convert that hash to an integer to finally get the seed
// that will be used to determine the order
orderSeed := int64(binary.BigEndian.Uint64(orderKeyHash))

// seed the PRNG with orderSeed... shuffle the order...

Edit:

I have accepted Ilmari Karonen's answer, because he put a lot of effort into it and it contains vital information for anyone trying to implement cryptography.

I have dismissed the idea of shuffling the message, as it would unnecessarily complicate my code and increase the likeliness of mistakes without adding to the security, which is especially bad in this context.

Because the message, once encrypted with AES256 and a key derived with scrypt set with N=65536 and p=2, will look like random noise, this ought to be sufficient.

If you have access to a PBKDF2 implementation, I'd just take a 8 byte output of PBKDF2. Whether that's a Little Endian or Big Endian value doesn't matter so long as you're consistent.

Since PBKDF2 has good spread, a 64-bit capture from it gets a 50% chance of collision around the 5.1 billionth different input, still down at 1% around 600 million.  (See the table on Birthday Attack.)


Generating a SHA256 pkcs1v1.5 Blind RSA Signature using Chaum's Blind Signature Scheme I am a noob to cryptography in the sense that I have very less understanding as to how RSA encryption schemes work in practice. However I do understand the theoretical foundations of RSA cryptography and also Chaum's Blind Signature scheme as described in the wikipedia article on RSA Blind Signatrures.
I did find an implementation of this scheme that I can use successfully to blindly sign using vanilla RSA.
However my problem is as follows: I need to be able to generate a SHA256 pkcs1v1.5 RSA signature based on the same blinding scheme described in the article I linked to before.
I understand that RSA Blind Signatures are less secure in general. However I do not intend to use the same keypair for encryption.
I have read up a little on pkcs1v1.5 RSA signatures and from what I could gather, they use 'padding', in addition to some other techniques to make RSA more viable.
The pkcs1v1.5 specification has a comment that states

Note.  Another way to implement the signature verification operation
is to apply a "decoding" operation (not specified in this document)
to the encoded message to recover the underlying hash value, and then
to compare it to a newly computed hash value.  This has the advantage
that it requires less intermediate storage (two hash values rather
than two encoded messages), but the disadvantage that it requires
additional code.

I am aware of this post that details that this is possible if the sender, or the 'Signee' does the padding before sending the message to be signed. On similar lines, what kind of padding and other methods do I have to employ in order to generate a pkcs1v1.5 Signature, so that any third party, knowing only N and E can verify this Signature using the normal method or the 'decoding method' quoted above?

I can't believe it but I actually found an answer.
The following js code does exactly the padding scheme as detailed in the EMSA-PKCS1-v1.5 message encoding specification
function messageToEMSA_PKCS1_v1_5(message){
    // https://tools.ietf.org/html/rfc3447#section-9.2
    SHA256_DIGEST_INFO = "30" + "31" + "30" + "0d" + "06" + "09" + "60" + "86" + "48" + "01" + "65" + "03" + "04" + "02" + "01" + "05" + "00" + "04" + "20" ;
    T = SHA256_DIGEST_INFO + sha256(message);
    t_len = 51; // Just T.length 19 octets from the Digest Info + 32 octets from SHA-256

    ps_len = 256 - t_len - 3;
    PS = "ff".repeat(ps_len);

    EM = "00" + "01" + PS + "00" + T;
    console.log(`EMSA-PKCS1-v1_5 encoded Message: ${EM}`);
    return EM;
}

Following this, the blind signature after being unblinded, would be a valid pkcs1v1.5 signature


How is Cross-Certification implemented? I am currently learning about Certificates in Public Key Infrastructure.

  Cross-Certification exists as an alternative because the concept of a single monolithic CA certifying every possible user in the world is quite unlikely.
  Cross Certification are issued by CA's to create Non hierarchical trust path.

It works on the concept that every root CA has cross certified each other. But how is that even possible?

It is stated that almost every country has it's own root CA (in an abstract way). And there exists a lot of countries in the world, then how can all of them cross certify each other?

For Example, the concept of Cross Certification is explained by showing how the root CA of England cross certifies the root CA of Africa. And then Alice living in England can verify the chain of trust of a Bob living in Africa. Stating, that Technically this would mean that Alice's root CA has obtained a certificate or itself from Bob's root CA and vice versa.

This method seems feasible when the number of CA's are limited (like CA of England and japan). But how could this scale up to a large number of CA's(CA of every country)?

In practice Cross Certification is rare, instead, certificate consumers trust multiple CAs. For example, Mozilla includes 154 different trusted CAs by default with their browser.

As to the process of cross-certification, it involves a CA signing other CA's public key. It can be one-way or cross-certified.