Is client certificate mandatory for two-way TLS? In One-way Transport Layer Security (TLS), client who initiates the connection verifies the identity of the server or entity it is connecting to, but server not necessarily validates client identity.
In Two-way TLS connections, both client and server validates each other's certificate (public key) to achieve mutual authentication. The question here is, does the client necessarily send its certificate? What if the client sends a credentials (E.g token/API key) that the server knows and validates to verify the identity, is this not a mutual authentication and two-way TLS?  I do understand certificates are a better way of proving identity than token/secret.

Strictly speaking, there is no such specification as "two-way TLS". It is rather an informal expression. It means a TLS connection with mutual authentication based on PKI.
If you use anything else for client authentication, but not TLS/SSL certificates, then it is not a two-way TLS. I'd suggest to use other words, because improper wording leads to misunderstanding and wrong expectations of all people involved: customers, developers, testers, auditors, etc.
To your questions:

does the client necessarily send its certificate?

Yes. Otherwise it is not a "two-way TLS".

What if the client sends a credentials (E.g token/API key) that the
server knows and validates to verify the identity, is this not a
mutual authentication and two-way TLS?

It is not a "two-way TLS". It does not mean that it is better or worse for particular purpose. It just means we cannot call it "two-way TLS".


What is most secure way for one party to encrypt 4 bytes in less than 40 bytes, which will be publicly available? I have a project where a user needs to store a U32 encrypted on a blockchain such that they can recover it themselves: the user will always have their key available but may "forget" the U32 value. No other party needs to decode the information, but the plaintext will eventually also be public on the chain.
The user has an entropy seed from which an infinite number of keys of any size can be deterministically derived. I was looking to using a single block of AES but it occurred to me that a simple XOR would also suffice. Assuming the user derives a unique "key" every time they perform this type of operation, is there any reason to do anything more complicated than that?

The obvious answer is to use a one time pad.  If you are truly using a unique random 4 byte key for each 4 byte block then it is provably secure.

The user has an entropy seed from which an infinite number of keys of any size can be deterministically derived.

The real problem is this "derived" randomness and how random it truly is.  I'm not aware of any infinite source of it.
With Salsa/ChaCha you could generate up 2^64 512 bit keys, each key being able to encrypt 16 different 4-byte blocks.  So I suppose infinite enough.
Users would need to seed it with a 320 bit key.  They need to change their their key after 2^68 (if my maths isn't wrong) encryptions. Using a setup similar to XChaCha allows you to extend this to 2^132.
In summary, if you have a cryptographically secure source of randomness you can just XOR.


What is proactive secret sharing scheme? In some papers, they just wrote that proactive secret sharing scheme is a secret sharing scheme which its shares are periodically updated. Does it have formal definition ?

Proactive secret sharing schemes are typically used for multi-party computation variously referred to as "Secure computation" or simply MPC that arose from the work of Yao and Goldreich, Micali and Wigderson (GMW) in the 80s.
MPC's require secrets to be shared among multiple parties, and some of these parties may be controlled by an adversary that is in the most general setting able to deviate from the specified protocol in a "byzantine" manner. As a concrete case, in the GMW protocol with $n$ parties, in order for the $i$th party to share its bit $b_{i} \in \{0,1\}$ with the other $n - 1$ parties, she generates $n - 1$ i.i.d uniformly random bits and sends one of the generated bits to each of the parties. She then sets her share of $b_{i}$ such that the sum of her share and the other $n - 1$ bits mod 2 gives back the original bit $b_{i}$. This sharing scheme is "perfectly" secure since there is no complexity assumption.
In the classic MPC model, it is assumed that the parties controlled by the adversary are determined beforehand and remain fixed during the course. This is sometimes called static corruption.

In the early 90s, Ostrovsky and Yung ("How to Withstand Mobile Virus Attacks", In PODC, pages 51–59) described settings where the adversary is allowed to control a varying number of parties throughout the computation and corrupt additional parties that may have been intact at the onset of the protocol. This is typically called dynamic corruption, and protos that are able to remain secure in this setting are sometimes called proactively secure. In this model, "proactive" security property stems primarily from the fact that secrets shared among the parties are periodically re-randomized through a sharing scheme, called a proactively secure secret sharing scheme (PSS).

I should note that the original Ostrovsky and Yung paper from 1991 does not explicitly use the term proactive secret sharing, but this term is used in a 2014 rework of the '91 paper ("How to withstand mobile virus attacks, revisited" by Baron, El-Defrawey, Lampkins and Ostrovsky [BELO14]). The "Block-Redistribute" aspect of the protocol forms the core part of the PSS scheme in the [BELO14] MPC, but it's presented as a specification rather than a formal definition. As such, I have not found a succinct formal definition for "proactive secret sharing". What you may ask for, on the other hand, is a definition of what it means for a MPC to be proactively secure rather than strictly a definition of the term "proactive secret sharing". If that's the case, the definitions in [BELO14] sec. 2.1 " The Proactive Model under the UC Framework" are helpful.


How can I use Weierstrass curve operations with a=-3 for implementing operations for a=0? I am working with golang's elliptic library.

It implements functions on Weierstrass elliptic curves with $a=-3$. I need to make my own library that allows me to handle curves with $a=0$. I understand there are specific equations to use to optimally perform operations on different elliptic curves, which can be found in Short Weierstrass curves.

I would like to know which functions from the library I should change, and which stay the same (as I'm not an expert in cryptography). Here is the full list:

IsOnCurve, affineFromJacobian, Add, addJacobian, Double, doubleJacobian, ScalarMult, ScalarBaseMult, GenerateKey, Marshal, Unmarshal, and some initialization functions.

As I understand I need to change the following:

IsOnCurve (removing the -3x)
doubleJacobian (different equation)
and the init functions

Those should stay the same:

Add
addJacobian (same optimal equation)
Double
ScalarBaseMult
Marshal
Unmarshal

And I'm not sure about those:

affineFromJacobian
ScalarMult
GenerateKey

Can anyone tell me if my list is correct, and if not, give me some feedback on how I should change the given items?

I have not thoroughly investigated golang's elliptic library (or Go at all), but I have implemented elliptic curves (with Jacobian coordinates) and I would say that your guess is correct. The "$a$" parameter is not used in the addition of two distinct points, but it appears in the formulas for doubling a point. With Jacobian coordinates, a normal implementation will include core functions such as addJacobian() and doubleJacobian(), which are used only through wrappers which filter out the special cases (if both operants to an "add" are identical, then it must be a "double"; if one operand is the point-at-infinity, then the result is the other operand).

The $a$ curve parameter is supposedly used when doubling a point, and when deciding if a point is on the curve or not (by applying the curve equation). It would also be used in point (de)compression, a kind of marshalling which saves a bit of space; but point compression does not appear to be implemented in the code you link to (it is optional and rumoured to be patented, which is why it is often avoided).

I am not entirely sure that the code is correct, though. In ScalarMult(), the multiplier is not reduced modulo the curve order, so an oversized value k could imply calling addJacobian() on a point and itself, something which does not appear to be handled in the code (this should be checked: if $n$ is the curve order, try $k = n+2$; this should yield $2G$ if the code is correct).


Thermal noise random I'm working with a Cortex M0 SoC that integrate an "RNG" (not specifically claimed as TRNG), that is however claimed to be "suitable for encryption". It works using thermal noise measurements.
Knowing the whole SoC retails for less than $10, my wonder is: if it is that good, why isn't it more widespread? In particular, why is it not available on the PC platform. I read that Intel used something similar, but it is no longer in use.
Since the whole RNG should probably be analyzed to determine if it's any good, my question is more like: "Can thermal-noise be used for a TRNG ?"

A true random number generator (TRNG) usually consists of two components: an “unpredictable” source with high entropy, and a randomness extractor — a function which, when applied to the source, produces a result that is statistically close to the uniform distribution. When the output of a TRNG is used for cryptographic needs, it is prudent to assume that an adversary may have some (limited?) influence on the distribution of the high-entropy source.

Thus it takes a bit of work to obtain randomness and there are many pitfalls.

If it's done well, the statistical randomness of the extractor’s output can be proven, and is not based on any unproven assumptions, such as the security of cryptographic hash functions. On the other hand output rates may be slow, and ensuring outside physical influences are thwarted may not be always possible. Obviously thermal noise in a circuit may be influenced by other factors.


Doubt about Shannon entropy Let's consider a random variable X that can produce the output $c$ with probability $1/4$. I was told that $-\log_{2}(\frac{1}{4})$ represents the number of bits needed to represent $c$. But, imagine that X can produce the output $c$ with probability $1/4$ and the output $b$ with probability $3/4$, then I only need $1$ bit to express $c$, for example, $0=c$ (and $1=b$). Why am I wrong?

Without proof or even a precise definition: when a random variable has independent outputs with $p$ the probability to output $c$, then an optimal encoding of the source's outputs (one that minimizes the expected number of bits consumed to encode all successive values of a large number of outputs, including order) will use on average $-\log_2(p)$ bit to encode the output $c$. For example, $-\log_2(\frac14)=2$ bit for $p=\frac14$, as told to the OP.

As noted in the question, it is possible to make a different encoding that only uses $1$ bit to encode $c$, and that's less than $-\log_2(p)$ when $p<\frac12$. But that different encoding will use more bits on average than an optimal encoding does, thus that observation does not contradict the statement in the previous paragraph.

For example, if the source outputs $c$ with probability $p=\frac14$ and $b$ with $p'=1-p=\frac34$, the encoding that outputs 0 for $c$ and 1 for $b$ requires $1$ bit per output, always, thus also on average. But it is possible to make a different encoding that consume less bits on average, down to the Shannon entropy of the source, which for two outputs is $-p\log_2(p)-(1-p)\log_2(1-p)\approx 0.81$ (see binary entropy function). An example of such encoding is to group outputs two by two, and encode as follows:
$$
\begin{array}{cc|l|cc}
\text{first} & \text{second} & \text{encoding} & \text{size} & \text{probability}\\
\text{output} & \text{output}& & s & q\\
\hline
b & b & \mathtt{0}   & 1 & \frac9{16}\\
b & c & \mathtt{10}  & 2 & \frac3{16}\\
c & b & \mathtt{110} & 3 & \frac3{16}\\
c & c & \mathtt{111} & 3 & \frac1{16}
\end{array}
$$

The probabilities $q$ sum to $1$, and it is possible to unambiguously decode a stream of bits output by this encoder.

The average number of bits for encoding two outputs is the sum of the products $s\,q$, that is $\frac{27}{16}$. The average number of bit per output is half that, that is $\frac{27}{32}\approx0.85$, which is less than $1$.

It's possible to prove that we can make encoders that arbitrarily approach the output bit per input symbol ratio of the Shannon entropy, but not encoders below that limit. It's also possible to rigorously define the average number of bits needed to represent an output value for a given encoder, then to show that this quantity must converge to $-\log_2(p_i)$ for encoders that approach optimality. That's involved, but we can at least justify that value.

Whatever sensible definition we give to the average number of bits $r_i$ needed to represent an output value $i$ for a given encoder, it must be such that we can compute the average number of bits produced by the encoder to represent an output of the source as $\sum p_i r_i$. We see that with $r_i=-\log_2(p_i)$, we get the standard formula for Shannon entropy:

$$S=-\sum p_i\log_2(p_i)$$

which justifies that in this formula, $-\log_2(p_i)$ is the average number of bits needed to represent an output value $i$. Which matches what the OP was explained.


Message authentication codes construction I was reading the paper $[1]$ and came across the scheme that I show below. While I understand the scheme well, I don't understand why they prepend a 0 to the block containing $r$ and a 1 to all other blocks. What is achieved by this? They never explain why they do it. Here is the scheme as presented in the paper:

$[1]$Bellare, Mihir, Roch Guérin, and Phillip Rogaway. "XOR MACs: New methods for message authentication using finite pseudorandom functions." Advances in Cryptology—CRYPT0’95 (1995): 15-28.

The short answer is:  They prepend bits in that way because the scheme is not secure without them.  While they might not explain it in English, their proof makes it clear where they use it.

Let us construct an attack against the scheme that does not prepend a bit to the blocks.  The same idea will work against a version of the scheme that prepends the same bit to every block.  In this version of the scheme, a tag for a single-block message $M\in\{0,1\}^{32}$ is $(r,z)$, where $$z = F_a(r)\oplus F_a(\langle1\rangle\| M).$$
Our attack will obtain about $2^{32}$ tags for an arbitrary single-block message $M$, stopping
if it ever gets a tag $(r,z)$ such that the upper $32$ bits of $r$ are equal to
$\langle1\rangle\in\{0,1\}^{32}$ and lower $32$ bits are not equal to $M$.  When it finds such a tag $(r,z)$, let $s\neq M$ denote
the lower $32$ bits of that $r$.  The adversary outputs a forgery on the message $M' = s$ with tag $(r',z')$ defined by
$$r' = \langle 1\rangle\| M \quad \text{ and } \quad z' =z$$  This tag will verify with message $M'$ because
$$z' = z=  F_a(r)\oplus F_a(\langle 1 \rangle\|M)= F_a(r')\oplus F_z(\langle 1 \rangle\| M'),$$
where the second equality uses the fact that our $r$ is equal to $\langle 1\rangle\| s = \langle 1\rangle\| M'$ (it switches the order of the arguments to $\oplus$).  Moreover, our adversary never queries the message $M'$ and one can verify that it will get the needed $r$ with good probability in about $2^{32}$ tries, so it will win the security game.

The intuition is that prepending the bits prevents this sort of thing from happening.  Specifically, this adversary found a way to force the verification algorithm to treat a previously used $r$ as a message, which can't happen with their domain separation strategy.


Raw signature of public key vs full certificate I'm working on an device that will have its own keypair to sign data that it acquires. The public key will be signed with a provisioning key to ensure authenticity of the device. I want to put the public key in a QR code printed on the device, as well as the signature by the provisioning key. If I use a regular X509 certificate structure the barcode gets really huge. Are there any pitfalls or really good reasons not to just put the public key and signature - base64 encoded - instead?

X509 certificates contain a lot of additional (management) data that is required to manage the PKI. If you do not require interoperability, you do not need this extensive structure. However, you might want to go through the basic fields of an X509 certificate and think over if you really do not need each of these fields. E.g., you might want the ID of the device signed together with the public key. You also might want a validity period assigned to a key pair and so on. You could also have a look at WAP or CVC certificates. These are more compact than X509 certs.


Why are singular "elliptic" curves bad for crypto? Consider the algebraic curve given by a short Weierstraß equation $y^2=x^3+ax+b$.

If $4a^3+27b^2=0$, then there are repeated roots of the right-hand side $x^3+ax+b$. How are these repeated roots bad for a discrete-logarithm-based cryptosystem?

When a Weierstraß equation $y^2 = x^3 + Ax + B$ over $\mathbf F_p$ has a null discriminant, then it does not define an elliptic curve: it is a singular curve. In that case, it means the polynomial $x^3 + Ax + B$ has a double or triple root $x_0$ and the point $(x_0, 0)$ is a singular point. All the non-singular points still define a group law with the regular construction as in an elliptic curve.

With a change of variable, you can always come back to these two cases:

$y^2 = x^3$, then there are exactly $p$ non-singular points and there is an efficient map to the additive group of $\mathbf F_p$ where the discrete logarithm is trivial.
$y^2 = x^2(x-1)$, then there are $p+1$ or $p-1$ points and there is an efficient map to the multiplicative group of $\mathbf F_{p^2}^*$ (which has $p^2 - 1 = (p-1)(p+1)$ elements) where the discrete logarithm is way easier to compute (but not as easy as the previous case).

In both cases it is very bad for crypto.


How can one sign with NTRU? I am looking at implementing NTRU, but I noticed that while the encryption/decryption algorithm seems to be mature and well-documented, there is comparatively little information about how to sign using NTRU (and the proposed method apparently leaks information about the private key).

My question is, why can't I just sign in the same way one would sign an RSA message, i.e. the sender "decrypts" a known quantity using his private key, so that the recipient can "encrypt" the signature and easily verify it? (With any required padding of course.)

Are there any flaws in doing this?

I'm Chief Scientist at Security Innovation, which acquired NTRU, and one of the co-authors of NTRUSign.

The difference between NTRUEncrypt and NTRUSign is in how they use the lattice. All the NTRU algorithms are based on solving the Close Vector Problem in a particular form of lattice known as an "ideal lattice".

For NTRUEncrypt, the encryption method is basically:

Select a random point in the lattice
Add the message to that point as a small perturbation.

Decryption is then a matter of mapping back to the lattice point and recovering the message by subtracting the lattice point from the ciphertext. This only works because the message is chosen to have a particular form that means that the mapping back to the lattice point will always work. Well, almost always -- you may have read about decryption failures in NTRU. These occur when the mapping back to the lattice point doesn't work, but we can control their probability. But hold this thought.

For NTRUSign, the signing method is:

Hash the message to a random point in space
Find a lattice point close to that hash point and publish it as the signature

Verification is:

Hash the message to the same point in space
Verify that the signature point is a lattice point and is close to the message.

So this is the difference between decryption and signing. Decryption only works on messages with a very specific kind of structure, the structure that's produced by encryption. For decryption, those messages come out of encryption, so it's not a problem. But for signing, the "messages" (actually hashes) come out of a hash function, and creating a hash function that has the right structure but doesn't allow just anyone to sign is very hard. The obvious hash function to use is one that maps a message randomly to the integer vector space containing the lattice, and for this hash function decryption wouldn't work at all.


Dangers of using CTR mode for encryption I know that it is never suggested to use the same key or key/IV pair twice for a stream cipher or for a block cipher operating in CTR mode. Filesystem-level encryption reuses the same key for a file when it is edited.

Would it be an okay idea or a bad idea to use CTR mode for such encryption? Would it require changing the IV upon each edit and re-encrypting to make sure it is secure?

From your question I'll assume that you do not plan to use strong means of authentication along with CTR encryption. If you do, the first point is invalid.

Never ever use CTR mode alone. If you use CTR mode alone (i.e. without authentication) you allow attackers bit level precision for changing files. This can result in very undesirable decryptions where important data was changed because the attacker knew the format, the position and the previous content.
Never ever re-use a nonce + key pair. If you do re-use a {nonce, counter} and key pair, you allow an attacker to perform a ciphertext only attack (the worst sort of attack imaginable) and the complete security of the system should break down. Note further that re-using the same counter at any space-time combination suffices.


Use $e$ in GGH as shared secret? I was wondering if we could construct a symmetric encryption scheme by assuming that the secret key itself in GGH is public and the shared "key" is the error vector $e$.

To encrypt we would take the lattice basis $B$ and our shared secret $e \in \mathbb{R}^n$ and do:

$c = m*B + e$

and to decrypt:

$m = (c-e) * B^{-1}$

Without the correct $e$ this should not decrypt correctly. But how could I attack such an encryption?

That wouldn't appear to work.  In a known plaintext attack, that is, where the attacker knows both $m$ and $c$, he can compute:

$$e = c - m * B$$

recovering the secret key.

Alternatively, in a ciphertext-only scenario, the attacker could take two ciphertexts $c, c'$ and compute

$$(c - c') * B^{-1} = m - m'$$

resulting in the difference between the two plaintexts.


How does blockmix in scrypt work? What is the meaning of the H function in scrypt? I am trying to understand how scrypt works. I am referring to the Algorithm section of scrypt's Wikipedia page. There I find this BlockMix function:

Function BlockMix(B):
    (B0, ... , B2r-1) ← B
    X ← B2r−1
    for i = 0 to 2r − 1 do
        X ← H(X ⊕ Bi)
        Yi ← X
    end for
    Output ← (Y0, Y2, ... , Y2r−2, Y1, Y3, ... , Y2r−1)

Now, as far as my understanding goes, this means: expand an r-bytes block into its single bytes, namely, B0, ..., B2r-1. Set X to the last byte, and propagate some perturbation by updating X with H(X ⊕ Bi). Finally return the output bytes, somehow shuffled (first the even, then the odds).

What I don't understand is the meaning of that H function. It's nowhere specified what it is. I guess it is a function that inputs one byte and outputs one byte. Is that a commonly known function? H usually stands for hash. Should I just pick any random bijection between the numbers in [0, 255]?

Anyone answering my question might as well consider to add this information to the Wikipedia page, to help the next reader.

I'll sum up the comments: according to the original paper, $H$ is any hash function which, ideally, uses limited parallelism$^1$, with Salsa20/8 being a candidate.

Footnote 1: In order to make the resulting memory-hard function less susceptible to attacks (which make an essential use of parallelism).


Does this PBKDF2-SHA1 payload hint at a cryptographic security issue? Blockchain first 16 encrypted bytes, IV, and iter_count – all encoded in Base64:

Yms6xqrzCfFsQadVZ5gQonMtnQAAAAAAAAAAAAAAAAAAAAAQJwAA69tYNg==

Does it looks like “correct” PBKDF2-SHA1 or does AAAAAA… indicate that something was broken?

During the login attemp to blockchain.info I get a response with a base64-encoded payload, that in fact authorizes my encrypted PBKDF2-SHA1 wallet. I have had no success trying to decrypt this (original BCI server/utils). I am absolutely sure that I’m using the correct passphrase (it's written on paper and was used successfully in 2016 and earlier 2017 before application update).

Anyway, the reason I’m asking if this looks like something suspicious and/or broken is that during my other analysis projects I never met a Base64 payload starting with 21 "A":

<Buffer 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 c6 aa f3 09 f1 6c 41 a7 55 67 98 10 a2 73 2d 9d f0 b0 39 32 ec e9 96 22 ab 2f 76 ff 6b 2b c5 c9 c1 5a ... >

When I compare that to my other newly created accounts, this seems to be a bit weird, since all other accounts produce payloads with a more random sequence at start… for example 3pV6yxnoKYKjj….

Do those 21 As in that one payload (related to one specific account) point to a security or cryptographic problem?

So lets take a look at this in hex:

626B3A C6AAF309F16C41A755679810A2732D9D 00000000000000000000000000000000 10270000 EBDB5836

This is bk: in ASCII, then 16 bytes of ciphertext, followed by an all zero IV, then a iteration count in hexadecimals : 10,000 (0x2710 in little endian), followed by what I presume is a 4 byte checksum or key check value.

So from a cryptographic standpoint this looks correct, unless an all zero IV is not acceptable.

Notes:

You cannot just start with character A when reading the IV. Byte boundaries for base 64 are within the characters for 3 out of 4 boundaries (or 5 if you count the one for the next byte). So you should always first convert the base 64 to hex.
Instead of 16 bytes of ciphertext I would expect 16 bytes of salt, used for the key derivation function. If those are random then it is alright to use an all zero IV, as the key would be different even if the same password is used; the random salt would make sure of that.


What is the Bilinear-map accumulator disadvantage Bilinear-map accumulator [1] is more efficient than the RSA accumulator [2] but do you know any disadvantage for the bilinear-map accumulator when compared to RSA accumulator?

I will list two disadvantages that come to mind.

A bilinear accumulator requires a public parameter which is linear in size, which means you need to have an upper bound on the number of data elements you would commit to the accumulator. The RSA accumulator requires a public parameter which is constant-sized.
A bilinear accumulator does not allow dynamic updates. If you have an accumulated digest $$A = g_1^{\prod\limits_{i=1}^N (s+d_i)}\;\;\; (s = \text{ the trapdoor}) $$ and need to insert a new element $d$, you would need to update the accumulated digest to $A^{s+d} = A^s*A^d$. But in order to compute $A^s$ without the trapdoor, you would need to know the coefficients of the polynomial $f(X):=\prod\limits_{i=1}^N (X+d_i)$. You would then compute the coefficients of $Xf(X)$ and use those to compute $A^s$. Thus, inserting a single element has a run time of $O(N)$.


Is Blake2b vulnerable to length extension attacks? There are very few resources for Blake2b apart from the official documentation and website. I would like to know if Blake2b is not vulnerable to length extension attacks unlike SHA2. I would like your help as soon as possible.

All from the BLAKE2 paper BLAKE2: simpler, smaller, fast as MD5
First of all

BLAKE2b is optimized for 64-bit platforms — including NEON-enabled
ARMs — and produces digests of any size between 1 and 64 bytes.

and from the abstract of the article

BLAKE2 is often faster than MD5, yet provides security
similar to that of SHA-3: up to 256-bit collision resistance, immunity
to length extension, indifferentiability from a random oracle, etc

The reason for the resistance to length extension attack
The countermeasure comes from the compression function. The last parameter is set to false when the processed chunk is not the last one.
Compress(h, chunk, cBytesCompressed, false)

It is set to true when the last chunk is compressed.
Compress(h, chunk, cBytesCompressed, true)

So, if an attacker tries to extend a hash, during the recalculation the verifier will arrive in a different hash value then the attackers provided.


Is it right about an example of bilinear map $e$? The equation for the elliptic curve is $y^{2} = x^{3} + x$ and is defined over the field $F_{q}$ for some prime $q\equiv 3 \pmod 4$, and set $q=307$. Choose random generator $g=[182, 240]$. My question is that how do I construct a bilinear map $e$ and compute $g_{1} = e(g, g)$?

The simplest construction that I know of is given in Section 6.9 of the book by Hoffstein, Pipher and Silverman (5.9 in the first edition). I also talk about it in Section 3.3 of this (but I do not claim that it matches the book's quality of exposition).

First, you need a prime $p$ with two properties:

You want $p\equiv 2\pmod 3$, this allows you to easily construct a supersingular curve over $\mathbf{F}_p$ (as $Y^2 = X^3 + b$ for any $b \ne 0$). Remember that a supersingular curve is one which has $p+1$ points.
You want $p+1$ to have a large prime factor, ideally $q = (p+1)/6$ should be prime. This allows you to pick a point of large prime order. In fact, it is best to first choose a prime $q$ of appropriate size, and then look for a suitable $p$.

For this example, I take $p = 587$ and $b = 1$. Then $q = (p+1)/6 = 137$ is prime, and the point $P = [332,103]$ has order $q$ on the curve $E$ with equation $Y^2 = X^3 + 1$ over $\mathbf{F}_p$. I note $E(K)$ the goup of points of $E$ with coordinates in $K$ ($K$ will be either $\mathbf{F}_p$ or $\mathbf{F}_{p^2}$.)

The basic tool is the Weil pairing, which I will note $e_q$. All you need to know about it is that it is a bilinear map from the group of $q$-torsion points of the curve (i.e., the group of points $P$ such that $qP = \infty$) to the group of $q$th roots of unity in $\mathbf{F}_p$ (i.e., the group of all $x\in \mathbf{F}_p$ such that $x^q = 1$). You can use many computer algebra systems to compute the Weil pairing, I use Pari/GP:

gp > p = 821;
gp > p%3
2
gp > isprime(p)
1
gp > q = (p+1)/6
137
gp > isprime(q)
1
gp > E = ellinit([0,1]*Mod(1,p));
gp > until(ellorder(E,P) == q, P = random(E));
gp > P
[Mod(332, 821), Mod(103, 821)]
gp > ellweilpairing(E,P,P,q)
Mod(1, 821)

However, the Weil pairing is not suitable as is for cryptographic purposes because it is also alternating, meaning that $e_q(P,P) = 1$ for all $P$, so we need to modify it. What we do is consider the curve as being defined over $\mathbf{F}_{p^2}$, and apply the Weil pairing in this curve. More precisely, it we let $\zeta$ be a primitive $3$rd root of unity in $\mathbf{F}_{p^2}$ (prove that it exists), then for any point $P = [x_P,y_P] \in E(\mathbf{F}_p)$, the point $P' = [\zeta\cdot x_P,y_P]$ is in $E(\mathbf{F}_{p^2})$. Moreover, if $qP = \infty$, then $qP' = \infty$ as well, which means that $P'$ can be an "argument" of $e_q$. Hence, finally, we define our "modified Weil pairing" $\hat{e}_q$ on the original curve (over $\mathbf{F}_p$) as follows: for a point $Q = kP$ (for some integer $k$), we let
$$\hat{e}_q(P,Q) = e_q(P,Q'),$$
where $e_q$ is the ordinary Weil pairing, but applied on the curve over $\mathbf{F}_{p^2}$. In practice:

gp > u = ffgen(p^2, u);
gp > until(z != 1, z = random(u)^((p^2-1)/3));
gp > E2 = ellinit([0,1],u);
gp > ellmodweilpairing(E,P,Q,q) = ellweilpairing(E2,P,[z*Q[1],Q[2]],q);
gp > ellmodweilpairing(E,P,P,q)
562*u + 172

We can see that this pairing is bilinear:

gp > Q = ellmul(E,P,99);
gp > ellmodweilpairing(E,P,P,q)*ellmodweilpairing(E,P,Q,q)
693*u + 108
gp > ellmodweilpairing(E,P,elladd(E,P,Q),q)
693*u + 108


Message Expansion / Encryption Blowup Factor / Ciphertext Expansion of ECC In order to complete the following table with asymptotic times and message expansions,

$\quad \quad \quad \quad \quad \quad \quad \quad \quad$ RSA $\quad$ McEliece $\quad$ ECC

Encryption Speed $\quad \quad \; \; N^2 \quad \quad N^2 \quad \quad \quad N^3$

Decryption Speed $\quad \quad \; \; N^3 \quad \quad N^2 \quad \quad \quad N^3$

Public Key Size $\quad \quad \quad \;\; N \quad \quad \; \ N^2 \quad \quad \quad N$

Private Key Size $\quad \quad \quad \;\; N \quad \quad \; \ N^2 \quad \quad \quad N$

Message Expansion $\quad \; 1-1 \quad \; 2-1 \quad \quad \quad ?$

I need to find the message expansion of ECC cryptosystem, but I don't find a clear answer anywhere.

Can someone give me and explain the missing value in the table?

Thanks in advance.

OK, a short amendment to your table, "message-expansion" only applies to messages which are quite long and not trivial one-bit messages, because they'd have a much higher message expansion.

Secondly, RSA doesn't have an expansion of "1" because of constructions such as OAEP. Also note that plain RSA has no form of semantic security and only improved variants provide IND-CPA and IND-CCA2 security.

Thirdly, McEliece can do better than "2" and usually does, depending on the details, it should have something around 1.5 at worst, also see Bernstein's Post Quantum Cryptography book and this paper (PDF). Depending on whether you want IND-CPA or IND-CCA2 security, better results may be achieved.

And now finally for ECC using ElGamal. Note first that you can't encode arbitrary messages deterministically as elliptic curve points and thus you can't easily encrypt arbitrary messages using this method.
The rest can be seen from the description in which is stated that the output effectively is two group elements and as two group elements usually are twice as large as a single group element (the message), you get a message expansion of "2". Note also that plain ElGamal is only IND-CPA and not IND-CCA2 secure.


Elliptic Curve Cryptography I have been trying this for a while. But I couldn't get it. How can I determine the point of intersection of the tangent line at (0, 0) on the   curve  $y^2  + y = x^3 + x^2$ ?

The tangent line at point $P(x_1,y_1)$ is:

$\frac{\partial f}{\partial x}(x-x_1)+\frac{\partial f}{\partial y}(y-y_1)$

Solving differentials, we obtain:

$\frac{\partial f}{\partial x}=3x^2+2x$

$\frac{\partial f}{\partial y}=-2y-1$

For $x_1=0$ and $y_1=0$ we have:

$\frac{\partial f}{\partial x}=3x^2+2x = 0$

$\frac{\partial f}{\partial y}=-2y-1 = -1$

So, by the first equation, the tangent line at $P(0,0)$ is $-y$.

Now, to calculate the intersection point with the curve we need to solve the next equations system:

$-y=0$

$y^2  + y = x^3 + x^2$

That have two solutions:
$x=-1, y=0$ and $x=0, y=0$

So, the tangent line intersect the curve at $(-1,0)$ and $(0,0)$.


In what way is XXTEA really vulnerable? I'm looking at using the XXTEA algorithm to encrypt a small amount of data (say, less than 32KB) in the context of a software licensing algorithm. That is, we wish to make it difficult (not impossible) for our customers to forge (encrypted) license files of their own.

Our intent is that our software will read the encrypted license file when it starts up. It will decrypt it with a key that is embedded in the executable. The license file will be read from disk and decrypted. The results of the decryption are then copied into a set of C language structures that contain licensing information.

We are looking to create something that prevents casual attempts to defeat the licensing mechanism. We are not trying to create a system that stands up to someone willing to invest a significant amount of time and effort in defeating the system.

The encrypting algorithm I'd like to use is XXTEA, using the "clarified" code from the bottom of the XXTEA Wikipedia page without modification: http://en.wikipedia.org/wiki/XXTEA

Our Intellectual Property lawyer is questioning this decision. He claims that the algorithm is weak and that we should find a better one. I disagree, since there are other, simpler ways to defeat the licensing mechanism than launching a cryptographic attack on the license file data.

However, I'm not a cryptographer and so I don't know how to interpret statements like these:

  XXTEA is vulnerable to a chosen-plaintext attack requiring 2**59 queries and negligible work. See cryptanalysis below.

and

  However, due to the incomplete nature of the round function, two large
  ciphertexts of 53 or more 32-bit words identical in all but 12 words
  can be found by a simple brute-force collision search requiring
  2*(96−N) memory, 2*N time and 2*N+2*(96−N) chosen plaintexts, in
  other words with a total time*memory complexity of 296, which is
  actually 2**(wordsize*fullcycles/2) for any such cipher. It is
  currently unknown if such partial collisions pose any threat to the
  security of the cipher. Eight full cycles would raise the bar for such
  collision search above complexity of parallel brute-force attacks.

I would be grateful for any advice on the vulnerabilities and/or reasonableness of what we are proposing to do.

XXTEA (also known as Corrected Block TEA) is a block cipher with $128$-bit key and block width parameterizable to $n\cdot32$ bits for $n\ge2$. It is an Unbalanced Feistel Cipher making $q=6+\lfloor52/n\rfloor$ passes over the block, with $q\cdot n$ rounds each modifying $32$ bits of the block. The round function is a simple Add-Rotate-Xor function of two 32-bit words (one for $n=2$), which are the next and previous ones modified in the round.

In Cryptanalysis of XXTEA, it is presented a chosen-plaintext attack, making use of differential cryptanalysis, recovering the key with about $2^{59}$ chosen-plaintext/ciphertext pairs and work comparable to enciphering that amount of data, applicable when $q=6$, that is $n>52$. The article is not peer-reviewed, but the argument seems plausible to me, and I take this attack as a given.

The practical significance of the attack in the context of the question is very low. That's because there is no way the attacker can obtain even a tiny fraction of the required ciphertext from the original publisher, much less with chosen plaintext; thus the only way that even a huge improvement of the attack could be performed is by using some derivative form of the original software with its original key as an encryption mean. The assumed attacker then has the key right in the software it is trying to use, and can recover it by reverse engineering (like stepping execution). Given the tremendous number of encryptions necessary, the attacker must deeply optimize its software, thus will have no trouble to spot the key. Therefore, the only practical risk I can see of using XXTEA (rather then an unbroken symmetric cipher and operating mode) in the context of the question is a tiny one of image for the publisher: one could demonstrate that the software is using a broken algorithm.

There's an easy solution to that: repair the algorithm by increasing the number of passes, e.g. by changing to q = 6 + 52/n to q = 16 + 52/n in the source code. This single-character insertion is more than adequate to block any attack remotely similar to the existing one, with a much less than threefold reduction in performance, entirely acceptable in the context. Update: If we want to keep the original $32$ rounds for the minimum $n=2$, which motivate the constant $52$, we should make an extra change and use q = 16 + 32/n.

The question does not detail how XXTEA would be used in the licensing scheme: it is not stated in which direction the data transfer is, and if the goal is to protect confidentiality or integrity. I note that towards that later goal, enciphering the whole data as a single block with some fixed field (checked after decryption, and wide enough, say at least $10$ bytes) is sound, because changes in the ciphertext propagate everywhere in the plaintext. That would not be achieved using the more conventional approach of a fixed-block-size cipher in some operating mode like CBC or CTR.

I must point out that public-key cryptography can make sense in this context: it allows enciphering data to the publisher and verifying integrity of data from the publisher without any secret key on the customer side. This in turn enables things theoretically impossible with symmetric algorithms. In particular, even assuming that an attacker has a rightfully licensed software, and gains complete understanding of how the copy-protection works, it remains impossible to illegitimately activate an unmodified copy of the software on another computer, assumed to be distinguishable from the licensed one by some identifier(s), such as MAC address, disk serial number, volume ID, OS-supplied UUID. The best attacks would require modifying the software, or the APIs it uses to get the identifiers (which nowadays is often as easy as licensing the software in a virtual machine, then cloning that).

Update: I'm facing a reasonable diverging opinion, stating that "You should never ever use a cipher or a hash function, that has been broken in academic terms". I agree with that advise in general when defining a new system, and I do suggest to at least summarily repair the academically broken XXTEA rather than use it as is. But there are a few exceptions beside using deployed gear with a minor dent when the risk is acceptable (which is common and perfectly justifiable). One such exception is when using a cryptographic primitive outside the normal hypothesis of cryptography, in particular this cornerstone: the key of a block cipher is assumed secret. Here we are in software copy protection, and in that game the key is next to the hands of the adversary; that makes cryptanalytic resistance of secondary importance. What is much more important is that the code using cryptography is hard to locate and  circumvent, and that means one should avoid use of standard cryptographic libraries, or OS-provided cryptographic APIs. This is one of few cases where rolling one's own implementation of cryptographic code is justified; then, given the secondary importance of cryptanalytic resistance, the simplicity of XXTEA (combined with a static field anywhere in the plaintext for authentication purposes) is appealing compared to the complexity of AES-GCM, which in addition is arguably more likely to become practically vulnerable in the field due to a weakness in the TRNG or whatever is used for the initial value of the counter.


RSA: Recover e given factorization of N and plaintext/ciphertext pair Is there a way to recover the public exponent e (assume in this case it is in fact not public) used in an encryption if I know the following:

Factorization of N : p and q
one plaintext m and its encryption c = m^e mod N

Obviously I can just bruteforce if e is small, but is there a more elegant way? (or just assume e is too large to simply bruteforce)

If $e$ is a random number, then knowledge of the factorization allows us to reduce the recovery operation to:

$$(c \bmod p) = (m \bmod p)^{e \bmod p-1} \pmod p$$
$$(c \bmod q) = (m \bmod q)^{e \bmod q-1} \pmod q$$

Solving both these discrete log problems will give us enough information on $e$ to efficiently recover it.

Now, while solving these two subproblems is easier than factoring $N$, or recovering $e$ without knowing the factorization, it is still nontrivial.  If we assume that the RSA modulus was a 2048-bit key, then each of these subproblems is a 1024 bit discrete log problem; that's larger than any published result.

On the other hand, if we are allowed to assume that $e$ is small (but perhaps a bit larger than we can brute-force), there are more efficient methods than simply trying each possible $e$ value.  For example, using the Baby Step Giant Step algorithm, you can efficiently check all possible values $e < 2^{61}$ with $2^{31}$ modular multiplications, and a few tens of Gigabytes of disk space.  You don't even need to know the factorization of $n$ (however, it would make it a bit more efficient, as that would allow you to compute everything modulo $p$)


Book request about elliptic curves, RSA and DSA I understand that this question can be hardly downvoted, but so be it if someone gives me really useful references :)

I wanna learn difference (deeply) between RSA, DSA, and ECC, especially I am interested in ECC and its application in GPG and SSH protocols, I googled some MIT courses but they seem too brief for deep understanding, so, please advice :)

Aim: I wanna make some research on topics to become a skilled person in this area.

This is an excellent resource that covers those topics: http://www.crypto-textbook.com/. And here's a channel that follows the book.


How many queries can you do (concretely, not asymptotically) for a balanced Feistel network with 7 rounds? In this paper Patarin says that:
"for every $\epsilon > 0$, when $m \ll 2^{n(1 - \epsilon)}$ ... for 7 rounds or more it is secure against all adaptive chosen plaintext attacks" where m is the number of queries that the adversary can evaluate.

What concretely is meant by $m \ll 2^{n(1 - \epsilon)}$?

For instance, to have statistical security $2^{-\sigma}$ (e.g. $\sigma = 40$) concretely how many queries can be evaluated?

The linked paper is missing a lot of proof details. In any case, it seems impossible to say anything concrete for finite $n$ due to the existence of terms in $O(\cdot)$ notation in the bounds. You simply do not know how large those implied constants are.


Best practices when encrypting a file with three different ciphers I have some files that contain important information, so I want to encrypt them by the most secure encryption method possible.

I've read countless StackExchange answers on similar questions and some Wikipedia articles about different ciphers, cryptoanalytic attacks, bad software implementations, cipher modes, etc. Google searches have not helped me in deciding which cipher mode is best, as this may depend on other factors that I will choose in my encryption process.

Having realized that one bad choice when encrypting a file may lead to failure, I want to describe my encryption process and have someone review it for anything that might weaken the encryption.

I do understand that it's impossible to brute force a cipher like AES256, Twofish (256-bit version), or Camellia256--in any practical length of time, according to academic consensus. With that said, I don't want the security of my files to depend on the soundness of a single cipher. Therefore, even if a vulnerability were to be found in one cipher, say AES256, my files would will still be protected by another.

By using multiple ciphers to encrypt my files, I know that I may not be increasing the security of the encryption against brute force per se; rather, I want to increase the security of the encryption against the future failure of a single cipher.

The following may be important in determining things like encryption order, encryption modes, etc.

Process:

1) I will be using GnuPG, and the ciphers I trust are AES256, Twofish (256 bit), and Camellia256, in that order.

2) There will be about 10 or 20 files, but I'm not sure yet. All the files are less than 1MB, and some only contain a few words/passwords, etc.

3) Since GnuPG can't encrypt a whole folder, I will need to compress the folder containing my files to a tar.gz file.

4) I will then encrypt this tar.gz file this way:

Enc1=Encrypt(TarFile, Camellia256, Passphrase1)

Enc2=Encrypt(Enc1, Twofish [256 bit], Passphrase2)

Enc3=Encrypt(Enc2, AES256, Passphrase3)

Questions:

I) Does the amount of the encrypted data matter? If so, what are the minimum and maximum sizes for the encrypted data?

II) Should I add some trivial data to the folder that I want to encrypt, like some random .png or .mp3 files, to avoid the cipher leaking some plaintext data?

How about when I encrypt the Enc1 file, should I add some trivial data to it before encryption?

III) Since I have to compress the folder that contains all the files to be able to encrypt it, does this weaken the encryption in any way? If this is the case, since I can't encrypt a folder without first compressing it, is there a solution?

IV) Knowing that I trust the security of the ciphers in this order--AES256 > Twofish (256 bit) > Camellia256--which one should I encrypt with first and which should be the last?

V) Since I will be encrypting using these three different ciphers, is it important to use different passphrases for each encryption?

VI) Knowing that I will only use ANSI characters--this includes alpha-numerals, lower and uppercase and some special characters--what is the minimum size of the passphrase that I should use? Is there a maximum size for the passphrase past which it will be less secure like in some kind of overflow? Can I use 100 characters? How about 1000 characters?

VII) Knowing all of this information about the data that I want to encrypt, and that I value security over speed, which commands/options/flags should I use with GnuPG to encrypt my files for each cipher to offer the best security possible?

I) There is no minimum. Maximum in your case is $2^{64} * 16$ bytes with same key.

II) No. No. GnuPG takes care of that.

III) No. Compressing does not weaken encryption.

IV) I don't think it matters because it is not authenticated encryption.

V) Yes, passphrases must be different.

VI) In your case you can get maximally 256-bits of security per cipher. You should use around 50 characters (depending on complexity) per passphrase. More does not hurt.

VII) I don't think you can tweak anything. It is "best security" by default.

It is important to note that GnuPG does not authenticate files encrypted with symmetric encryption, which means you cannot detect, if it has been modified.

You can read more about cascade encryption here: https://blog.cryptographyengineering.com/2012/02/02/multiple-encryption/


A simple block cipher based on the SHA-256 hash function I've come up with this little routine for doing encryption using the SHA-2 (in this case SHA-256) hash function. As such it is a block cipher with a 256 bit (32 byte) block size and an arbitrary key length. It's easy to see that you could replace the hash function and get an entirely new type of algorithm.

I want to know if there are any problems, especially flaws, in this construction, and whether algorithms of this type have been studied.

Initialization with key:

$$ S_0 = H(k) $$

Encryption for plaintext blocks $P_1, \dots P_n$:

$$ S_i = H(S_{i-1})$$
  $$ C_i = P_i \oplus S_i $$

Decryption for ciphertext blocks $C_1 \dots C_n$:

$$ S_i = H(S_{i-1})$$
  $$ P_i = C_i \oplus S_i $$

Here is some sample C source code using SSL:

#include <openssl/sha.h>

struct sha_crypt_state {
    unsigned char digest[SHA256_DIGEST_LENGTH];
};

void sha_crypt_set_key( sha_crypt_state *state, unsigned char *key, int key_length )
{
    SHA256( key, key_length, state->digest );
}

void sha_crypt( sha_crypt_state *state, unsigned char *block )
{
    sha_crypt_state temp;
    SHA256( state->digest, sizeof(state->digest), temp.digest );
    memcpy( state->digest, temp.digest, sizeof(temp.digest) );

    for ( int i = 0; i < sizeof(state->digest); ++i ) {
        block[i] ^= state->digest[i];
    }
}

void sha_crypt_test()
{
    const char *key = "secret";

    // prepare a test block
    char block[SHA256_DIGEST_LENGTH];
    memset( block, 0, sizeof(block) );
    strcpy( block, "Hello, testing encryption!" );

    // test encrypt
    sha_crypt_state state;
    set_key( &state, (unsigned char *)key, strlen(key) );
    sha_crypt( &state, (unsigned char *)block );

    // test decrypt
    set_key( &state, (unsigned char *)key, strlen(key) );
    sha_crypt( &state, (unsigned char *)block );
}

First of all, this no block-cipher at all. It's a stream-cipher. Thus you can use every key only once, and you can't use any cipher modes built on block-ciphers.

Your scheme is vulnerable to a known plaintext attack. If the attacker knows 32 aligned(or 63 unaligned) bytes of plaintext, he can calculate the state of your cipher:

$ S_i = P_i \oplus C_i $

The later $ S_j (j>i) $ only depend on the $ S_i $ the attacker recovered, i.e. he can calculate all of them. And thus he can decrypt everything that comes after that known plaintext.

Such a plain text attack is often possible in practice. Files often start with known magic bytes, network protocols often contain known sequences in headers (http headers should be long enough),...


How should we interpret the cryptanalysis results of SIMON and SPECK? The NSA recently released SIMON and SPECK light weight block ciphers. Although initial spec release did not have much of cryptanalysis details, two works later appeared providing the cryptanalysis for the same SIMON and SPECK.

But how should we interpret those results? Are they considered good or bad?

For example:

Attack complexity of key-recovery attack for SPECK32/64 is it requires $2^{29}$ plain texts…
Is that good or bad?
Rectangle attacks need $2^{30}$ plain texts…
Is this good or bad?

Let's first get something out of the way. You say ".. key-recovery attack for SPECK32/64 ..". This is not true. The cryptanalysis you linked attacks SPECK32/64 with 10 rounds. This is less than half the amount of rounds used for SPECK32/64.

Then onto your actual question, is $2^{29}$ chosen plaintexts a good or a bad attack? I can't decide that for you, but I can give you an idea. SPECK32/64 uses a block size of 32 bits, or 4 bytes. This means that after encrypting 2.1 GB of plaintexts your key could be recovered.

Whether that is deadly for security or not is up to you to decide, not me.


Where is defined the fact of having a "learning" and "challenge" phase in cryptography proofs? I've read Bellare and Rogaway 2004 and Shoup 2004 about game-based cryptography proofs, but I lack precisions about how should be built the "learning" and "challenge" phases, since my games will probably have this structure.

And what are they suppose to provide anyway ? Security against Adaptive adversaries ? The games I have read are like:

learning phase: do whatever you're allowed to do
challenge phase: submit two challenge sets, read what the oracle send you back and guess which set has been chosen

Yet adaptive adversary should mean (citing wikipedia) ciphertexts may be chosen adaptively before and after a challenge ciphertext is given to the attacker

thanks for explanations and/or links

You're confused about a few different things here. Assume that you have some cryptographic concept and you need to write down a definition of security. Such a definition can typically be written down as a game. When you write down your definition, you consider what the adversary should be able to do, i.e. it's while writing down the game that you assume whether you want active adversaries or not. This will be reflected in the operations that you allow the attacker to do, i.e. what the oracles will be.

Once you have written down the games themselves, then you typically prove bounds for an adversary being able to distinguish between the games assuming some bound on the number of oracle queries. At this point you don't distinguish between the type of adversary. The adversary can do anything that the game allows.

As an example, assume you have a security definition where you want the attacker to get access to $n$ ciphertexts corresponding to some plaintexts $p_1,\ldots,p_n$. If you want a non-adaptive adversary, you define your game to contain an oracle that will take as input $n$ plaintexts and which will return $n$ corresponding ciphertexts and allow only one query. If you want an adaptive adversary, then you would provide a single oracle that takes a plaintext and returns a ciphertext, but which allows itself to be queried $n$ times.

You might then wonder where real world computational limits fit in. What you normally prove is that if you can distinguish between two games, then you can construct an algorithm for solving say DDH or CDH. This reduction argument then links distinguishing the two given games to something you assume that can't be done and this will give you an estimate of how hard it should be to distinguish between the original games.


Random oracle based on SHA-256 I am given the following problem.

  Consider SHA-256 to be a random oracle in a practical application.
  Construct an (almost) random oracle $\{0,1\}^*→\{0,1\}^{3000}$ based on SHA-256.

Does it mean that the input is any length of zeros and ones and that is should hash to a value which is 3000 digits of zeros and ones? If yes, could I just apply SHA-256 12 times, splitting the input in 12 parts and remove 72 bits, then I will get 3000 bits? Or did I misunderstand?

Does it mean that the input is any length of zeros and ones and that is should hash to a value which is 3000 digits of zeros and ones?

Yes, that's the meaning of $\{0,1\}^*→\{0,1\}^{3000}$. It would be better to reformulate using the usual shortcut for "digits of zeros and ones": bits. Also, $\{0,1\}^*$ is the set of all bitstrings.

  Could I just apply SHA-256 12 times, splitting the input in 12 parts and remove 72 bits, then I will get 3000 bits?

$256\times12-72=3000$, thus you have the domains right. But would that be indistinguishable from a random oracle¹? No. Find how you would make the distinction. Then improve that construction. Ideally, make a proof that if a method could distinguish the refined construction from a random oracle¹, then it could be turned into a method making that distinction for SHA-256.

A random oracle with $k$-bit output is an hypothetical device that accepts a bitstring as input, and

if that bitstring was not previously submitted, draws and outputs a random bitstring in $\{0,1\}^k$
otherwise outputs the same bitstring as it did for the previous submission of the input bitstring.

¹ With no way to compute SHA-256, and perhaps disregarding the length-extension property of SHA-256, and its input length limitation; some or all of these might be what the question means with "(almost)".


XORing a header with SHA512-hash - secure? I am writing a application that encrypts text several times and stores the result. The result looks like complete random bytes, therefore I add some random bytes at the end. To let the program know where the real encrypted text ends I put an header at the beginning of the file. The header consists of 8 bytes: If $h$ is the header, then $h_0$ and $h_1$ are the magic numbers 0 and 204 (I have chosen this numbers randomly to check the file), $h_2$, $h_3$, $h_4$ and $h_5$ show the length of the text in as 32-bit integer and $h_6$ and $h_7$ are just completely random just to fill the header up to 8 bytes. To make the header look like random bytes (a program could find such files easily if I don't do that) I XOR the header-bytes with the SHA512-hash of the password. If the hash is $s$, then

$h_i = h_i \oplus s_i \oplus s_{i+8} \oplus s_{i+16} \oplus s_{i+24} \oplus s_{i+32} \oplus s_{i+40} \oplus s_{i+48} \oplus s_{i+56}$

That makes the file look like random bytes, but after all i think that this reveals information about the sha512-hash of the password, since at least 2 bytes of the header are known and 4 others can be predicted by looking at the size of the file. So this could help an attacker to find the password with a rainbow table, because even the magic numbers help the attacker to "eliminate" 65535 out of 65536 password-hashes (since the magic numbers are known, only 1 out of 65536 hashes will XOR the magic numbers to the bytes given in a file).

My question is: Is this way of securing the header really as insecure as I think it is and if so, how can I prevent this (I don't know  why, but I would prefer a method just with XORing and hashing)

Leaving text encryption and padding questions aside and focusing on the header stuff, here's how I'd approach the problem:

FileHeader = {
  BYTE Salt[16]  # Random bytes, K = KDF(Salt, Password)
  BYTE EncHdr[]  # EncHdr = AES-GCM(K, h0...h5)
}

Salt is a sequence of random bytes (it's there to prevent Rainbow table attacks)
EncHdr is the encrypted version of your current header containing magic bytes and length (you can store other information in there, too)
KDF is any key-derivation function, such as PBKDF2, crypt, scrypt, etc.

Now, if you don't want to use proper encryption and KDF, you can try this:

FileHeader = {
  BYTE Salt[16]  # K = HMAC-SHA512(Password, Salt), split K into (K1, K2)
  BYTE EncHdr[]  # EncHdr = Encrypt(K1, Header)
  BYTE MacHdr[]  # MacHdr = HMAC(K2, EncHdr)
}

So, instead of computing K = SHA-512(Password) you compute K = HMAC-SHA512(Password, Salt) and then split resulting 64-byte K into two 32-byte subkeys K1 and K2 (e.g. K1 is first 32 bytes of K and K2 is the last 32 bytes of K).

You then use K1 to encrypt header payload (magic and length) similarly to as you did before. After that you use K2 to authenticate encrypted data by computing HMAC.

Compared to your scheme, this one is (a) resistant to Rainbow tables (because salt is used to derive key in addition to password) and (b) protects from unauthorised modifications of encrypted header data by authenticating it.


I don't understand the definition of monotonic access structures I am very confused with definition 1 in section 2.1 of this article.

  Definition 1 (Access Structure [2]) Let $\left\{ P_1, P_2, ..., P_n \right\}$ be a set of parties. A collection $\mathbb{A} \subseteq 2^{\left\{ P_1, P_2, ..., P_n \right\}}$ is monotone if $\forall B, C : \text{if } B \in \mathbb{A} \text{ and } B \subseteq C \text{ then } C \in \mathbb{A}$.

Following to this post, why isn't $\mathbb{A} = \left\{ \left\{ 1, 2 \right\}, \left\{ 3, 4 \right\} \right\} \subseteq 2^{\left\{ 1, 2, 3, 4 \right\}}$ monotone?
Where do $B$ and $C$ come from? Are they both elements of $\mathbb{A}$? Are they any kind of sets? If yes, $B = \left\{ 1, 2 \right\}, C = \left\{ 1, 2, 3, 4, 5 \right\}$ would be true, but doesn't make sense, because $C$ is not an element of $2^{\left\{ 1, 2, 3, 4 \right\}}$, so it can't be an element of $\mathbb{A}$, too. But the definition above implies that.

It's for $B,C \in 2^{\{P_1, P_2, ..., P_n\}}$

So, take $B = \{1,2\} \in \mathbb{A}$ as in your example. $\forall C \in 2^{\{1,2,3,4\}}$ such that $B \subset C$, $C$ must be in $\mathbb{A}$.

Possible values of $C$ are $\{1, 2\}$, $\{1, 2, 3\}$, $\{1,2,4\}$, and $\{1,2,3,4\}$. As you can see not all of them are in $\mathbb{A}$.

The idea is that if any set has access, all sets that contain it must also have access.


Signature operations may leak the private key; signature verification should be safe? What does this warning mean:

  Signature operations may leak the private key. Signature verification should be safe.

A haskell cryto library displays the quoted warning above (see Crypto.PubKey.ECC.ECDSA) but I don't really grasp why they are producing that warning.

Can you please explain what this means (from a cryptographical point of view)?

The authors of the code also wrote:

  WARNING: Vulnerable to timing attacks.

They know their code can leak information thru timing of its operation. Therefore, they rightly wrote:

  Signature operations may leak the private key.
  Signature verification should be safe.

The first sentence is because, due to the aforementioned information leak, the confidentiality of the private key (which must be used to perform a signature, and should be kept secret) could be compromised during a signature generation operation.

The second sentence is because, in a signature verification, the public key is used, and that is not secret. Thus, information leak is much less of an issue, and can't compromise the confidentiality of a key. However, there are rare situations where the signature itself is deemed secret (say, because it can be reused); that might explain the use of "should".


How to encrypt the truth table in garbled circuits? I'm learning about garbled circuits, and I'm using the following tutorial: Yao's Protocol.

I have a questions regarding to construction (encryption) of truth table in garbled circuits.

Slide 14 says:

  For each wire x, y, z, specify two random values, corresponding
  to 0 and 1.

So I picked:

(k_x0, k_x1) = 1, 0
(k_y0, k_y1) = 0, 1
(k_z0, k_z1) = 1, 0

Then,

  We need to “associate” (k_z0, k_z1) with (k_x0, k_x1, k_y0, k_y1).

Here's my table according to the values in slide 16.

x | y | z | GCT
----------------
1 | 0 | 1 |  ?
1 | 1 | 1 |  ?
0 | 0 | 1 |  ?
0 | 1 | 0 |  ?

However, I can't figure out what should GCT values be?
How should those values be calculated?

Yao, encodes AND curcuit as;

the $x$ values as $k_x^0,k_x^1$,
the $y$ values as $k_y^0,k_y^1$,
the $z$ values as $z_k^0,z_k^1$.

Here the upper script represents 0 or 1.

\begin{array}{|c|}
\hline GCT \\\hline
  E_{k_x^0}(E_{k_y^0}(k_z^0))  &  \\\hline
  E_{k_x^0}(E_{k_y^1}(k_z^0))  &  \\\hline
  E_{k_x^1}(E_{k_y^0}(k_z^0))  &  \\\hline
  E_{k_x^1}(E_{k_y^1}(k_z^1))  &  \\\hline
\end{array}

Where $E$ is Symmetric Encryption Scheme, and in these schemes Block Ciphers can be utilized. One can use Asymmetric Encryption schemes but that will be slow, and non-standard.

so, given to keys, only one of the rows can be decrypted correctly.


Good Encryption Exponent I have placed a bet that I can create a public key such that my adversary will not be able to crack (decrypt) it for at least one week. For my primes $p$ and $q$, I chose very large numbers that are $101$ digits long, each. I also tried to make them to be as distinct as possible.

Now what I am wondering is whether to choose a big encryption exponent or a small one. Since I have began my study of Cryptography about a month ago, I am not too familiar with choosing a solid encryption exponent. I heard that choosing the digits $3, 5, 17, 257$ or $65537$ would give me a good security but I have not read about it. I was thinking of going with $257$ because intuition tells me that there exists a inverse relation between the two: when choosing large primes for $p$ and $q$, then pick a small encryption exponent and vice versa. But I don't know if this makes complete sense in some regards.

Any input is appreciated.

Factoring the modulus, by definition, does not uses the public exponent, just the modulus. In fact, it is easy to see that the public exponent has no impact whatsoever on security until it is actually used, e.g. something is decrypted or signed.

For the security of the algorithm (not just the key), it is not known whether a short public exponent induces extra weaknesses. Some people have feared it so, but in fact, for all we know, the shortest possible public exponent ($e = 3$) is as good as any other.

With some details:

All other things being equal, a short public exponent implies better performance of public-key operations (message encryption, signature verification), so that's a good idea.
Some widely deployed implementations of RSA cannot use public exponents which do not fit in 32 bits, so you need, for interoperability, to keep your public exponent short.
A short private exponent may induce trouble. If you want to force the private exponent to be short (and that's a bad idea) then you must allow the public exponent to be big (about as big as the modulus). So this is an argument for a short public exponent: it prevents the private key generation system from doing something tempting (for performance) but stupid (for security).
There is a widespread tradition of using $e = 65537$ and not $e = 3$, because of an old myth about a possible attack which does not actually apply to properly used RSA (see this for some details).

As has been pointed out, two 101-digit primes imply, in bits, a 670-bit or so modulus. It so happens that the current World record for a RSA modulus factorization is for a 768-bit integer -- and it took a lot more than one week (depending on how you look at it, it took between two and four years; and it included some heavy thinking by really smart people). So your bet is quite safe, provided that you did not botch the prime generation. In particular, sentences like this:

  I also tried to make them to be as distinct as possible.

make me fear the worst. The good way to generate the two primes is to generate both of them randomly with, as most as is feasible, uniform generation. A lot of well-intentioned "fixes" like the one you may allude to above can easily turn, in fact, into big weaknesses. You should refrain from that. Randomness is enough.

(Similarly, I hope you used a proper cryptographically strong source of randomness. And, more generally, just use some existing software like OpenSSL: this will be vastly easier and safer.)


In the reduction proof below, where OWF exists only if is a PRG. I am not able to understand the highlighted part I am able to understand how G(x) id generated. But then what is the use of variable z. Also if the probability is >1/2 + e then the distinguisher wins! Then how is this still a OWF

This is an example of proof by contradiction. If you have ever seen a proof that the square root of 2 is irrational, that probably used a similar logical argument. Our goal is to prove that $\mathcal A$ does not exist, but we do that by assuming it does exist and then deducing that something goes wrong. The place to pay attention is bullet 4 where we assume $\mathcal A$ exists; mathematicians and computer scientists could make life easier at this point by adding "SPOILER ALERT: It doesn't!". The next three bullets proceed from this assumption and at the end of bullet 7 the wheels fall off because, as you realised, we have constructed a case where the distinguisher wins and because we know that $G$ is a PRG this cannot happen. We go back to bullet 4 and realise that we must have gone wrong by assuming the existence of $\mathcal A$. We conclude that no such $\mathcal A$ can exist.
The variable $z$ is meant to represent a response to a challenge from the adversary. After that the proof shows how you can distinguish the response if you can lay your hands on $\mathcal A$ (SPOILER ALERT: You can't).


Certificate for the public key I am new to Network Security and learning about various security features like Diffie-Helmann and others.

I understand that the Public key send by the server to the client needs to certified that it is authentic. So, a Certificate Authority (CA) needs to sign the public key. But I would like to know how is this public key signed in the certificate. Using some private key? And if so, how does the client decrypt this certificate and finally get the public key of the server? For example: how does it work in case of a TLS handshake?

The certificate is not encrypted.  It contains signatures (basically hashes) that are encrypted with the private key.  The public key can decrypt that and the hash can be verified.  In SSL/TLS there is a signature that the client supplies via private key to prove they are the owner, and the CA has signed it the cert with their private key, which can be verified using a CA cert you mark as explicitly trusted.


Can homomorphic encryption filter? Often in articles homomorphic encryption is praised as the holy grail of encryption for cloud storage. This is done by suggesting that it can do any computation, and as such could be used for encrypted databases.

Performance issues aside, this makes me very sceptical. If such a database is to be any useful you need to be able to do queries. I understand how these work and how you could do the tricks needed to transform a query into a circuit.

However such a circuit only does a modification on the data, but it does not reduce it's size. In fact, the only way I see you can get the results is by executing the circuit and returning the entire modified database.

So is it possible for homomorphic encryption to actually filter and return a small encrypted subset of a larger encrypted database based on a query?

So is it possible for homomorphic encryption to actually filter and return a small encrypted subset of a larger encrypted database based on a query?

Sure it is. Say we have a database with (encrypted) test scores and student id and want to query the DB for the student with the highest score. Using FHE we can do comparison that for our purposes assume returns either 0 or 1.

students,scores = query()
high_student = encrypt(pk, 0) # encrypt with the public key
high_score = encrypt(pk, 0) # same

for student,score in (students, scores):
  bit = score > high_score
  high_score = bit*score + (1-bit)*high_score
  high_student = bit*student + (1-bit)*high_student

return high_student

This illustrates how you can filter as long as the number of returned results is fixed (not even necessarily fixed to 1). What if you wanted every student with greater than a 90%? I don't think that is possible with out returning something the same size as the entire table. this makes sense as you don't want your FHE to leak any information. That would leak how many values are greater than 90%.


How does HOTP keep in sync? My understanding of HOTP is that each password is unique and based on a counter.

$$PASSWORD = HOTP_1(K,C)$$

Where $C$ is an incremental counter.

What I wish to know, is how you keep the client and server in sync?  Looking at current systems (google authenticator), there appears to be no indication if the actual 'counter' number, but you can generate successive passwords at will.

What happens if, for example, the password you have generated uses $C = 5$, but the server is expecting $C = 3$?

Also, what is the 'integrity check' for?  Google cant seem to come up with a solution.

The HOTP standard describes the resynchronization algorithm (section 7.4). Basically, the server remembers the last value $C$ of the counter for which a correct password was presented. When a new password is to be verified, the server tries $C+1$, $C+2$... until one matches, or $C+w$ is reached for some $w$ called the "window size".

The intended scenario is the following: the client has a handheld device which outputs the successive passwords, one new password per button-press. The client may press the button a few times between two login attempts. The server "bets" that the client will not press the button more than, say, 100 times before attempting to log in again: so the server uses $w = 100$. If you let your 3-year-old nephew play with your HOTP device a whole afternoon, chances are that it will be too much desynchronized, and login will not work any longer.

The server wants to keep $w$ small, because:

The raw effect of $w$ is that, at any time, the server will accept $w$ possible passwords; the higher $w$ is, the higher is the risk that an attacker trying random passwords may log in.
The computational cost on the server in case of a wrong password is proportional to $w$.

but $w$ must not be too small, because a desynchronized device implies extra costs (more work for the help desk), which should not happen too often, even in the presence of hyperactive infants.

The RFC 4226 contains no instance whatsoever of the word "integrity" so I have no idea what your last question is about.


How to attack a classical cipher using known partial plaintext? I have a ciphertext generated by a classical cipher. I do not know what was cipher used to generate it. I do however have the beginning of the plaintext.

What are the cryptanalysis approaches for classical ciphers?
How do you suggest trying to recover the plaintext in this instance?
How can I leverage the known plaintext to attack the cipher?

I have this ciphertext:

  NUVRRIEZWBRVRFFAPUUKFVRYNQBCINHZKNETUVDVUMRTEANPAFIELBPOANIXLCMEZQETKDKVWBMNCTRVUMRFNTFDGWRUMCSCTHSGKDULRFCNABNCGSNMMGRFNTLOWQRBETZRMUBQYURFRFASANGPEQRFFAFCZACAZCTUBTHKUNEZHPPWSGPNABHZKZQNREANLCHUCZDLMLPUNTMNETDAUINQADUNSUMGETETHFBNMNNONTFBBPOQEMZPETEQUIDTHKNABKDZWBDBRZUSRASUMNIRARETETHFBZKRHPNQFAKRICMGETMULCTCULSLGBIVWBDBIEMUFCUVNUGPINFBQTMPNUMSRNNANTNANCMNNTFUMUKRILRFFAPUUKFVRYNTCMETNUVFWDABBRFNRIEFRFNTHGPUHPNKCILEGBUTWUSCPQSLMNIBWQINFBQTFAVRLCKRHKLZNFAZLSNTBDBEASTD

It begins with the partial plaintext:

  it turns out that


Construct Schnorr Protocol can only verify by designated verifier Currently I have a DLP as following, $y = g^x \bmod p$, I can easily construct a proof of knowledge by using Schnorr Protocol.

But I would like to put it a a system of 2 parties with public key and private key as following.

Prover has private key $x_p$ and public key $y_p = g^{x_p}$
Verifier has private key $x_v$ and public key $y_p = g^{x_v}$

Is it possible i can construct a proof of knowledge that prover knowing $x$ in $y = g^x \bmod p$ and only can be verified by designated verifier with public key $y_p$?

I try to add a trap door commitment to a non-interactive schnoor protocol. Trap door protocol provide a back door for selected verifier by public key.

Cryptography setup

$y=g^x$ where $r$ is the secret to prove
$y'=g^{x'}$ where $y$ is the public key of the verifier and $x'$ is the private key of the verifier

Construct the proof

Pick $w$, $r$, $d$ randomly in $Z_q$
$c=g^wy'^r$
$t=g^d$
$h=hash_q(c, t)$
$s=d + (h + w)x$
$(w, r, t, s)$ is the proof and send to verifier

Verification

$c=g^w y'^r$
$h = hash_q(c, t)$
verify $g^s = ty^{h+w}$

Simulating Transcript

Pick $\alpha$, $\beta$ randomly in $Z_q$
$c=g^\alpha$
$t=g^sy^{-\beta}$
$h=hash_q(c ,t)$
$r = (\alpha - w)(-x')$
$w = \beta - h$
$(w, r, t, s)$ is the transcript

Because of the trap door commitment, designated verifier ($y'$) can create a valid proof.
But only the designated verifier know the proof is come from himself or prover. For others, they can't tell the proof is come from designated verifier or prover. Only designated verifier or prover know the proof is created by who. So only designated verifier can be convinced in this protocol.

So this protocol, can convince designated verifier knowledge of r in Schnorr Protocol. The verifier can't transfer the proof to others and he is the only one can be convinced.


symbol representation based cipher? so i had an idea recently for a cipher. the idea is as follows: for every ascii character in the input, replace it with a corresponding sequence of 25 binary digits that, when arranged into a 5x5 grid, make an image that relates to the character. take the output binary sequence, and convert it back to ascii. the benefits i think this cipher may have are: only the sender and recipient of the info know what images correspond to what characters, therefore making it harder to guess, since the 25 digits don't line up neatly with bytes, the data of some characters will overflow to the next byte, making it not as obvious whats going on, and lastly, it can easily be combined with other ciphers to make even the decrypted binary arrange properly still look like meaningless gibberish. my question is, does it provide any real level of security to a message transferred between two people, assuming those trying to decipher it have no prior knowledge about the cipher? thank you. by the way this is as a followup to my previous question about the vigenere cipher, as something else to add security to it. link to the question here: trying to identify the key of a vigenere cipher via brute force

It sounds like a nice codebreaking puzzle, but little more than that.

If the encryption algorithm is known to the attacker, they can map each 5x5 binary grid to an arbitrarily chosen symbol (say, the number of distinct 5x5 grids seen in the message so far) and then solve it as a simple monoalphabetic substitution cipher e.g. using frequency analysis.
Note that this attack does not depend on the choice of the 5x5 pixel grid patterns in any way.  In practice, if the patterns are not chosen at random, the pattern chosen to represent each plaintext character might provide additional clues to the attacker.  But the generic attack described above works even if they don't.
(Using multiple grids per character and choosing between them at random would turn your scheme into a homophonic substitution cipher, which can be somewhat harder to break than simple substitution especially if the amount of available ciphertext is low.  But even homophonic substitution can be broken via statistical analysis if enough ciphertext is available, and even more easily if the attacker has access to at least some known plaintext.)

If the encryption method is not known to the attacker, it may take them some time and effort to figure out that the ciphertext should be converted to binary, laid out on (a multiple of) five lines and then each 5x5 grid of bits should be treated as one character.
However, assuming that the ciphertext is long enough to contain at least some repeated grids, the method you describe will leave statistical patterns that will be very obvious if the ciphertext is analyzed in binary (e.g. an unexpectedly low number of distinct groups and an unexpectedly high serial autocorrelation when the ciphertext is divided into 5-bit groups) and still apparent to some extent even if it's analyzed e.g. as 8-bit bytes (since e.g. the number of distinct 5-byte / 40-bit groups will still be lower than expected of a random byte sequence).
Also, assuming that the attacker doesn't know the encryption algorithm violates Kerckhoffs' principle, and is considered an unsafe assumption in modern cryptography, as it's hard to prevent such secrets from leaking (you've just leaked your algorithm by posting it here!) and even harder to restore the security of a system after a leak (since a completely new and unrelated algorithm would have to be devised, analyzed and communicated to all parties).  Instead, secure encryption schemes in the modern sense all feature a key of some kind, such that the system remains secure even if the attacker knows everything about it except the key, and such that the key can be easily changed if it's compromised.
While your scheme does have a "key" of sorts, in the choice of 5x5 bit grids to represent each character, this key does not offer much security since, as noted above, there are efficient generic attacks on monoalphabetic substitution ciphers (which yours effectively is, once the obfuscation layers are removed) that an attacker can use to find the key.  Thus, any additional security your cipher offers beyond that of a simple substitution cipher is based entirely on its non-keyed obfuscation elements, and would thus be considered worthless in a modern security analysis.


Will a SHAKE128 stream cipher be vulnerable to related key attacks? Suppose that SHAKE is seeded with key concatenated to an IV, will the 'key' stream produced by SHAKE128 vulnerable to related key attacks like RC4 is?

My guess is no because seed is already "absorbed" before the key stream is "squeezed" out.

There is no way to know for sure, but it seems unlikely to me.

SHAKE128 is an extendable output function, basically a hash function with variable output. It must be secure with completely attacker controlled input. If you use it to build a stream cipher (perhaps using KMAC (draft pdf), which is supposed to be PRF), it seems unlikely that related keys would be a concern without the hash function use case also being broken.

However, the security goals of hash functions and stream ciphers are different and SHA-3 itself could be broken, so only time will tell.

  My guess is no because seed is already "absorbed" before the key stream is "squeezed" out.

This particular argument does not really make sense, since RC4 also absorbs the key first and only then produces output. Yet it is vulnerable to related key attacks.


Relation between encryption algorithms and (password) hash functions This is a really basic question.
Blowfish is not seen as a secure cipher.
but bcrypt is one of the most secure hash functions.
So first: How can a hash function be based on an encryption algorithm, after all these two things have little to do with each other?
Second: If blowfish is insecure and bcrypt is based on it, how can it be secure ?
And just a little question regarding bcrypt: In Linux-based operating systems the code for hashes is

 $1 – MD5
$2 – blowfish
$2a – eksblowfish
$5 – SHA-256
$6 – SHA-512

With "blowfish" they actually mean bcrypt, right?

This is just a sketch of the idea but I think the reasoning is as follows:

The output of a good block cipher looks random so you can think of a block cipher as a PRF.
If you have a PRF you can do simple things like throwing away half of the output to turn it into a compression function.
Hash functions are traditionally built from such compression functions. Usually in a Merkle-Damgård construction.

Clearly the security of the Hash function depends on the security of all these building block and the precise steps taken in between.

Even if blowfish may have weaknesses it is possible that the output still has sufficient entropy that it can be turned into a good compression function. Note that according to Wikipedia the problem with blowfish is its small block size which doesn't affect the PRF property.

EksBlowfish is a step of bcrypt. As described in the publication.


Enigma: a Question from WW2 I have seen in the Imitation Game that the Germans reset the Enigma at midnight sharp, and then they start messaging by sending the weather report in the morning.

But the device made by Alan Turing, the Christopher, sometimes only took a few minutes to decode Enigma.

How did the German receiver know the settings of the machine? I thought that they may be sending the next day's setting at midnight, but if they were compromised once, the enemy would know all the next day's settings too.

So, how did they do it?

The simple answer is also part of one weakness with all encryptions that use symmetric key, AKA pre-shared key. Key sheets that lasted 31 days where generated and sent out by courier or so. The weakness is ofcourse that if the enemies get their hands on it then they can read all the messages that used that key.
And yes - sometimes the allied did get their hands on a key sheet and then they had the keys for one network for up to a month.


Comparison among algorithm based on key length Some months ago I found in some paper that we cannot compare symmetric algorithm with asymmetric algorithm based on the key length and more important we cannot compare asymmetric algorithm using only the key length, while a comparison of only symmetric algorithm in this term is reasonable... I explained it basing on the fact that:

in symmetric encryption algorithm the key length identifies the number of attempts necessary to decrypt the communication in both way, while in asymmetric encryption we are not sure that for a key of n bits, we will use all the possible numbers, so using ONLY  the key length as a term of comparison is not sufficient, we could have key of 300 billion of bits but available only 2...

My question so is: is it true that all the possible symmetric algorithm uses all the possible numbers of n bits as possible keys or among these there are some of that not usable?

Thanks

Usually we only consider those keys, we can actually use. There is no restriction about the bits in a symmetric key, you can use all of them. For asymmetric encryption schemes, both keys need to fulfill some constraints to actually work. For example:

In RSA, $e$ has to be chosen coprime to $\phi(n)$, and you need $ed=1 $ mod $\phi(n)$0. What does it mean? Yes, there are certain values of $e$ (and $d$) which do not work.

edit: Even numbers never work, because $\phi(n)= (p-1)(q-1)$ is always divisible by 4. Other than that, the fastest way is to pick a random odd number for $e$, and check if it is coprime to $\phi(n)$.

What the reason is, that we can not blindly compare bit sizes of keys, is that attacks on symmetric and asymmetric encryption schemes are fundamentally different. It is a bit like comparing apples and oranges. So a 200 bit symmetric key is just something different than a 200 bit asymmetric key.

However, there are heuristics (not proven) to compare the strengths of these keys. For example NIST provides information about that here.

A very good read is Universal security; from bits and mips to pools, lakes -- and beyond, which tries to accommodate the the irritating scale of bits in a humorous way.


breaking one-time pad with key reuse Suppose I have the message $m_1 = \sf{i\ like\ dogs}$.

Suppose its one-time pad encryption with key $k$ is a given hexadecimal string of 22 characters.

How would I encrypt a message $m_2 = \sf{i\ like\ cats}$ with the same key $k$?

I was given a similar question (but with different messages). Firstly I observed that the hexadecimal ciphertext had twice the character count than the message, so I thought each message character was mapped to a hexadecimal string of 2 characters.

My problem is that I don't know how would the $\oplus$ of the one-time pad work in this situation (as the message is not binary), so I couldn't guess the key. Any idea on how this should work?

It's fairly simple.  1st byte of $k$ in pseudo code is:-toAscii("i") XOR toBinary(1st hex pair). ASCII code of "i" = 105 as an example. Then repeat for the remaining bytes to obtain all of $k$.

See ASCII and Hexadecimal for reference.


Encrypting documents through a proxy key Suppose I'm developing an app to secure a lot of documents. These documents were encrypted (say, using AES) with a key X.

This key X is basically the password that the user enters before wanting to view any particular document, because that doc need to be decrypted using X.

If the user wishes to change the key X to something else (maybe his password got compromised), then he'll have to decrypt all the documents, and then re-encrypt all of them using the new value of X.

What if, instead, I have a key Y, which is used to decrypt/encrypt the documents. However, Y itself is a key that is stored on the system, encrypted using X, which is what the user enters.

I'm thinking that the advantage of this would be when the user wants to change his password, he only needs to decrypt and re-encrypt Y, without having to decrypt/re-encrypt all the documents.

Are there any possible weaknesses that I'm missing with this method, or is it sound?

There is the obvious weakness that if Y ever gets compromized, changing the password will not help. The attacker will be able to decrypt all past and future documents. One way this might happen is if the password gets compromized, and the attacker gains access to the encrypted value of Y.

TrueCrypt volumes work in a similar way. When you create a volume, a master key is created which doesn't change throughout the lifetime of the volume, even if you change the password.


Encrypting a broadcast channel We're building a data service that is expected to go out through a single "fat pipe" channel. The design requirement says that the data in the channel must be protected by authentication and encryption. I'm ready to argue that the strongest encryption for such a system (single channel, multiple subscribers) is the "cable box" method - a single key for all subscribers.

Is there a more secure method than this - one that doesn't have the same key for every subscriber?

Yes, there is.

I'm assuming your broadcast stream is (or can be) somehow broken up in smaller messages (or "packets"), and you don't need to retire a key before a message is finished.

Then you produce a random session key for each message, and encrypt this session key with each of the subscribers' keys, prepend them (together with some tagging) to the message.

Each subscriber than filters the header for his section, decrypt the session key and then can decrypt the whole message.

This gives some overhead proportional to the number of subscribers for each message, so it works better when the messages are large enough and the number of subscribers is low. On the other hand, if subscribers can switch on at every time, you'll want to have the message size small so they don't have to wait long until the next session key comes around.

The OpenPGP protocol includes this feature, and is commonly used for sending encrypted emails to multiple receivers. I suppose S/MIME does it similarly.

This method works both with symmetric long-term keys as well as with asymmetric key pairs for encryption (such as RSA or ElGamal).

If you have a "normal" directed communication method in addition to your broadcasting channel, you could also send each subscriber the session key (encrypted with his key) directly, without the bandwith overhead for all the other subscribers.

There might be some more fancy method of encrypting a session key to more receivers without the linear bandwith growth, but I know of none. (1-of-n secret sharing or such?)


Counter Mode Known plain text attacks Counter mode uses a counter that is incremented for each block. Doesnt predictability of this counter expose the scheme to attack? I mean if you are incrementing some nonce, then I have a good chance of guessing the next value

Modern ciphers are explicitly designed to be resistant to key recovery under known and chosen plaintext attacks. Assuming a successful cipher design, encrypting an incrementing counter does not offer an adversary any advantage in regards to obtaining the key, or predicting future ciphertext blocks.

This could be less true with a weak cipher and/or extremely large numbers of encrypted plaintexts.


Turning a cipher into a hashing function This is theoretical question. I'd like to know if it's possible (and what are eventually the consequences), not that I'm going to do it in one of my projects. ;)

The first hashing functions created were based on a symmetric cipher (just like the first Unix crypt was based on DES). The idea was simple. Use the password as key to encode a constant.

I'd like to know if it's still possible to convert any modern symmetric cipher into a hashing function (and second question: into a cryptographic hashing function). Is it possible (easier) to guess the key, when you have an encoded and decoded messages?

Not only we can turn block ciphers into hash functions, but we do.

The usual hash functions (MD5, SHA-1, SHA-256...) use the Merkle-Damgård construction which relies on a block cipher E. A running state r is initialized to a conventional value. Then the input data is split into a number of chunks, each chunk being used as key for the block cipher: r is encrypted with E, using the current chunk as key; the result is added (or XORed) with r, and this yields the new state r for the next chunk. Last obtained state is the hash output.

If you want to apply the Merkle-Damgård construction on a standard block cipher such as AES, you will run into the following problems:

The size of the internal state is the size of the hash output, and it is also the block size of the cipher. AES is a 128-bit block cipher, leading to a 128-bit output, which is a bit too small with regards to today's technology (it would imply resistance to collisions only up to 264 evaluations, which is expensive but doable).
The MD construction exercises unusual features of the block cipher. In particular, the input data is used as key, and collision attacks (a major concern for hash functions) correspond to related-key attacks on the underlying cipher. Related-key attacks are not a problem for block ciphers when they are used for what they were designed to, i.e. encryption. AES is known to have slight weaknesses with regards to related keys but this is not a problem for encryption. It will become a problem if AES is used as building block in a MD-based hash function. (Resistance to related-key attacks was not a design criterion of the AES competition.)

Therefore, MD-based hash function use custom block ciphers which are designed to be especially robust against related-key attacks (or, at least, so we hope for). In the case of SHA-1, the inner block cipher was blessed with a name of its own, SHACAL.

Another example is Whirlpool, based on the block cipher "W", an AES derivative with a larger block size (512 bits) and a revamped key schedule to make it much stronger against related keys (and, unfortunately, it makes it much slower too). This addresses the problems explained above. (Whirlpool does not use the Merkle-Damgård construction, but Miyaguchi-Preneel, a distinct construction which has its own quirks.)

Yet another example is Skein, one of the SHA-3 candidates. It builds over an internal block cipher called Threefish; again, a block cipher with large blocks (512 bits in the "standard" Skein, extensible to 1024 bits).

A few SHA-3 candidates reused not the AES, but parts of the AES; in particular, ECHO and SHAvite-3. The idea was to be able to optimize the hash function with hardware meant to speed up AES, especially the AES-NI opcodes of recent x86 processors. But that's not reusing the block cipher itself.

What must be remembered is that building a hash function out of a block cipher is hard. This is not the same usage context. A fundamental difference is that a block cipher has a key which the attacker does not know (and tries to guess), while a hash function has no secret (when trying to build a collision, the attacker knows everything about every operation in the hash function).


Apply HKDF after Diffie-Hellman Key Exchange I'm trying to use HKDF after Diffie-Hellman key exchange. However, I got stuck on the HKDF part.
from Crypto.Protocol import HKDF
from Crypto.Hash import SHA512
from Crypto.Random import get_random_bytes

salt = get_random_bytes(16)
key1, key2 = HKDF(master_secret, 32, salt, SHA512, 2)

From my understanding, I only need one key for ChaCha20 or AES-256-GCM. Is it a good idea if I only generate one key by HKDF?
One more thing, how can I generate a good salt for this case?

From my understanding, I only need one key for CHACHA20 or AES-256-GCM. Is it a good idea if I only generate one key by HKDF?

In one direction yes, as the MAC and encryption part only requires one key for ChaCha20/Poly1305 and AES-GCM. If you need multiple key parts you can either increase output size and split the result, or you can call HKDF twice using different labels (in the Info component).
Note that you may want to explicitly verify that you generated the same master key on both sides, preferably that should be performed with a separate derived key (and, e.g., HMAC).

One more thing, how can I generate a good salt for this case?

A cryptographic 128 bit salt is fine, as your code seems to be doing at this time.