Question about IETF RFC6979 determinisitc (EC)DSA document section 3.6 additional data k' In RFC6979 document
https://tools.ietf.org/html/rfc6979
page 14~15, Section 3.6 "Variants"

o. Additional data may be added to the input of HMAC, concatenated
after bits2octets(H(m)):
    K = HMAC_K(V || 0x00 || int2octets(x) || bits2octets(h1) || k')

 ...  In [SP800-90A] terminology, k' is the "additional
 input" that can be set as a parameter when generating pseudorandom
 bits.

The line

K = HMAC_K(V || 0x00 || int2octets(x) || bits2octets(h1) || k')

appears to be from step d in section 3.2 "Generation of k".
Q1:  Additional data k' is concatenated after bits2octets(H(m)) in HMAC input in step d.
May we also need to concatenate k' after bits2octets(H(m)) in HMAC input in step f?
ie step f becomes
K = HMAC_K(V || 0x01 || int2octets(x) || bits2octets(h1) || k')

Q2: As said

SP800-90A terminology, k' is the "additional input"

In SP800-90Ar1 document
https://nvlpubs.nist.gov/nistpubs/SpecialPublications/NIST.SP.800-90Ar1.pdf
section 10.1.2.3 "Instantiation of HMAC_DRBG",
there is no "additional input" in "HMAC_DRBG Instantiate Process" but
k' appears to be passed as "personalization_string" as in SP800-90Ar1 section 10.1.2.3.
If k' is used as "personalization_string", then in Q1, we may also concatenate k' after bits2octets(H(m)) in HMAC input in step f, no?
Q3:

SP800-90A terminology, k' is the "additional input"

In SP800-90Ar1 document section 10.1.2.5 "Generating Pseudorandom Bits Using HMAC_DRBG",
there is an "additional_input" argument.
Is the "additional input" in RFC6979 document section 3.6 referred to the "additional_input" in
SP800-90Ar1 document section 10.1.2.5?
If so, may we need to pass additional data k' as "additional_input" also to "HMAC_DRBG_Generate Process",
ie in RFC6979 section 3.2. step h.1~h.3?
Presumably as a result, RFC6979 section 3.2. step h may become:
Inserting a new step before step h.1:
(K, V) = HMAC_DRBG_Update(k', K, V);  //step 2 of "HMAC_DRBG_Generate Process"

and the later half of step h.3 may be modified, if k is rejected and generating a new k is needed,
the original process appears to be step 6 of "HMAC_DRBG_Generate Process":
(K, V) = HMAC_DRBG_Update(null, K, V)
ie
    K = HMAC_K(V || 0x00)
    V = HMAC_K(V)

may become
(K, V) = HMAC_DRBG_Update(k', K, V)
ie
K = HMAC_K(V || 0x00 || k')
V = HMAC_K(V)
K = HMAC_K(V || 0x01 || k')
V = HMAC_K(V)

as later half of step h.3.
May such modifications be needed?

I had emailed Dr Thomas Pornin the very same question and received his reply. With his permission I cross post his answer as followed

From: "Thomas Pornin" ...
Date: 2021/04/22 11:38

Q1:  Additional data k' is concatenated after bits2octets(H(m)) in HMAC
input in step d.
May we also need to concatenate k' after bits2octets(H(m)) in HMAC input
in step f?

There is no real "need" here. Section 3.6 lists (but does not formally
specify) possible variants of the mechanism described in RFC 6979; these
variants are, emphatically, NOT the "true" RFC 6979 mechanism (section
3.6 says as much) and, in particular, do not match the test vectors
contained in the RFC. However, they all make sense, cryptographically
speaking, and thus can be considered in some specific contexts.
The process described in RFC 6979 has been designed to reuse as most as
possible the definition of HMAC_DRBG from NIST SP800-90A, with the
avowed goal of being able to rely on existing security analysis of that
specific construction. Note that HMAC_DRBG is still, as defined by NIST,
a random generator that expects to work along with a seed generator. The
context of RFC 6979 is outside of the scope of HMAC_DRBG; thus, whatever
we do, we cannot really claim to be using HMAC_DRBG in a formal sense;
we can only claim that we use a construction for which existing
cryptographic analysis also applies to the case of deterministic DSA and
ECDSA signatures (see references from section 4).
Thus, in that context, there is no real notion of "correct" or
"incorrect" variant. If injecting some additional input (k') into the
first HMAC call (step 3.2.d), you may or may not also inject the same
additional input into the third HMAC call (step 3.2.f). Both variants
work and "make sense" (neither seems more secure or less secure than the
other). Neither variant matches the RFC 6979 test vectors; this does not
compromise interoperability (in all of this, interoperability is about
generating signatures that are acceptable to unaware verifiers), but it
is out of the scope of RFC 6979. It is a case of "yeah, sure, you can".
Section 3.6 merely points out that having additional input (k') injected
into HMAC_DRBG maps to construction elements in NIST SP800-90A which are
designated as "additional_input" in the process on page 48 of that
document (page 47 in the 2015 revision of SP800-90A, but RFC 6979 dates
from before 2015), so that variant is not something absurd or unheard
of.
--Thomas Pornin

So I'd guessed that the term "additional input" in RFC6979 doc 3.6 (page 14 the last line ~ page 15 the first line) is not the term "additional_input" (used in generating and reseeding) in NIST.SP.800-90Ar1 doc 10.1.2.5 (page 47) in exact sense.  Nor is it the term "additional entropy" (used in instantiation) in NIST.SP.800-90Ar1 doc. It just means "additional" (extra, more) data.  We may or may not use k' as "additional entropy" or "additional input" in HMAC_DRBG instantiation or generating.


Can we build two messages with same MD5 but different size? Can we build two messages with same MD5 but different size?
I researched MD5 collisions, but everything I found targets messages of the same size.

This answer was moved following closing of the question.


A strange phenomenon of the composition of permutations of order 2 Suppose that $f,g,h:X\rightarrow X$ are permutations such that $f^{2}=g^{2}=\textrm{Id}_{X}$ (i.e. $f,g$ have order 2). Let
$F=f\circ g$. Let $D_{f,g}$ be the distribution that takes the value $n$ where $n$ is the least positive integer such that $F^{n}(x_{0})=x_{0}$ for randomly chosen $x_{0}$.

So if $f,g$ are chosen at random, then the expected value $E(D_{f,g})$ has order around $|X|$ with high probability. However, in my experience, if $f,g$ are not chosen randomly and they have some sort of relation to each other, then $E(D_{f,g})$ often falls very close to either $\sqrt{|X|},2\sqrt{|X|},4\sqrt{|X|},\frac{4}{3}\sqrt{|X|}$. Furthermore, if $f_{1},g_{1},f_{2},g_{2}$ are all closely related in some mysterious way, then
$$\frac{E(D_{f_{1},g_{1}})}{E(D_{f_{2},g_{2}})}$$ is typically very close to $1$.

For example, suppose that $X=\{0,1\}^{n}\times\{0,1\}^{n}$ and $R,S:\{0,1\}^{n}\rightarrow\{0,1\}^{n}$ are randomly selected functions. Let $f(x,y)=(x,y\oplus R(x)),g(x,y)=(x\oplus S(y),y)$. Then $f,g$ are permutations of order 2 which are related and where $E(D_{f,g})$ is typically around $2^{n}$ (The phenomenon holds even when the relation between $f$ and $g$ is more complicated. It is hard to tell when the phenomenon will hold though).

What is the mathematical explanation for this phenomenon?
Is there any way to predict $E(D_{f,g})$ when $f,g$ have a simple description and are easy to compute?
I am wondering if this phenomenon could cause an insecurity in a symmetric cryptosystem that is constructed from permutations of order two. For example, suppose that $f,g$ are closely related permutations of order two, and suppose $h$ is another permutation of order 2. Let $\ell_{0}=f\circ g$ and $\ell_{1}=f\circ g\circ h$. Suppose that for an expanded key $a_{0}\dots a_{n-1}$, the block encryption function is $$E_{a_{0}\dots a_{n-1}}=\ell_{a_{n-1}}\circ...\circ \ell_{a_{0}}.$$
Then could there be any cryptographic weakness from the block encryption function $E$? In particular, could there be any security weakness that arises from a cryptographic hash function that arises from the Matyas–Meyer–Oseas construction from the encryption function $E$? Should I be suspicious of a possible weakness of cryptosystems of this form?

So it turns out that there is nothing strange about the composition of random permutations of order 2. The thing is that the distribution of the size of the orbit of an element under the operation $g\circ f$ where $f,g$ are involutions strongly depends on the number of fixed points the functions $f,g$ and if $f$ or $g$ have large quantities of fixed points, then $g\circ f$ has small orbits.

When computing the iterates $(f\circ g)^{k}(x)$, when one encounters a fixed point of the function $f$ or of the function $g$ before going back to $x$, one begins to uncompute the iterates $(f\circ g)^{k}(x)$. After one uncomputes the iterates $(f\circ g)^{k}(x)$, one eventually uncomputes back to $x$, and at this point, one starts computing $(f\circ g)^{-k}(x)$. When computing $(f\circ g)^{-k}(x)$, one eventually encounters another fixed point of the function $f$ or of the function $g$. At this point, one reverses the direction of computation until one returns to $x$ in a complete orbit. The amount of time it takes to find the first fixed point follows an exponential distribution, and the amount of time it takes to find the second fixed point after crossing $x$ also follows an exponential distribution with the same parameter. Therefore, the amount of time it takes to make a complete orbit will be $X+X$ for some exponential distribution $X$. The probability density function of $X+X$ is $xe^{-x}$ up to renormalization however.

Observe that every permutation can be written as the composition of two involutions. However, some permutations have a much higher probability of arising as the composition of two involutions than other permutations.

Suppose $1\leq r\leq k$. If $h:[k]\rightarrow[k]$ is a random permutation, then the probability that the size of the orbit with respect to $h$ of a random element $x$ is $r$ is precisely $\frac{1}{k}$. Suppose that $f,g:[2k]\rightarrow[2k]$ are permutations selected at random subject to the condition that $f,g$ have no fixed points. Then let
$P_{k,r}$ denote the probability that the orbit with respect to $g\circ f$ of a random element $x\in[2k]$ has cardinality $2r$. Then, after one performs an exact computation of $P_{k,r}$, by taking a limit, one obtains $\lim_{n\rightarrow\infty}n\cdot P_{n,\lfloor nx\rfloor}=\frac{1}{2\sqrt{1-x}}$ for all $x\in(0,1)$ (in other words, $x$ probably has a very large orbit).

Now suppose that $f,g:[k]\rightarrow[k]$ are randomly selected permutations subject to the conditions that $\{x\in[k]|f(x)\neq x\}=2m,\{x\in[k]|g(x)\neq x\}=2n$. Then let $P_{m,n,k,r}$ denote the probability that the orbit of a random element has length $r$.

Then for $x>0$, we have $\frac{k\cdot P_{n,n,k,v}}{k-2n}\rightarrow xe^{-x}$ as $v\cdot\frac{k-2n}{k}\rightarrow x,k\rightarrow\infty,v\rightarrow\infty$. (I may probably give more details as to why this is the case later on).

Now, take note that the expected value of the distribution with probability density function $x\cdot e^{-x}$ is $2$. Therefore, the expected value of the size of the orbit of a random element approaches $\frac{2k}{k-2n}$. In the scenario outlined in the question, the functions $f,g$ typically have $O(\sqrt{|X|})$ many fixed points which would ensure that there are around $\frac{2k}{k-2n}$ many fixed points.


Shor's algorithm for elliptic curve discrete logarithm problem Could someone write Shor's algorithm for solving the discrete logarithm problem and how it could apply to elliptic curves in a few, easy to understand steps? I have a basic understanding of quantum computing, but not enough to understand his paper.

Could one adapt Shor's algorithm to solve the DLP?  Yes: Shor's original paper (arXiv preprint) explains how, in §6 on p. 321.

Could one adapt Shor's algorithm to solve the ECDLP?  Yes.  Researchers at Microsoft recently published estimates for how big a quantum computer you would need to do so.  (Spoiler: Smaller than RSA at comparable classical security levels.)

Could one write down how it works in a few easy-to-understand steps?  Maybe, but that's above my pay grade at the moment if you find those two papers to obscure!  You might start with Scott Aaronson's article on Shor's algorithm, see if you can find the hidden subgroup problem hidden in the algorithm, and adapt it to the hidden subgroup problem in discrete logs.


CBC-MAC 8 octet ICV compatable with 16 octet block size? I'm trying to use DTLS in Preshared key mode for CoAP which necessitates using CipherSuite TLS_PSK_WITH_AES_128_CCM_8

I'm trying to start with the CBC-MAC but I'm not sure how to get an 8 octet ICV out of it?

Do I just truncate the output and only use the first 8 octets?

Do I use an 8 octet block size instead of the 16 imposed by the CBC function I'm using for hardware acceleration?

const unsigned char k[16] ="lbsHgUDHKgeinLfU";//key 128bits

const unsigned char message[16] = "Hello world!  ";//multiple of 16 bytes as required
unsigned int mLen = sizeof(message);//16

unsigned char zeroInit[16]= {0};

//CBC-MAC with 8byte ICV
//uint8_t mac[8];//8 octet ICV (hopefully)
uint8_t mac[16];

esp_aes_crypt_cbc( &c,ESP_AES_ENCRYPT,mLen,zeroInit, message, mac);

and the output I get is:
ad  ea  26  07  25  bb  43  8a  85  b5  ec  ca  6c  b6  b5  d3

The only difference I see with an array size of 8  is that I only see the first 8 bytes.

In general the authentication tag size is indeed generated by simply using the first (leftmost, in most byte array representation) bits. In general Tlen - the length of the tag - is supposed to be a multiple of eight, so a tag size of 64 bits results in the leftmost 8 bytes.

You cannot just change the block size of a block cipher. AES is only supporting a 128 bit / 16 byte block size (although Rijndael supports any block size between 128 and 256 bits inclusive using 32 bit increments). So changing the block size of a cipher is generally out of the question.

The usage of just the first/leftmost bytes out of the full MAC output is so widespread that an AEAD API interface that I wrote based the method signatures on the fact. Note that the output of a MAC is indistinguishable from random anyway, so in principle you can use any bits of the result; using the first/leftmost bytes is however the commonly agreed default.

If unsure: read the standard, NIST SP-800 38C:

  Set $T=\operatorname{MSB}_{Tlen}(Y_r)$

and

  $\operatorname{MSB}_s(X)$ : The bit string consisting of the $s$ left-most bits of the bit string $X$.


Research topics related to cryptography and Hamiltonian cycles I am very interested in pursuing a research where I can show an application of Hamiltonian cycles in Cayley graphs of some group such as reflection groups to the field of cryptography.

But currently I can't figure out where the existence of such a cycle will become important in cryptography and how to develop any useful finding as research output.

Can anyone suggest me an idea to start? An approach?

Thanks a lot in advance.

Cycles (not necessarily Hamiltonian) in the Cayley graph correspond to relations among generators of the group. The RSA assumption can be written as "It is computationally difficult to find a non-trivial relation in the RSA group $(\mathbb{Z}/pq\mathbb{Z})^*$", which is a property of $(\mathbb{Z}/pq\mathbb{Z})^*$ known as being "pseudo-free" (see The RSA Group is Pseudo-Free), so the computational complexity of finding cycles in the cayley graph can be connected to more standard cryptographic assumptions via this notion.

If one wants to force this point of view, you can see the sieving step of index calculus attacks (on both factoring and discrete log) as finding relations in between group generators (this is the standard notion), so finding cycles in the cayley graph of certain groups. While the discrete log problem is defined over a cyclic group (who's cayley graph is simply a $n$-gon), it's not clear to me what particular cayley graph one would be finding cycles in.
In particular, for the discrete log problem you fix a "factor base" of various different generators of the group, and then find relations between their discrete logarithms (with respect to a fixed generator), so the cayley graph does not appear to be just that of a cyclic group (which only has a single generator).

Neither of these deal with Hamiltonian cycles though, and one doesn't need the cycles to be Hamiltonian for the problem to be difficult.


Black-Box Zero Knowledge vs Non-Black-Box Zero Knowledge I'm confused about the definitions of black-box zero knowledge and non-black-box zero knowledge. I have searched and found explanations but still a bit confused about it. From the context, their definition (with auxiliary input) of black-box zero knowledge proof system between the prover $P$ and (malicious) verifier $V^*$ can be described as follows:

$\{\langle P(\omega), V^*(z)(x)\rangle\}_{(x,\omega) \in R, z \in \{0,1\}^{p(|x|)}}$

and $\{S^{V^*(z,x,\cdot)}(x)\}_{(x,\omega) \in R, z \in \{0,1\}^{p(|x|)}}$

are (perfectly/statistically/computationally) indistinguishable, Where $S$ is a simulator which has access to a oracle function $V^*(z,x,\cdot)$

In my opinion, the only difference between the definition of non-black-box zero knowledge and the definition of black-box zero knowledge is that non-black-box zero knowledge allows that for all $V^*$ there exists unbounded simulator $S$, is this correct?

The difference is to do with the quantifiers on the simulator. Non black-box zero-knowledge says that for all verifiers, there exists a simulator that can simulate a proof of all statements (i.e. there can be one simulator per verifier). Black-box zero knowledge says that there exists a simulator that can simulate a proof of all statements over all verifiers (i.e. there is one simulator total). Therefore, black-box zero-knowledge is the stronger definition of security.

Reference: Lysyanskaya, 2002 (page 31) https://dspace.mit.edu/handle/1721.1/29271


RC4 S-Box and Keystream I'm studying the RC4 algorithm and I have the following questions:

On all questions assume that an expanded (2048-bit) key is used, and that the first 4096 bytes of the KeystreamIm are discarded.

After the above process, is the resulting S-box indistinguishable from a random permutation of the numbers 0 through 255?

Assuming the above process, are the bytes generated indistinguishable from random data?

As for your first question "is the S-box indistinguishable from a random permutation?", well, there are likely some subtle biases.  For one, we know that, after exactly 4096 steps, the combination $j=1$ and $SBox[1] = 1$ is impossible; that's because $i=0$ after 4096 steps, and the combination $j=i+1$ and $SBox[j]=1$ is known to be impossible (given the standard RC4 key setup; this was first observed by Hal Finney).  Because of this, there is likely a bias away from $SBox[1] = 1$ after exactly 4096 steps, and so this would appear likely to be a distinguisher (albeit not a strong one) from a random permutation.

As for your second question "are the bytes generated indistinguishable from random data?", the answer for that is "definitely not".  We know how to distinguish a roughly Gigabyte output of RC4 from a random stream; see this paper for the details; note that discarding an arbitrary amount of RC4 keystream before you start sampling does not affect this attack.


dealing with real numbers in Integer Vector Homomorphic Encryption lib I am using Integer Vector Homomorphic Encryption for the encryption lib.

I have to multiply a learning rate of 0.01 (i.e. between 0 and 1) by the encrypted data (vector) but it is not integer. I had wanted to multiply by 1/10 instead. Is it possible? because it is know that HE scheme doesn't support division. Is the any way out?

There are several ways...

If the message space of your scheme is $\mathbb{Z}_t$, then you can

Multiply all the plaintexts by $10^k$ before encrypting them and instead of multiply those vectors by a learning rating between $0$ and $1$, multiply them by an integer learning rate between $0$ and $10^k$.
Remove the divisions and track the changes introduced by this remotion. For instance, instead of evaluate $x = \frac{c_0 + c_1}{10}$, do $y = c_0 + c_1$ and keep in mind that $y = 10x$ so you can find the right answer after decrypting. Take a look to the section 3.2 (Division-Free Integer Algorithms for Classification) of this paper...

But if the message space of the scheme you are using is (let's say) more robust, like a polynomial ring, then you can encode double values into plaintexts, which enables you to encode the learning rate, then encrypt it and finally multiply by the vector of ciphertexts.

That answer may be helpful to you.


Symmetric cipher speed (AES vs Camellia vs Twofish) If I have understood correctly, Twofish is more secure (harder to break) than AES and Camellia, but it's slower than both.

How can I measure the speed difference between AES vs Twofish and Camellia vs Twofish? Does Twofish use twice as much time? Half as much time? Or does it just take a few percent longer to encrypt/decrypt than AES/Camellia?

I'm in the starting/planning phase of software development: the local stored data will be encrypted, and the data to be transmitted over a network will be encrypted/signed. I would like to use Twofish as the symmetric cipher, but if it uses twice the resources of AES/Camellia, then it's not a good idea.

Just use AES. It's hardware-accelerated and implementations have had ages to have flaws discovered and patched. More strongly, just use GPG to encrypt data at rest and just use TLS (>= 1.2, with appropriate AEAD ciphers) for data in motion. "If you're typing the letters A-E-S into your code, you're doing it wrong."

Anything you build yourself is infinitely more likely to be broken as a result of your design choices than by your choice of cipher.


CBC Mode error during encryption In CBC mode I know that if i get a corrupted Ci* block than Pi and Pi+1 will be wrong during the decryption, but i believe that this happens only when Ci* is not envolved during the feedback stage at the encryption, my question is what happens if the corrupted block is a feedback at the encryption stage, will it have the same impact as before?

As you can see in the Wikipedia article a ciphertext block is used for two different things during decryption:

as input to the block cipher to calculate the output, which is then XOR'ed with the previous ciphertext block to create the corresponding plaintext block at the same position;
as input to the XOR to calculate the next plaintext block, together with the next decrypted block.

You can see it clearly in the picture, by following the arrows of one of the ciphertext blocks:

(XOR is denoted by $\oplus$ )

As the block cipher is a pseudo random permutation the plaintext block at the same position is indistinguishable from random even if only one bit is changed. The fact that it is XOR'ed with the value of the previous ciphertext block does not change this fact. There is only one restriction: the result is not identical to the plaintext block that would be calculated without the change.

Things are different with the next plaintext block. Only those bits that have flipped in the ciphertext block will be flipped in the next plaintext block. So the change is localized and not random.

Next or previous blocks are not affected as the affected ciphertext block, intermediate values or plaintext blocks are not used as input anywhere else.


AES VS PRNG+HASH+XOR I was thinking of doing symmetric encryption using just hashing and simple XOR encryption. It would work as:

Alice and Bob share a symmetric key
Alice manages to send an (authenticated) IV to Bob
Bob and Alice both combine the IV with the symmetric key and use it to seed a PRNG
the output of the PRNG is hashed (SHA256)
whenever a message needs to be sent, the data is XORed with the hashed PRNG output

Are there any serious issues with this approach? If indeed there aren't any, why would one use a SHA256/AES combo with 2 points of failure instead of just relying on the existence of one way functions like SHA256? Why use AES at all?

It is possible to turn a hash function into a stream cipher; there are several methods for that, and the simplest is to compute $h(K||IV||x)$ for hash function $h$, initialization vector $IV$, and successive values of a counter $x$. This yields an arbitrarily long sequence of pseudo-random blocks (32 bytes per invocation if $h$ is SHA-256). Then XOR that stream with the data to encrypt or decrypt.

We don't usually do that for two main reasons:

Security of the scheme is not that easy to characterize. A "secure" hash function (resistant to collisions and preimages) will not necessarily imply a secure stream cipher that way. (Very) roughly speaking, the stream cipher is secure if the hash function behaves like a random oracle.
Performance sucks. Hash function are efficient at processing a lot of input data, not at generating a lot of output data.

It is of course quite tempting to have a unique primitive diversified into multiple usages; it would save space in code. However, in embedded systems where ROM size is at a premium (in particular smart cards), CPU power and RAM are even more scarce, and AES performs better than SHA-256 along these metrics.

Sponge hash functions, like the upcoming SHA-3 (Keccak), have an internal structure which is kind-of "reversible", meaning that they are good at input and at output. A Keccak core should allow both secure hashing and efficient pseudo-random generation (i.e. encryption, with a XOR).

Conversely, authenticated encryption modes like GCM use a block cipher for both encryption and integrity, the latter replacing what would have been classically done with a hash function (with HMAC).


does CFB support random read access? According to Wikipedia block cipher modes of operation, simplified CFB supports random read access. but what about the real CFB where we have a shift register? below are pictures extracted from the book "Cryptography and Network Security by William Stallings" for CFB.

And

Does it support random read access? if yes, how?

Yes, with some more ciphertext.
The CFB mode encryption equations;
\begin{align}
I_0 &= \text{IV}\\
I_i &= \big((I_{i-1} \ll s) + C_i\big) \bmod 2^b,\\
C_i &= \operatorname{MSB}_s\big(E_K(I_{i-1})\big) \oplus P_i\\
\end{align}
and decryption equations;
\begin{align}
I_0 &= \text{IV}\\
I_i &= \big((I_{i-1} \ll s) + C_i\big) \bmod 2^b,\\
P_i &= \operatorname{MSB}_s\big(E_K(I_{i-1})\big) \oplus C_i\\
\end{align}
As you can see, to read one value one needs more than one ciphertext and that is defined by the CFB mode is used. NIST has CFB-1, CFB-8, and CFB-128. The $s$ in the CFB-$s$ represents the encryption size per block cipher encryption/decryption.

CFB-1 needs to read 129 ciphertexts block, one can be IV, to decrypt one block
CFB-8 needs 9 to read 129 ciphertexts block, one can be IV, to decrypt one block
CFB-128 needs 2 to read 129 ciphertexts block, one can be IV, to decrypt one block

The good is that if you read sequentially then the need is not linear, for example, 2 sequential ciphertext blocks will need only 3 on CFB-128, 10 in CFB-8, and 120 in CFB-1.
Actually, even in the reduced sizes like CFB-1, this is not really a problem, since the 128 ciphertexts are bits and that is only two reads if the data can be access 128-bit per reading. The memories can handle this and harddisk has wider read access. This, however, has a drawback on the decryption time. AES-CFB-1 needs 128 decryptions, AES-CFB-8 needs 16 decryptions.
Note that we don't use CFB or CTR on-disk encryption, we rather prefer XTS or XEX modes.


Cryptographic Challenge: How to Say Something Confidentially to Snowden? The Snowden situation raises an intereting cryptograpic problem. At present, how can something be sent confidentially to Snowden?

Claim:

I have no particular political orientation. The above question is merely a cryptographic challenge. The meta assumption is…

You trust someone, denoted as Snowden, but Snowden does not trust anyone and you do not know any further information about Snowden, except his name or identity.
You should be careful that someone, say FBI, might impersonate Snowden to you.

Objective:

How to build a global and secure communication channel between you and Snowden from scratch, without resorting to trusting any third party?
Snowden does not trust anyone at the beginning, but he wants to find someone whom he can trust, via the secure channel built (if possible) in Step 1. How is this done?

Is this possible to do by using cryptography?

For convenience, let us call this challenge the Snowden challenge. How do we model the security objectives for Snowden and you?

Generate a file of cryptographically strong random data at least as long as the message to be sent.  This will allow communicating the secret using the random data as a one-time-pad. I.e., produce the ciphertext by using a bit-by-bit combining function such as XOR.
Purchase a plane ticket for an international flight connecting through Sheremetyevo airport.
Burn a copy of the OTP data onto a CD-ROM. Label it "Lady Gaga" and lock it in a briefcase handcuffed to yourself.
Take the flight. During your layover, locate Snowden in the international travel area.
Whisper the secret to Snowden.
Both of you then giggle loudly something about Lady Gaga.
Drop the CD-ROM in the trash so the spooks don't have to report home empty-handed.
(Optional) exchange public keys with Snowden to secure your future communications.

EDIT: OK, I felt bad about leaving a response that might be interpreted as just trolling. But in all seriousness, this is a classic identity bootstrapping problem.

Once we have identity authentication worked out, message integrity and confidentiality are basically solved by standard encryption systems. There's no magic bullet for bootstrapping identity, but here are the questions I ask myself when trying to approach the problem:

First: Precisely what facts are being authenticated?

For example, do you have a public key which claims to be Snowden's and you're trying to prove that it is genuine? Authentication has a cost, why would he go out of his way to prove that to you?

An easier problem to solve may be "If Snowden wanted to receive a message from me how could he do so securely?"

Second: To whom are these facts being authenticated?

Are you trying to prove to Snowden that a message you sent is genuinely from you? Or is some unknown party claiming to be Snowden expected to prove to you that a message you received is from the authentic Snowden?

Third: Who has what to lose from a successful attack?

Perhaps you are sending something to Snowden and then relying on him to do a perfect job of authenticating what he receives (i.e., proving the absence of an active man-in-the-middle attacker). But if he doesn't care at least as much as you do about the security of the message, he might do a halfhearted job of it you might continue on transmitting messages insecurely.

Fourth: How far do these credentials extend?

In other words, will your actions allow Snowden to do more than just verify you? For example, would he be able to impersonate you to a 3rd party? How about the other way around?

In summary:

A cipher is a device for converting a plaintext confidentiality problem into a key distribution problem.

An ephemeral key agreement algorithm is a device for converting a key distribution problem into an authentication problem.

A signature algorithm is a device for converting a message authentication problem into an identity problem.

If you can somehow establish trust for authentication credentials in one or both directions, the rest is mostly a solved problem. But this can only be built on top of human systems: What will it take for you and/or Snowden to believe that the other party is authentic?


Rotation table for 8 round DES I'm trying to implement DES from scratch using the NIST paper and the Wikipedia article on DES.

I got 16 round DES done, but I can't seem to get 8 round DES working. I figure it's because I got the rotation table wrong. The rotation table I'm using for the 16 round version is straight off of Wikipedia's DES Supplementary Materials, while the 8 round version is the same with a few 2's in the middle taken out to make the length 8. { 1, 1, 2, 2, 1, 2, 2, 1 } for encryption and { 0, 1, 2, 2, 1, 2, 2, 1 } for decryption, which uses inverted key scheduler for decryption. Apparently, that's wrong, and I can't find a table or a algorithm for creating a rotation table.

If anyone can point me to either, it'd be much appreciated.

The catch is that for decryption to work reliably for all keys, the subkeys must be the same for encryption and decryption with order reversed. With many DES implementations, that implies the sum of the rotations in the key schedule should be a multiple of $28$, the width of the C and D registers.

Use say $15,2,2,2,2,2,2,1$ rather than your $1,1,2,2,1,2,2,1$ and you should be flying (assuming the code handles these larger values, and does not use the optimization enabled by the fact that after removing the first value in the DES key schedule table $1,1,2,2,2,2,2,2,1,2,2,2,2,2,2,1$, the $15$ remaining entries are a palindrome). Note: I have changed my suggested values so that the subkeys used match the ones in the last $8$ rounds of encryption in standard DES; that reuses some of the work made by DES designers when crafting PC-2 w.r.t. the key schedule.

Alternatively, use $1,1,2,2,2,2,2,2$ for encryption and make an extra rotation by $14$ before decryption. That way we use the same subkeys as for the first $8$ rounds of encryption in standard DES.

Update: the modified question tells us that the implementation uses different tables for encryption and decryption. In that case, $1,1,2,2,2,2,2,2$ for encryption and $14,2,2,2,2,2,2,1$ for decryption should work (with rotation counts in opposite directions and before the use of the generated subkey). The first decryption value must equal the sum of encryption values$\pmod{28}$. The following decryption values are obtained by dropping the first encryption value and reversing the list.

Caution: care should be taken that all keys bits are used about evenly and regularly, by considering the interaction of rotation counts with PC-2. Because I'm lazy I kept the original first $8$ $rotations, which is at least not disastrous in this respect.


How to perform decryption in this single-bit PKE scheme? Consider a cyclic group $G$ of order $q$, and let $g$ be a generator for $G$. Assume $(G, q, g)$ is public. Consider the following 1-bit public-key encryption scheme.

To $generate (pk,sk)$:

$x \xleftarrow{\$} {1, , 2, . . . , q}$
$h ← g^x$
$pk ← h, sk ← x$
Return $(pk, sk)$

To encrypt the message $M = 0$, we define $E_{pk}(0)$ as:

$y\xleftarrow{\$} {1, 2, . . . , q}$
Return $(g^y, h^y)$

To encrypt message $M = 1$, we define $E_{pk}(1)$ as:

$y\xleftarrow{\$} {1, 2, . . . , q}$
$z\xleftarrow{\$} {1, 2, . . . , q}$
Return $(g^y, g^z)$

Define $D_{sk}(C)$ and prove that this 1-bit public key encryption scheme is $IND-CPA$ secure if the DDH assumption holds for $(G, g)$. (To be clear,
this means doing a reduction.)
(Why would no one ever actually use this scheme in practice?)

I haven't been able to come up with proper decryption yet. And I was thinking proving it to be $IND-CPA$ secure would be along the lines of ElGamal security proof. Am I right about it?

And practically, I don't think this is used much because the work involved in 1-bit encryption multiplied across the number of bits in the message would be much larger than the alternative option of using a multiple bit encryption. Am I right about this?

To decrypt, you basically take the $g^y$ component and raise it to the secret key, obtaining $g^{yx}$. Now, if this value is equal to the second component of the ciphertext, you can see that $M$ must be 0, since $g^{yx} = h^y$; otherwise, $M$ is 1.

Regarding the proof: yes, it would be very similar to ElGamal, since you have to construct the challenge ciphertext using a DDH tuple.


Block ciphers as secure as AES but immune against cache timing attacks? This is a question out of curiosity! I really don't know of any other block cipher that is as secure as AES that has a substitution permutation structure and can be used as an alternative to AES to protect implementations against cache timing attacks.

Searching Google, revealed other NIST finalists, but the best of them had a Feistel structure. There are also many others, but there is less confidence in them compared to to AES.

I am looking for a good block cipher that is similar in structure to AES with same level of security, and efficient to implement in software, for both small and large devices.

There are no efficient attacks against AES that I know of (not counting the related key attacks on AES-256). The minimum security offered for AES-128 is still around 126 bits, and that's with pretty inefficient attacks. Furthermore it is studied very well, so nobody is going to present a cipher that has seen so much cryptanalysis (other than its predecessor DES). So yeah, "as secure" is going to present a problem I guess.

If you look at a cipher that doesn't use a Feistel network you might want to have a look at Threefish. It is a tweakable block cipher with a larger block size, a large number of rounds and large key sizes. As it is part of Skein, a SHA-3 finalist, it did receive some cryptanalysis. The main attack against it is a key distinguishing attack, which is not practical for the full round version and is not applicable when Threefish is used solely as a cipher. Oh, yeah, and it doesn't use tables :)


Can one extend the nonce of ChaCha/Salsa20 by XORing the extra bits with the key? Can one extend the ChaCha and Salsa20 nonces by XORing the extra nonce bits with the key?

My reasoning is as follows:  the Rumba compression function allows attackers to supply any 48-byte input to the core, and HS1-SIV (a CAESAR 2nd round candidate) explicitly assumes and requires that ChaCha20 be secure in the related-key model.  As the HS1-SIV authors point out, this IS secure if the ChaCha and Salsa cores are ideal $48B\rightarrow 64B$ PRFs (they XOR a MAC with the key).

Maybe. But your scheme hasn't been vetted by the community for its impact.

Better to use XSalsa20 or the related XChaCha20 as recommended by Bernstein himself: http://cr.yp.to/snuffle/xsalsa-20110204.pdf

In my opinion it was a fairly major faux pas that DJB originally chose short 64-bit nonces for Salsa20 and ChaCha20, especially given all the nonce-misuse attacks in the past. Storing a no-chance-to-repeat counter is actually really hard in practice. He then went on to make a "idiot-proof" crypto library that requires a user-supplied nonce for every "simple" box function, and yet doesn't include the nonce in the authenticated cipher text output.


What type of commitment scheme is it? I am having a task where I have to evaluate a commitment scheme. I checked already a few questions here, but they have not helped me :( I hope someone is able to help me out in that.

What do I have?

$commit_H$ - perfectly hiding and computationally binding

$commit_B$ - perfectly binding and computationally hiding

Here is $commit_1(m)$ step-by-step.

$commit_1(m)$:

compute $(c_H, d_h) := commit_H(m)$
compute $(c_B, d_B) := commit_B(c_H)$
output $(c_B, (d_B, d_H))$

The first question is if this is a commitment scheme. My answer would be yes, because we have a commitment ($c_B$) and open values $(d_B, d_H)$.

How to open the commitment? $open(open(c_B, d_B), d_H)$

I hope this is correct so far. Now comes the part where I have no clue. I have to decide what type of commitment it is. Is it type B (perfectly binding) or type H (perfectly hiding).

My first thought was that it is perfectly binding. In order to proof this, I am using contradiction.

Contradiction: There exists an algorithm A, such that

$((x_1),(x_2)) \leftarrow A(1^n) ~~(x_1 \neq x_2)$

$commit(x_1) = commit(x_2)$

$commit_B(commit_H(x_1)) = commit_B(commit_H(x_2))$

$commit_B(c_{H1}) = commit_B(c_{H2})$

This would be a contradiction, because $commit_B$ is perfectly binding.

The next step would be to show that it is not perfectly hiding, because my though is that it is type B.

This is where I am stuck. $commit_B$ is not perfectly hiding, which means that an computationally unbound attacker would be able to decommit the first part ($commit_B(c_H)$), but would be stuck at the second part ($commit(m)$), because it is perfectly hiding.

My question would be, what am I doing wrong? Did I misunderstood something? Could someone help me out?

Thanks

Edit: Thanks to the answer from poncho, I get the following solution. It is not completed yet, since I fell unsure about it. Would be nice if someone or even poncho could correct if necessary.

The commitment scheme $commit_1(m)$ is of type $H$. This means, it would be perfectly hiding and computationally binding.

There are 3 things I want to show:

Perfectly hiding
Computationally binding
Not perfectly binding

I would like to start with number 3 - not perfectly binding.

$commit_H$ is not perfectly binding, which means that $\exists m_1, m_2; m_1 \neq m_2$ such that

$c_{H1}=commit_H(m_1)=commit_H(m_2)=c_{H2}$.

$\implies commit_B(c_{H1}) = commit(c_{H2})$

Even $commit_B$ is perfectly binding, after opening $c_B$ it would be possible to open $c_H$ to either $m_1$ or $m_2$ (given unbounded computation) (Thanks poncho).

Next, I would like to show perfectly hiding. I used therefore a game, where an Attacker sends $m_1$ and $m_2$ to $commit_B$ and this is send to $commit_H$. Here is the game I had been thinking of:

We have an unbounded attacker $A$ with an advantage of $\epsilon(n)$.

The probability to win this game is:

$Pr[b=b'] = Pr[Challenger_H(n)=1] = Pr[Challenger_B(n)=b]$ since he passes the messages $m_0$ and $m_1$ without altering them.

$Pr[b=b'] = Pr[Challenger_H(n)=1] = Pr[Challenger_B(n)=b] = Pr[A(n)=b]$.

Since $commit_H$ is perfectly hiding, we get the following equation:

$\frac{1}{2} = Pr[A(n)=b] = \frac{1}{2} + \epsilon(n)$
$\Rightarrow \epsilon = 0$ otherwise it would be a contradiction.

The last thing (can I call it property?) to proof is computationally binding. I am not sure yet how to do that. I am thinking to prove it with computationally and statistically indistinguishability. I will crack me head later on that one too.

My first thought was that it is perfectly binding.

It's not.

  $commit_B(C_{H1}) = commit_B(C_{H2})$

That's fine

  This would be a contradiction, because $commit_B$ is perfectly binding.

Actually, that's not a contradiction, because it's possible that $C_{H1} = C_{H2}$

After all, $H$ is not perfectly binding; what that means is that you can have two different messages with the same commitment (one would hope that it is hard to find both sets of the random coins that would yield the common commitment; but we're talking about existence, not computational complexity).  In fact, if $H$ is perfectly hiding, then any valid commitment could possibly correspond to any message (if there's a message that it could not reveal, then the receiver could deduce that message was not the committed one).

Hence, $commit_H(M_1) = commit_H(M_2)$ is perfectly possible, given the appropriate random coins.

And, so, when we open the larger scheme, the committer can (given unbounded computation) change his mind what he opens $H$, and so this is not perfectly binding.


One way function built from AES? I'm implementing a Hash based signature algorithm and this paper recommends the use of $F(X,\mathit{salt})=\operatorname{AES}_\mathit{salt}(X)\oplus X$ as a hard one way function. The salt plays the same role here as it does in password hashing and is a fixed public value that varies across small groups of calculations.

The requirement is that $F$ be preimage resistant. (IE: given $F(X,\mathit{salt})$ attacker can't find $X$ faster than brute force)

Cryptanalysis has been done which rules out AES in contexts where the attacker gets to find approximate solutions to similar equations or gets control of key bits (EX:as hash compression function). In all these cases the attacker has degrees of freedom to work with. Here they don't.

Is $F$ preimage resistant? Can the attacker find $X$ with siginficantly less that $2^{128}$ work?

This is the Matyas–Meyer–Oseas construction.  It was introduced by engineers at IBM in 1985, and analyzed in the ideal cipher model by Black, Rogaway, and Shrimpton in 2002 among all possible iterated compression functions $h_i = f(h_{i-1}, m_i) = E_a(b) \oplus c$ where $a$, $b$, and $c$ are message blocks $m_i$ or chaining values $h_{i-1}$.  For this case ($i=1, j=6$, or $a = h_{i-1}$, $b = m_i$, $c = m_i$), in the ideal cipher model, the adversary's probability of finding a preimage after $q$ queries lies in $[0.4 q/2^n, 2q/2^n]$.

Now, AES is not an ideal cipher—at best, it is a pseudorandom permutation family.  But it is likely that the related-key attacks of Biryukov and Khovratovich do not substantively affect the security of this scheme when the salt is not under attacker control.

(All the references you need are actually in the paper you cited already, right where it recommends using AES.  If you can't follow them because of morally reprehensible academic paywalls, Sci-Hub and LibGen are your friends.)


Shamir's Secret Share I'm not quite sure the benefits of working over a prime modulus in Shamir's secret share- but doesn't limiting the numbers you pull from make the secret easier to guess? Instead of being over the real numbers, with infinite elements, limiting yourself to some prime limits the possibilities-albeit that number can get very large.
Isn't this bad? What benefits are there to working over a prime that justify this choice?

Computers are unable to handle real numbers, especially irrational numbers.

Computers can handle a fraction of the rational numbers (for being limited in size in a binary representation), and without some special tricks it can't handle the entire field $\mathbb{Q}$.

So you're down to integer arithmetic anyway (if you consider floats: rounding and cancellation can really mess things up). However, addition and multiplication over integers are just a ring structure and not a field (multiplicative inverse elements do not exist). So if you need to invert multiplication you need to use the finite structure.


Encryption of big files in Java with AES/GCM I have to encrypt big files. Say their size ranges from 500mb to several of gigabytes.

I would like to use AES/GCM/NoPadding as provided by Java 1.8 since that gives me automatic authentication and encryption.

I would like to use the handy Cipher Input/Output Stream cause I can chain it with GZip I/O Streams to compress the data a little before encryption.

However I was reading that the implementation of Java appends the authentication tag at the end of the stream. That means that for a long file, if I were using CipherInputStream to decrypt it, it wont be able to tell whether the contents have been tampered or not until it reaches the end of the stream, right?

If that were the case, wouldn't it be problematic to actually use that operation mode for what I'm trying to accomplish becuase since the file can't be decrypted in memory it will have to be decrypted somewhere in the filesystem until the failure is detected, leaving some time for an attacker to see the plain text?

Is this a potential thread and a real concern that I should be worrying about or there's something about the algorithm / cipher streams that I'm missing and prevents that from ocurring?

There is nothing in the GCM cipher that prevents it's use it in streaming mode. You should however not use the resulting plaintext during decryption for anything that requires security before you have verified the authentication tag.

The authentication tag is not to prevent you from decrypting the ciphertext. It is there to provide for integrity and authenticity. You should never decrypt where an attacker can see the plaintext. If possible, you should even try and make it hard for an attacker to perform side channel analysis.

Note that GCM is bounded to encrypting about 68 GB ($2^{39} - 256$ in bits) of data for a single IV. The amount of invocations is $2^{32}$ but you should be advised to stay well away from those limits. Note that repeating the IV for two separate encryption invocations is a catastrophic event for GCM.

CipherInputStream in general is horrible. I would suggest to reprogram it using Cipher and memory mapped files and ByteBuffer itself. The Java implementation (where the tag is automatically put at the end) and CipherInputStream make for this horrible buffering mess.

I'm rewriting the Bouncy Castle implementation and I see a code & complexity reduction of about 30% when I separate the tag from the decryption, plus it enables to decrypt each byte separately. In other words it restores the online properties of the underlying CTR cipher.

With Java 8 however you may want to stick to the Java 8 implementation as GCM may be sped up using intrinsics (for the server VM on the latest Intel processors). Note that according to archie below this functionality is not yet present.


What is the actual result of a Logjam's DH attack? Does a Logjam attack calculate a group of probable Diffie-Hellman private keys for a user and then try them one at a time to see if it can decrypt the message - or does it directly calculate the one specific instance of a user's private key?

Simple description of Logjam
Logjam is a two-step process. First, you take a group and apply a precomputation to it. Most people use one of a few different groups, so breaking a single group effectively breaks every single key exchange done by anyone using that group. If a group is "broken", then any key exchange done with Diffie-Hellman using that group can be broken quite easily,* revealing the shared secret. This is the second step to the process, using values derived from the precomputation to quickly determine the shared secret.
Logjam does not attack any one user's individual key and it does not rely on any information specific to any single key exchange event. In fact, the initial precomputation step of the attack could be performed for a group even if no one has ever used that group before. All it means is that when anyone does use that group, the derived shared key could be passively recovered by an eavesdropping party.
Slightly more accurate description
A simplified view of Diffie-Hellman is that it involves Alice and Bob agreeing on a generator $g$, and a prime modulus $p$. All operations are done modulo $p$, making it a finite cyclic group. Alice generates a secret integer $x$ and sends the result of $g^x$ to Bob. Bob generates a secret integer $y$ and sends the result of $g^y$ to Alice. Now Alice calculates $(g^y)^x$ and Bob calculates $(g^x)^y$. It just happens to be that $(g^y)^x = (g^x)^y = g^{xy}$, so now $g^{xy}$ is the shared secret. DH gets its security from the fact that Eve has access to $g$, $p$, $g^x$, and $g^y$, but is unable to calculate the value of $g^{xy}$. Seems all rosy, right?
Recall that all of the above operations are done modulo $p$. Unfortunately, it turns out that a one-time computationally-intensive calculation done on $p$ allows an attacker to derive information that allows them to calculate $g^{xy}$ from only $g^x$ and $g^y$, despite never having direct access to either $x$ or $y$. They can re-use the information derived from the analysis for any exchange done modulo that same prime $p$.
Full description
https://weakdh.org/imperfect-forward-secrecy-ccs15.pdf
Mitigations
There are three ways to mitigate this attack:

Use a custom modulus - You can generate your own DH modulus instead of an existing group. This would force an attacker to perform an extremely complicated precomputation step tailored specifically to your system, making it impractical to attack. After all, $10,000,000 to break a third of the Internet's key exchange is nothing to a powerful adversary, but it's probably too much to spend on a single target. This is an option if you don't want reduced performance from a larger modulus.

Use a large modulus - You can use an existing but large (2048-bit or greater) group. While the precomputation attacks are still possible and breaking the group would allow mass recovery of shared secrets, the size of the modulus would make it impossible to attack with any modern technology. This is a risky option if technology significantly improves in the near future.

Use elliptic curve cryptography - Finally, you can switch away from finite-field Diffie-Hellman and instead use elliptic curve Diffie-Hellman. ECDH, in addition to being faster and more secure even at smaller key sizes, is not vulnerable to precomputation attacks. It performs calculations as points on a curve, rather than modulo a large prime number (your potentially exploitable group).

* It still requires some serious computing power, don't get me wrong, but it's nothing compared to the initial precomputation step. A powerful ASIC cluster could break each key exchange using the broken group in real time.


Looking for a formula for "Given $x_1$, $\ldots$, $x_{n-1}$, the output $F(x_1,\ldots,x_n)$ is dependent of $x_n$ and is of $l$-bits security" Suppose I have a function $F(x_1,\ldots,x_n)$, where each $x_i$ is of $l$-bits security (suppose each $x_i$ is a binary string of length $l$). At the same time, suppose there are $n$ persons, each one having a value $x_i = b_i$.
I want to write down in a mathematical formula the following: "given $x_1=b_1$, $\ldots$, $x_{n-1}=b_{n-1}$, the output of $F$ is dependent of $x_n$ and is of $l$-bits security". I.e., if any $n-1$ persons plug in their values, there are $2^l$ possibilities for $F(b_1,\ldots,b_{n-1},x_n)$.

For example, consider the function $F(x_1,\ldots,x_n) = x_1$.
The output of $F$ is only dependent on $x_1$.
This function offers no security: if player 1 plugs $x_1=b_1$, there is one unique possibily for $F(x_1,\ldots,x_n)$ ($l=0$).
Second example (bit-wise sum). Consider $F(x_1,\ldots,x_n) = x_1 + \cdots + x_n \pmod{2}$.
Given $x_1,\ldots,x_{n-1}$, the output depends on $x_n$ and is of $l$-bits security.
Now, returning to the question, I have an intuition that the formula that I want is
$$H(F(x_1,\ldots,x_n) | x_1,\ldots,x_{i-1},x_{i+1},\ldots,x_n) = H(h_i) \quad \forall i=1,\ldots,n$$
where $H$ is the Shannon Entropy.
Can someone point if I am in the right path and formally describe the formula that I am looking for and explain it?
Thanks in advance.

To be well defined as a function, you need to specify lengths of the $x_i$, which is not the same thing as their entropy. Also, the $H(h_i)$ in your equation should probably be $H(x_i).$

Let's assume each $x_i$ are binary vectors of length $n$ for concreteness. Then what you want in a more general version of this problem would be
$$
\mathbb{H}(F(x_1,\ldots,x_n) | x_1,\ldots,x_{i-1},x_{i+1},\ldots,x_n) \geq \mathbb{H}(x_i) \quad \forall i=1,\ldots,n
$$
which also takes care of the unequal entropy case for the different $x_i.$


A simple keyed message authentication code using XOR Suppose I have a key that is at least 32 characters in length and provides at least 128-bits of entropy. If I picked from the character set of [a-hjkmnp-z2-9-], then I know that each unambiguous character provides exactly 5 bits of entropy if built from a CSPRNG, such as /dev/urandom. Thus, a 32-character string would meet my requirements by providing 160-bits of entropy. Something like amjgg6d3e9v7makwad2y544qtz-wxu9x. Suppose also I have a 16-character base64 salt. Something like BGTH8iPYi16nJCCh.

Now, suppose I hash the concatenated password and salt with SHA-256(salt||password), giving hex string H1;

3b1a89849599a9a2b8ebfa34fb4f9ef7fc26093980fb49901d6670329fcc8da8

And suppose I hash the message "foo bar baz" with SHA-256 as well, giving hex string H2:

dbd318c1c462aee872f41109a4dfd3048871a03dedd0fe0e757ced57dad6f2d7

My question is this: Aside from the cryptographic strength resting on the entropy of the provided key, and the cryptographic strength of the hashing function, what is cryptographically weak with the MAC construction of H1 XOR H2, which provides the following as a hexadecimal string as a MAC?

e0c9914551fb074aca1feb3d5f904df37457a9046d2bb79e681a9d65451a7f7f

Assuming your authenticated message is public (which is reasonable), this scheme seems insecure for the following reason:

Your authentication tag $t$ over message $m$ is computes as

$$t=sha256(salt||key) \oplus sha256(m)$$

This means that any adversary knowing $m$ can compute a new authentication tag $t'$ for a message $m'$ in the following way:

$$t' = t \oplus sha256(m) \oplus sha256(m')$$

This will result in

$$t' = sha256(salt||key) \oplus sha256(m) \oplus sha256(m) \oplus sha256(m') = sha256(salt||key) \oplus sha256(m')$$

This is, by your definition, a valid authentication tag for $m'$.

You need to incorporate the message into the authentication tag in a non-reversible way. For example, HMAC does $h(k \oplus opad || h((k \oplus ipad) || m))$. This way, a new authentication token cannot be created without inverting the hash function $h$. (opad and ipad are fixed values that are used to ensure the keys are different at both positions)

Additionally, you would have to distribute your salt to the recipient somehow, and ensure that the adversary cannot change it. Otherwise, authentication will be impossible because the recipient cannot compute $sha256(salt||key)$.


Cryptanalys of "bad" RC4 implementation I need help of cryptanalyzing a "bad" RC4 implementation to recover an encrypted text of 13742 bytes.

I don't know the key and this implementation does not utilize the drop-n routine.

But, I know the key length (256). Also, I think it is a bad implementation because the KSA is as follows:

def ksa(key) :                                   # RC4_KSA_STANDARD
  S = range(256)[::-1]                           # S = range(256)

  j = 0
  for i in range(256) :
    j = (j + S[i] + key[i]) % 256                # j = (j + S[i] + key[i % len(key)]) % 256
    S[i], S[j] = S[j], S[i]

  return(S)

The initialisation of S is inverted ([::-1])
j is calculated without key[i % len(key)]

My hypothesis: recover the first round with the first 256 bytes of encrypted text (because KSA is maybe more "predictable" without key[i + len(key) % 256]).

My questions are:

Am I on the right track?
Otherwise, is there some better strategy?
What is the calculation to conduct the attack to obtain the plaintext message?

I have a little problem with the mathematical logic in some aspects (is my bad asperger side). If anyone would be kind enough to explain this to me?

This post answers my first questions: RC4 Keystream Reconstruction

Because I integrate others informations to this problem.

The RC4 algorithm has some well-known vulnerabilities but it is not completely moldy. So, if I understand correctly, finding the initial encryption key even with the clear text is difficult (Principaly in this case, no reset rc4, key lenght, ...).

On the other hand I understand that I work on a similar challenge.

I have to decrypt a file of the same type: INTEL Hex Format

So, Drop-N routine or not, if I know the plaintext I know the associated XOR key.


How should I manage Diffie-Hellman parameters on a Web Server? Is there a best practice for Diffie-Hellman parameters (p, g, and q) used on a web server?

The server is using ephemeral keys, but should the parameters be rotated on a regular basis? Is it OK for the server to keep them fixed for years (in the source code)? Or should they be generated uniquely for each site?

This server does not appear to be under NIST and FIPS, so I don't believe they need to be fixed for compliance.

I will address your question below, however I have a serious concern that I want to bring up first. I glanced at the $p$ used in ngx_ssl_dhparam, and it is not immediately obvious that it was chosen correctly.  Unless you know that whoever generated that value knew what they were doing, you should select a different value.

The security of DH depends on, among other things, the factorization of $p-1$.  If $p-1$ has a prime factor $q$ (and $g$ wasn't selected such that $g^{(p-1)/q}\equiv 1\  (\bmod p)$), then an attacker, seeing the DH public value $g^e \bmod p$, can determine $e \bmod q$ with $O(\sqrt{q})$ work.  This means that if $p-1$ has a number of moderately sized factors (which will often be true of randomly chosen primes), and $g$ wasn't carefully selected, then you'll be leaking a significant amount of information; quite potentially enough to make DH completely insecure.

In your case, we have $g=2$; this would appear to make it unlikely that $g$ was chosen to avoid small factors.  And, if $p$ were a safe prime, this would not be much of a concern (because safe primes have no small factors to $p-1$ other than $2$), however you stated (and I have not confirmed) that their specific $p$ is not a safe prime.  I do note that, with $g=2$, your group has $g^{(p-1)/2} \neq 1$, and hence you do leak at least one bit of $e$ -- if that were all you leaked, that would not be much of a concern; however it begs the question "what else is being leaked".

I haven't checked if your $p-1$ has small factors; unless you check (or you trust whoever generated it), I would strongly urge that you use a different value of $p$.  This specific value of $p$ might be secure, however I don't know that (and I suspect you don't either). When I am asked for recommendations for DH groups, I always send people to the IKE groups; those are all safe primes (and work well with $g=2$, not leaking even that one bit)

Now, to go back and answer your question: no, you shouldn't have to rotate the group parameters on a regular basis.  It turns out that solving the problem "given these $N$ DH exchanges over the same group, solve any one of them" is not actually any easier than "given this 1 DH exchange, find the shared secret".  That is, if the group is weak when you reuse it for DH, you shouldn't be using that group in the first place.

On the other hand, a 1024 bit value of $p$ is getting to be fairly small nowadays.  NFS has been used to factor a 768 bit value recently; it should not be that long before it could practically be used to solve 1024 bit DH problems (which would mean that your group could be broken, even if $p$ was chosen without any inherent weaknesses).  I would suggest you consider at least a 1536 bit $p$ (and preferably a 2048 bit value); from what we know, those should be secure for a number of years.

Update: I just double-checked; $p$ is indeed a strong prime, that is, $(p-1)/2$ is also prime.  Hence, the concerns I raised about $p-1$ having small factors do not apply; there is a 1-bit leak (because of the factor 2 of $p-1$), however there is no other leakage.

My concern about the size of $p$, and whether that would be secure long-term, still remain.  I'll leave in the comments about weaknesses that may arise with $p-1$ having small factors; even if they don't apply in this case, future readers may find it useful.


Upper bound Linear Feedback Shift Register It is clear that when we have any output stream $x_0,x_1,...$ produced by linear-feedback shift register, then this output has to be periodic.

Now I was wondering if we can find an upper bound for the period of the output sequence from a linear-feedback shift register with $R$ registers over $\mathbb F_q$?

Between them, K.G. and Dilip Sarwate have pretty much answered your question. That is, you can derive an upper bound using the method described by KG:

  When the LFSR reaches a state it has been in before, what happens to the output sequence? How many possible states are there? Now you have an upper bound

However, working out how tight this bound is can be much more difficult (as per Dilip's comment):

  In general, the period of a polynomial $g(x)$ is the least integer $e$ such that $g(x)$ divides $x^e−1$. If $g(x)$ is the feedback polynomial of an LFSR, then $e$ is the upper bound you seek.

In particular, this is the cycle generated if you initialize the LFSR with all the entries $0$ except for the last one set to $1$.

For a good LFSR, the period will be close to the maximum possible. Consider the tightness of the bounds described by K.G.: if the feedback polynomial is 'badly' chosen (for example $x^k-1$), the period may be much lower.

Since each time you 'step' the LFSR you are multiplying by $x$ within the appropriate field extension, to calculate the period it doesn't matter where on the cycle you start. It does matter that your initial condition is somewhere on this cycle, as for example initializing with the $0$ state leads to a cycle of only $1$ element. Now, if the period is maximal, then every non-zero element must be part of the 'main' cycle, and so any initialization vector will lead to an LFSR of maximal period. However, if the period is lower than this, we must be careful to ensure that the starting vector is indeed on the main cycle.


Plaintext formation for checking avalanche effect I have developed an encryption algorithm. Now i want to check avalanche effect by making one bit change in plaintext and observing how many bits are changing in ciphertext. But my doubt is "what is one bit change in plaintext" say for e.g
if plaintext P1= 11223344 then do we mean one bit change as
             P2= 11229344

No.  You cannot use decimal numbers (or ASCII characters for that matter).  You have to use binary.  Your algorithm will be operating in binary as do digital computing devices.  If you were to use ASCII chartacters as you have, you'd only be testing the printable range of byte values.  You'd have huge gaps in the test inputs and no continuity.  You might only test 50% of the possible range, depending on your interpretation of what a printable ASCII character is.  If you've defined your P1 and P2 as integers, then the gap will be even bigger (= 10/256%) as you're now restricting yourself to integer parsable characters.

So in the Java language, P1=0b1110011 and therefore P2=0b1010011.  You randomly flip them.  In Java that's easy as you can use BigInteger for that and it handles arbitrarily sized integers and their random generation.

There's some more detail of the test procedure in this, this and this other answer.  Good luck with your normal curve.


Diffie-Hellman in the wild Say we have a public network and lots of peers.   Each may need to communicate with another peer.

Would there be any huge security issue to each peer making the the public part of their key openly available across the network?

In this way, any other peer in the system could automatically calculate a secret to communicate with them.   (e.g. using the secret as the AES encryption key)

Any caveats or issues welcome, thank you.

Basically yes, you can do that. Public keys are meant to be shared. The devil is in the details however:

public keys without trust are pretty useless as you don't know who you are performing the key agreement with;
two static keys will always generate the same key for the same partners if you use a naive DH implementation, something you probably don't want;
you need different keys for the sender and receiver
you need message integrity and authentication once you start sending messages

Etc. etc. etc. Different methods of performing DH are described in NIST SP 800-56A Revision 2. That still doesn't describe the authentication framework though. You could do worse than learning TLS 1.2 and 1.3 for starters.


Probabalistic Polynomial-time Algorithms & One-way functions I've been reading up on probabilistic polynomial-time algorithms and one-way functions, and I was hoping to get some guidance on the topic.

A textbook I'm reading states the following for one of the conditions for one-way functions:

Hard to invert: For every probabilistic polynomial-time inverting algorithm A, there exists a negligible function negl such that
$$Pr[A(f(x))\in f^{-1}(f(x))] \leq negl(n)$$
where the probability is taken over the uniform choice of x in $\{0,1\}^n$ and random coin tosses of A.

What exactly does it mean by "random coin tosses of A"? Is it stating that the "inversion function" is randomly generated by such a process?

A probabilistic algorithm uses random numbers to define the next step it should do (google for instance "Monte Carlo Algorithm").
"Random coin tosses" merely says that the random numbers are equally distributed.
The algorithm A will use the random numbers only internally, it will not output any random number.
But A's output will depend on those random numbers.
Therefore, it will output a correct pre-image only with a certain probability.


Is this scheme a provably fair random number generation? I have thought up a method for generating random numbers between a client and a server which I hope is fair:

The client and server decide on a range in advance, $0$ trough $n-1$.
The server generates a $256$ bit random number $m$ (in the range $0$ to $\operatorname{floor}(\frac{2^{256} }{ n}) · n$) and hashes it with SHA-256 to give $m'$. $m'$ is then sent to the client.
The client generates a $256$ bit random number $o$ (as above) and sends it to the server.
The server can now calculate a fair random number $p = m + o \pmod n$.
The server sends $m$ and $p$ to the client.
The client can now check $\operatorname{SHA256}(m) = m'$ and $p = o + m \pmod n$.

Am I overlooking anything?

Yes, your scheme is fine.

Nitpick: I think you mean that your goal is to generate a random number in the range $0\ldots n-1$ (not $0\ldots n$).  Also, to avoid bias, you need to generate $m$ as a random number in the range $0 \ldots (\lfloor 2^{256}/n \rfloor \cdot n)-1$ (not $0\ldots \lfloor 2^{256}/n \rfloor \cdot n$).

This problem is known as secure coin flipping, and it has been studied in great depth before.  For solutions and analysis, look at the following questions on this site:

How to fairly select a random number for a game without trusting a third party?
https://crypto.stackexchange.com/a/465/351
Proof that lottery does not know outcome of draw
A fair peer-based coin-flipping protocol?


Does SRP also authenticate the server to the client? The Secure Remote Password (SRP) protocol lets a client prove to a server that it knows a specific password without revealing that password to the server. The server stores a cryptographic verifier for the user account. If an attacker impersonates as the server it cannot learn the user's password.

Now, does it also work the other way around. If a SRP password authentication succeeds, does that also prove to the client that the server knows the correct verifier, and thus assuming that the verifier was kept secret that the client is talking to the real server? (Or at least to the server that it originally gave the verifier to?)

Reading the protocol description I think it does, but as far as I can see the description nowhere mentions this property as something SRP is supposed to do. So maybe there is something I'm missing.

SRP protocol on Wikipedia
The Stanford SRP Homepage

According to the Stanford page mutual authentication can be provided if both sides keep their secrets secret. Thanks mikeazo.


Algorithm: How to use x and y mouse movement co-ordinates to generate random data? Background:

I'm making a program for fun as a learning exercise. I want to generate some actual random key material (not pseudorandom) from a JavaScript program. For my program is just for encrypting/decrypting plain text letter by letter so I've chosen to use the ASCII printable character set (what characters you can type on a standard US keyboard) which gives 95 possible characters.

I want to capture a users' random mouse movements on screen to capture a long stream of random numbers. I want to use the x & y coordinates from each mouse position out of a possible screen resolution of 1920x1080 pixels and then map them back to a character within the list of possible ASCII characters. Then I can use that character in my key material. Let's say the program captures the following series of x and y coordinates like so:

[478,702]
[503,701]
[581,687]
[633,670]
[691,646]
[757,620]
[814,599]

Question 1:

At this point should I multiply the x and y coordinates to get a better random number, ie 478 x 702 = 335556 and use this number? Because if I just took the x number separately then you might end up with consecutive numbers e.g. 121, 122, 123, 127 as they're moving the mouse in one direction which doesn't look particularly random. Or should I add the numbers together ie 478 + 702 = 1180? Or perhaps alternate between adding and multiplying for each set of coordinates I get to make the random number?

Question 2:

Now what's the best way to map the random number to a character in my list (array) of possible characters? If I've got an array of all the 95 characters [0 - 94] for a zero based array, and lets say my random number is 1180, how do I map that back to a character in my array? Do I loop over the array multiple times until I'm at the 1180th character and now use that character for my key? Essentially this would be like repeating the 95 possible characters in a row up to 1180 characters, then taking the last one. Or maybe you can work this out mathematically?

Or do I create a big 2D array with all the characters repeated horizontally and vertically (like a big grid to match the screen size), then when an x and y mouse coordinate comes in I map it to the x and y indexes in the big 2D array and use that character?

Question 3:

What is the entropy quality of the random numbers generated from the mouse movements? Does mapping it back to the reduced character set reduce the entropy? How can you make the process of capturing random data from the mouse movements better?

Question 4:

If my screen size is 1920x1080 pixels and I pull out an x and y coordinate from that. What is the search space ie $2^x$? how do you work that out?

Many thanks

The PuTTYgen program, which is open source, contains the following comment in WINPGEN.C where it collects mouse movement for key generation:

/*
* My brief statistical tests on mouse movements
* suggest that there are about 2.5 bits of
* randomness in the x position, 2.5 in the y
* position, and 1.7 in the message time, making
* 5.7 bits of unpredictability per mouse movement.
* However, other people have told me it's far less
* than that, so I'm going to be stupidly cautious
* and knock that down to a nice round 2. With this
* method, we require two words per mouse movement,
* so with 2 bits per mouse movement we expect 2
* bits every 2 words.
*/

I don't know how accurate this information is. I just remembered seeing it and though it was worth sharing.


Commutativity of keyed hashes Definition

${H_1}^{K_1}(X)$ means data  $X$ hashed by keyed hashing algorithm $H_1$ with key $K_1$.

Short question

Is $H_1^{K_1}(H_2^{K_2}(X))$ equal to $H_2^{K_2}(H_1^{K_1}(X))$?
Is $H_1^{K_1}(H_1^{K_2}(X))$ equal to $H_1^{K_2}(H_1^{K_1}(X))$?

Long question

My web application is storing a hashed password in a database. A web service requests for authentication that the user types a password, which is hashed with a random key and then sent to the server. The server thus only sees $H_1^{K_1}(X)$ where $X$ is the password, not the password itself.

I have to compare the client-side hash with the original password.
How can I do that?

For H1=H2 there are one-way functions with that property: $y = g^x \mod p$.

$ (g^{k_1})^{k_2} = g^{k_1 \cdot k_2} = (g^{k_2})^{k_1}$

This property is exploited by the Diffie-Hellman key exchange. One variation of DH used for password based authentication is SRP.

I strongly recommend to use an existing protocol, and not write your own. Implementing SRP is quite easy to get wrong. I'd just use SSL, either with a normal suite (such as ECDHE_RSA) sending the password in plain over that connection, or using a SRP suite(only supported by a few libs, such as GnuTLS).


DSA vs. ElGamal vs. Schnorr It has been well known for a long time that NSA played a primary role in the development of the Digital Signature Algorithm (DSA).

DSA is a sort of hybrid of the ElGamal and Schnorr signature schemes.

My question is this. Based on what we know now, why did NSA invent a new scheme rather than just adopt ElGamal or Schnorr? I am looking for informed speculation based on what is known today about the relative strengths and weaknesses of these schemes, with references. (References for the strengths and weaknesses, I mean, not for the speculation.)

If your speculation is that NSA did something to weaken DSA, what could they possibly have gained other than the ability to forge signatures?

Or was DSA just the result of IP concerns? If so, I would like to see a reference for that, too.

Apparently, Schnorr was quite adamant, at that time, about the applicability of his patent to DSS. See this message and that one. These are from 1998, but the controversy had begun earlier; see for instance this bulletin from NIST, from late 1994, where references to it can be found in the "Patent Issues" section. Interestingly, NIST not only tried to avoid Schnorr's patent, but they also filed their own patent. Also, see this message for another analysis.

It must be recalled that when NIST began pushing standards for asymmetric cryptography, RSA was already taking the lion's share of the market; what really deserves an explanation is not why NIST preferred DSA over Schnorr signatures, but why they used the DH/DSA pair instead of RSA. IP issues are a very plausible explanation; as the references above show, there indeed was some bitter strife in those years.

As for ElGamal signatures: that scheme is more expensive. ElGamal signatures work modulo a prime $p$ and require one modular exponentiation (for generation) or two (for verification) with exponents as big as $p$; and the signature is two integers modulo $p$. This contrasts with DSA and Schnorr, which both work in a subgroup, traditionally a 160-bit subgroup for a 1024-bit modulus. DSA and Schnorr are 6 times faster than ElGamal, and produce signatures which are 6 times smaller. This difference in performances is enough to explain not choosing ElGamal. Indeed, the short size of DSA and Schnorr signatures has long been the selling point for these algorithms when compared to RSA.


One-time pad encryption - how does the receiving side decrypt the message? If a message is sent using one-time pad scheme, which generates random bits in order to, for example, XOR them with the message's bits - how does the receiving side generate the exact series of bits ?

If the receiving side is able to generate the same series then how is it still random ?

The one-time pad requires pre-shared key. Usually, one of the two parties generates the keystream, writes into a paper or CD/DVD, or USB, etc.. and sends the keystream to the other party in a secure way. The secure way is not encryption, it is using some men to carry it to the target. After the transmission, they can use the key to decipher.

Wikipedia lists historical uses of the one-time pad. One case is very important; the Venona Project. At some point, the Russians had reused some part of the key. So, the question is how one notices this? The USA and British Code-breakers always tried the crib-dragging and one day was successful!

Some of The Crib Draggin answers in CryptoSO;

Taking advantage of one-time pad key reuse?
How does one attack a two-time pad (i.e. one-time pad with key reuse)?
Little problem with Vernam Cipher

And, an article: A Natural Language Approach to Automated Cryptanalysis
of Two-time Pads


How do I construct a 256-bit hash function from 128-bit AES? I would like to generate a 256-bit hash on a microcontroller that has a 128-bit (only) AES engine. How can I construct a 256-bit hash function from a 128-bit cipher?

HMAC is a specific construction which aims at providing a message authentication code. HMAC is defined over a hash function, something which AES is not.

So if your question is really about having HMAC, not just any MAC, and using an AES primitive, then your question becomes: how can we build a hash function out of a block cipher ? This is not an easy question, especially if the block cipher uses blocks which are smaller than the intended hash function output size. You could investigate ECHO, a former SHA-3 candidate, which received a reasonably fair share of analysis by many cryptographers, who found no actual problem in it. ECHO is built upon some constitutive parts of AES, and can benefit from most hardware accelerators for AES.

On the other hand, if you just want a MAC (not specifically HMAC), and have an available AES primitive, then I recommend CBC-MAC (just don't use the exact same key to encrypt data !). This will yield a 128-bit MAC. A 256-bit MAC is a weird requirement, since 128 bits ought to be enough to provide adequate security (if 128 bits are not enough, then the attacker is way more powerful than the whole of Mankind, including all governments, agencies, private corporations and mafias -- and at that point you probably have more trouble than a possibly weak MAC: for all practical purposes, the attacker is God).

One could imagine defining a 256-bit block cipher with a Feistel network where the confusion function is an AES instance, with enough rounds and distinct round keys -- like what the DEAL block cipher did with DES, during the AES competition. Then CBC-MAC on that block cipher would yield a 256-bit MAC. But custom building of block ciphers or other cryptographic primitives is not recommended at all since it is hard to get right, and you cannot test for the security of the result.


Can SRP be used with Elliptic Curves? I'm sure it can, because SRP (secure remote protocol) can be implemented everywhere where Diffie-Hellman works, but I need a proof to put this aspect into Wikipedia.

Edit: ok, can it be at least partially moved to elliptic curves?

SRP needs more than a group, it requires a field. See the specification: second user sends $B = v + g^b$. This requires two operations, addition and multiplication. You cannot trivially slap that onto a group which provides only one operation, such as elliptic curves.

Variants of SRP which use elliptic curves have been proposed, but do not seem to have reached wide acceptance or even substantial scrutiny yet. See for instance this proposal. Also, this article gives some details (e.g. it claims to break a previous proposal for an EC-based SRP variant).


Practical benefit of using a KDF? I see that KDFs should be used in systems that rely on PSKs, but what practical benefit does it provide?

For instance, suppose the system relies on a shared secret for AES encryption and decryption. If the en/decryption uses a key derived from a KDF, an attacker could still sniff the key and decrypt the file. Yes, the key could be regenerated using the secret, but for the purpose of en/decryption, it would remain fixed unless compromise is detected.

So, under what scenarios does KDF increase protection? Is it just to increase the entropy of the key so that it'd be harder to crack?

Thanks

An important principle in cryptography is "key separation" which holds that one should "use distinct keys for distinct algorithms and distinct modes of operation".  Violating key separation often opens up avenues of attacks that may break confidentiality, integrity, or even recover the key.

You can use a KDF to derive cryptographically independent keys from a single "master key", and then use those keys in different algorithms and/or modes, thus respecting key separation.

The paper "On the importance of the key separation principle for different modes of operation" (Gligoroski et al) provides the definition of key separation that I used above, and a description of some attacks that are possibly when key separation is violated.


How to properly AES encrypt a string, deriving the key from the same string? Let's say someone has a list of names, e.g.:

'Batman'
'Batman'
'Super Man'

I am auditing this list, but I'm not allowed full access to all names. So they must be encrypted.

I should be able to:

Determine that one name appears twice in the list, and that one appears once
Get a clear text name (from the list owner) and use it as key to decrypt its encrypted version

One approach is for the list owner to encrypt the names with a pre-determined iv, and a pre-determined algorithm for generating a key. Just to illustrate, a simple algorithm could be to append 0's until the key is 32 bits:

batman_cipher    = SymmetricEncryption::Cipher.new(key: 'Batman00000000000000000000000000',
                                                   iv: '1234567890ABCDEF',
                                                   cipher_name: 'aes-128-cbc')
super_man_cipher = SymmetricEncryption::Cipher.new(key: 'Super Man00000000000000000000000',
                                                   iv: '1234567890ABCDEF',
                                                   cipher_name: 'aes-128-cbc')

batman_cipher.encrypt('Batman')         # => 'TYBaLlaS/8QogiyBt77LVQ=='
super_man_cipher.encrypt('Super Man')   # => 'aSrFGzbWjwXGpEf0VU8t4Q=='

The encrypted list would be:

'TYBaLlaS/8QogiyBt77LVQ=='
'TYBaLlaS/8QogiyBt77LVQ=='
'aSrFGzbWjwXGpEf0VU8t4Q=='

The only way for me to get the clear text names would be to guess or to ask the list owner for one of the names so I could test it:

batman_cipher.decrypt('TYBaLlaS/8QogiyBt77LVQ==') # => 'Batman'

My question: Unless there is a better approach, what would be the best strategy to strengthen the security, e.g. generating secure keys?

It seems that there are no specific security implications in deriving a key from the string you want to encrypt. And the best strategy I can find elsewhere is to hash the string and truncate its output to 32 bits

My question: Unless there is a better approach, what would be the best strategy to strengthen the security, e.g. generating secure keys?

When you want to derive key for cipher, do use a KDF, ciphers require high-entropy key on all it's length to avoid potential weaknesses. Also, this way you avoid any problems with strings longer than your key size is.

But it appears that you don't need encryption at all. You can just get hash for every item. Then you can check list for duplicates, and request for original text, which then you can validate because you have hash. This is very same as encryption, except you can theoretically get collisions (but if you find collision in modern hash, that would be something special - nobody yet managed it).


Attestation of private key deletion I recently came across an article outlining a framework for a hypothetical cryptocurrency, the article is here if you care to read the whole thing. The relevant section is the "Digital Cash" section. The main primitive seems to be the enforcement of a single owner of a private key through the use of secure enclave hardware as follows:

Signed "sending" application $A$ generates and encrypts a private key $S$ using an attested hardware key.

Upon request from $A$, another "receiver" application $B$ sends $A$ its public key.

$A$ encrypts $S$ with $B$'s public key and then deletes its copy of $S$.

$A$ sends over this ciphertext to $B$, and now $B$ effectively has ownership of $S$ since there is some unspecified way of verifying that $A$ has really deleted its copy of $S$.

My question is how does the attestation of $A$'s deletion of its copy of $S$ work, and why can $B$ trust it? Additionally, how could this same scheme be replicated without the use of secure enclave hardware?

There is no cryptographic way to attest to the deletion of a key. Cryptography deals with mathematical properties of information. If someone knows the key, they have the key and that's that.
To have assurance that some information has been deleted, you need to use non-cryptographic means. The root of trust, i.e. the system that can provide the assurance you're looking for, needs to have several aspects:

You need assurance that the root of trust is protected, so that what happens inside the root of trust stays inside the root of trust. This can rely partially on cryptographic means, for example if the root of trust stores data outside the protection zone in encrypted form, but there has to be a non-cryptographic means of protecting the data encryption key. The assurance comes from the manufacturing process of the root of trust.
You need assurance from the root of trust that the information you're interested in was never shared with untrusted parties.
You need assurance from the root of trust that it deleted all of its copies of the information you're interested in.

In the real world, the root of trust typically consists of multiple parts:

The secure enclave hardware and firmware.
The manufacturing, provisioning and delivery processes of the secure enclave.
The software, running inside the enclave, that generates and later deletes $S$.

From the secure enclave manufacturer, you get a promise that the secure enclave preserves the integrity of the applications that it executes, and the integrity and confidentiality
of the data manipulated by the applications. Furthermore, the secure enclave contains a signature key which it uses to sign attestations, and you get the corresponding public key. An attestation is a promise about the state of the enclave, for example “Version 1.3 of ACMESecureKeyApp is installed”.
From the software manufacturer, you get a promise that the software doesn't share $S$ with anyone, and eventually deletes all copies of it. This promise is often delivered from an attestation coming from the software running in the enclave: the enclave sends a message “ACMESecureKeyApp 1.3 said ‘…’, signed, your secure enclave”, and ‘…’ is ‘I deleted $S$ securely’. You trust ‘I deleted $S$ securely’ because you trust the manufacturer of the software, and you trust “ACMESecureKeyApp 1.3 said ‘…’” because you trust the manufacturing and the chain of custody of the secure enclave.


Derive one public key from ECDH when the other and and the shared secret is known Suppose we have an elliptic curve Diffie-Hellman key exchange protocol, where Bob and Alice have public keys $pk_{Alice}= [sk_{Alice}]G$ and $pk_{Bob}= [sk_{Bob}]G$ ($[.]$ elliptic curve "exponentiation"). As usual, they computed the shared secret $s$ as the x-coordinate of $(x,y)= [sk_{Alice} sk_{Bob}]G$
Now Carol has access to $s$ as well as $pk_{Alice}$ and moreover knows a set of public keys $S_{pks}$, such that Bobs public key is in that set, i.e. $pk_{Bob}\in S_{pks}$.
Is it possible for Carol to find Bobs key in $S_{pks}$ (Assuming $S_{pks}$ contains more then just a single element of course)

Is it possible for Carol to find Bobs key in $S_{pks}$

This is a decisional Diffie-Hellman problem.
We can summary this problem as: "we're given the values $G, aG, abG$, and a series of values $c_1G, c_2G, ... c_nG$, can we recognize $c_iG = bG$"
We can reword the problem as "assuming $H = aG$, we're given the values $H, (a^{-1})H, bH$, can we recognize $c'_iH = (a^{-1}b)H$"; with this rewording, this is obviously a DDH problem.
Hence, this problem is possible if the DDH problem is tractable; that is, if we're in a pairing-friendly curve, or if the group order has small factors, or the group order is small enough (or you have a large quantum computer handy).  If none of these are true, then it's believed hard.


Division of Point in Elliptic Curve: Getting Back Point Let $P=(x_p,y_p)$ be a point on elliptic curve $E (a, b) := y^2=x^3+ax+b$, for an integer $n$, there exists a point $Q=(x_q,y_q)=nP$ on $E (a, b)$.

If $(x_q,y_q)$ and $n$ are given, what is the algorithm to find  $(x_p,y_p)$?

If possible provide code for python.

With Elliptic Curves, we can compute the order of any point (and, in particular, the point $nP$; this is especially easy on the curves we actually use for ECC, because those curves typically have an order $hq$, for a small $h$ and a large prime $q$ (and the order of any point is a divisor of $hq$).

So, if $q$ is the order of the point $nP$, and if $n$ is relatively prime to $q$ (since we generally have $q$ prime in practice), we just compute $n^{-1} \bmod q$; we then have $(n^{-1} \bmod q)nP = P$; that is, multiplying $nP$ by the scalar $n^{-1} \bmod q$ gives us back the original point.


Cipher Feedback Mode I can't understand what CFB really is. It said in Wikipedia that CFB is same as CBC, but I find that CFB is more difficult than CBC.

Can someone explain to me how CFB works. Such as how Initialization Vector(IV) work inside the Encryption Algorithm process together with the Key, and also how does the ciphertext message working to the next block cipher encryption.

And also my other question, is it okay to to use CFB with AES? I am confused because the plaintext message should enter AES algorithm to encrypt the plaintext message, but here in CFB, only Initialization Vector and Secret key will permuted by the block cipher.

Here is my another issue with CFB:

  "To use CFB to make a self-synchronizing stream cipher that will synchronize for any multiple of $x$ bits lost, start by initializing a shift register the size of the block size with the initialization vector. This is encrypted with the block cipher, and the highest $x$ bits of the result are XOR'ed with $x$ bits of the plaintext to produce $x$ bits of ciphertext. These $x$ bits of output are shifted into the shift register, and the process repeats with the next $x$ bits of plaintext. Decryption is similar, start with the initialization vector, encrypt, and XOR the high bits of the result with $x$ bits of the ciphertext to produce $x$ bits of plaintext. Then shift the $x$ bits of the ciphertext into the shift register. This way of proceeding is known as CFB-8 or CFB-1 (according to the size of the shifting).

  In notation, where $S_i$ is the $i$-th state of the shift register, $a \ll x$ is $a$ shifted up $x$ bits, $\operatorname{head}(a, x)$ is the $x$ highest bits of $a$ and $n$ is number of bits of IV:

  $$ \begin{aligned}
C_i &= \operatorname{head}(E_K (S_{i-1}), x) \oplus P_i \\
P_i &= \operatorname{head}(E_K (S_{i-1}), x) \oplus C_i \\
S_i &= ((S_{i-1} \ll x) + C_i) \bmod 2^n \\
S_{0} &= \operatorname{IV} \\
\end{aligned} $$

  If $x$ bits are lost from the ciphertext, the cipher will output incorrect plaintext until the shift register once again equals a state it held while encrypting, at which point the cipher has resynchronized. This will result in at most one blocksize of output being garbled."

I can't understand the formula and also what is the use of shift register. Can someone help me?

Well, with CFB mode, the encryption process is "take the most recent ciphertext block, pass it through the block cipher, and then exclusive-or that with the plaintext block to generate the next ciphertext block".  As for the IV, that's used as "the most recent ciphertext block" when encrypting the first plaintext block (where you don't have a most recent ciphertext block yet).

Now, the advantage that CFB brings to the table is error recovery, including errors that add or delete ciphertext blocks.  That is, is a ciphertext block is garbled (or a block is inserted or removed), the corresponding decrypted plaintext block and the one after that is also garbled; however, after that, the decryption process resyncs, and then it decrypts the rest of the text correctly.  Now, CBC also has this same property in regards to entire blocks; however, if you take the last 128 bits of ciphertext, encrypt that, and then use (say) only 8 bits of each AES block output, and exclusive-or that is 8 bits of plaintext to form the next 8 bits of ciphertext, well, now you have something that is resilient against changes that inserts or removes individual bytes from the ciphertext (at the cost of having to run the block cipher N times to encrypt N bytes).  Nowadays, this is not considered relevent (we generally want to encrypt and MAC entire messages, and if anything was changed, we reject the entire message); historically, this was considered a nice feature if (say) you were encrypting data going over an RS-232 interface (which really could add/drop individual bytes).

The other advantage that CFB mode has (over, say, CBC) is that the decryption process also uses the block cipher in encryption mode; depending on how different the block cipher encryption and decryption is, this can be convienent.

Now, as for your questions:

As to the relationship between CBC and CFB; well, they both perform the same general process, they both take iteratively exclusive-or in the next block of plaintext, and then run that through the block cipher.  How they differ is where they pull the ciphertext from; CBC pulls it after we run the internal state through the block cipher, CFB pulls it after we compute the exclusive-or.
Is it OK to use with AES?  Why, yes, AES works perfectly well with CFB.  As for your statement that "the plaintext message should enter AES algorithm to encrypt the plaintext message", why, that's not at all true; in Counter mode, the plaintext message doesn't go through the AES algorithm at all.  For CFB mode, for the very first ciphertext, yes, the plaintext doesn't enter the AES algorithm; however, for any other ciphertext block, we send the previous ciphertext block through it, and the previous plaintext blocks were used to compute the previous ciphertext block.


Cracking an RSA with no padding and very small e I have a project wherein I have to crack a given cipher text encrypted using RSA and have been given N and e. Can someone suggest an RSA attack using a very small exponent e(here e=3) and no padding?

If there is no padding, then you can try the following:

You can run an exhaustive search on the possible plaintexts. No padding means no randomness; encryption is deterministic, so you can "try" plaintexts and see if one matches the encrypted value when encrypted.
Without padding, encryption of m is me mod n: the message m is interpreted as an integer, then raised to exponent e, and the result is reduced modulo n. If e = 3 and m is short, then m3 could be an integer which is smaller than n, in which case the modulo operation is a no-operation. In that case, you can just compute the cube root of the value you have (cube root for plain integers, not modular cube root).