Is there a way to cleanse a picture of information from steghide? Recently I learned of the steghide application (a command-line tool allowing the use of steganography, the art of hiding information inside other information, used in practice with JGP and WAV files primarily with gzip compression and AES encryption).

Excitedly, I hid sensitive data in my desktop background, deleting the original desktop background in it's place.

After more research, I realized that the default algorithm used (128-bit AES) is considered weak (for my standards, anyway. It's nice to be ahead of the game, using 4096-bit RSA and 256-bit AES for things).

Is there a way to cleanse this JPG file of the irrelevant bits that the embedded file is stored in?

I'm not entirely sure how the use of the passphrase (aside from encryption) is implemented to hide the file in a recoverable place using steghide, but I would assume that if you know the passphrase, you can find the exact bits that the file is located in. Is there a way to locate these bits and overwrite them in the same manner you would use to shred a file, but keeping the original image the same (to the human eye)?
Or am I boned?


Difference between second pre-image resistance attack and collision attack According to my understanding of hashing algorithms -:

Collision attack is an attack wherein we have a hash(x) and we try to find hash(y) such that x!=y while hash(x)=hash(y).

Second pre-image resistance is where we have a message x and a hash(x) and try to find another message y such that hash(x)=hash(y).

According to me the collision attack and second pre-image resistance attack seems similar as in the case of both, we need to find two different hashes which are same while the message associated with the hash is completely different.

You are mistaken. A collision attack is where you need to find any $x$ and $y$ such that $hash(x)=hash(y)$. Thus, you have much more freedom in finding the collision. This makes it "easier" for the adversary.


Calculating the multiplicative inverse of a number in $GF(2^n)$ where $n > 8$ Suppose that:

We have a polynomial $g(x)$ of degree $n$.
$n > 8$.
$q$ is the multiplicative inverse of $p$ in $G(2^n)$ modulo $g(x)$. If $p = 0$, then $q = 0$.

This could be used:

As a non-linear substitution stage in a block cipher, where $y_i = S(x_i)$ and $S: \{0, 1\}^{16} \rightarrow \{0, 1\}^{16}$.
In the decryption routine of a block cipher, where the round keys are used in finite field multiplication during encryption and their inverses need to be known for decryption.

I've seen log/antilog tables presented as the "standard" solution for calculating multiplicative inverses over a finite field, but if $n$ is bigger than 8, like, say, 16 or 40, that's going to take a very long time. What would be another method of calculating $p$'s $q$ that would consume less time and computational resources?

First, let us take AES as an example.

We have $\operatorname{GF}(2^8)$ where each bit represent the coefficient of a polynomial in $\operatorname{GF}(2)[X]$. The modulo reduction is done with $$p(x) = x^8 + x^4 + x^3 + x+ 1$$

Thus you can generate all the elements from a $1$ to $255$ and this forms a cyclic group : $<g^1, g^{\ldots}, g^{255}>$

Notice that:
$g^{2^8-1} = g \iff g^{255} = g$
or:
$g \cdot g^{2^8-2} = 1 \iff g \cdot g^{254} = 1$
thus $g^{254}$ is the inverse of $g$ or in other words:

Computing the $254^{th}$ power of an element give its inverse (more here)

This exponentiation can be quickly done using square-and-multiply.

  Thus for a field of $2^n$ with $p$ being an irreducible polynomial of degree $n$, for $g$ an element of $\operatorname{GF}(2)[X]$: $$g ^{-1} = g^{2^n-2} \bmod p$$

Also the use of tables is ill-advised do to the constant timeness. A bit-sliced implementation of this operation will be preferable.


Static DH/Static ECDH certificate using OpenSSL I've been searching for some time and have found no way to create a working certificate and private key pair with a DH or ECDH public key using OpenSSL. Once I do this, I'd like to sign it with an RSA key, too. Does OpenSSL support this? If so, how can I do it?

DH: OpenSSL commandline has three options for creating certs, but all of them either selfsign the cert or require a selfsigned CSR, and DH can't do either of those. OpenSSL library called from a program you write can construct an X509 object (cert) containing a DH publickey, subject and other attributes as you specify, signed by an RSA key corresponding to a parent (CA) cert. Look at the code for ca.c or x509.c in x509_certify as a (very approximate) starting point. Remember that if the same parent key/cert was or will be used to issue other certs as well you should keep all serialnumbers unique, perhaps using the same simple file ca and x509 use.
(update) In 1.0.2 this changed; x509 -req -CA[key] now has an option -force_pubkey which allows you to create a CSR with a dummy key that supports signing but issue the cert for the DH key. (I didn't notice right away because the usage message wasn't updated until 1.1.0.)
(added) Plus as Maarten spotted OpenSSL has long used PKCS3 parameter encoding (p,g and optionally subgrouplen but not q) not X9.42 as specified by RFC3279 (p,g,q and optionally cofactor). However in 1.0.2 up X9.42 format is supported under the name DHxparams and is automatically used if the q field is set in the DH struct, which (as well as reading it in) occurs if you convert DSA-format parameters (which always use p,g,q) using DSA_dup_DH, invoked by commandline dhparam -dsaparam (!), or create them using genpkey -genparam -algorithm DH -pkeyopt dh_paramgen_type:{1 or 2} (!!).
ECDH: the same key format is used for ECDH and ECDSA and the cert is distinguished if at all only by whether KeyUsage extension permits keyAgree versus digSign. Therefore with commandline you can generate (in order) EC parameters and an EC keypair, an ECDSA-selfsigned CSR, and a cert signed by a parent key&cert either RSA as you asked or ECDSA, optionally containing a KeyUsage extension as you desire (and other extensions also). The two options and variations are the same as for entity RSA except using an EC keypair -- which is generated using EC parameters (aka curve) where RSA keypair is generated using only a bitsize (which is sometimes defaulted).
protocols: If you intend to use these certs for SSL/TLS, note that OpenSSL does not yet implement the static-DH ciphersuites, even though it has long implemented the primitives needed by those suites -- and DHE and DHanon which are implemented. Apparently for the last 15 years there has been essentially no demand; this suggests that the peer systems you can communicate with using static-DH is probably the empty set. The probably-soon next release 1.0.2 is planned to add them. (update: it did, in Jan. 2015) OTOH static-ECDH has been implemented since EC ciphersuites as a whole were implemented; the code was actually in 0.9.8 but disabled by default, and since 1.0.0 it has been enabled by default except that RedHat packages before late 2013 removed (all) EC due apparently to patent concerns. (update) However 1.1.0 released in Aug. 2016 removed both static-DH and static-ECDH ciphersuites.
curve format: for EC (including ECDH) it is possible to represent some standard and popular EC curves either as a OID that maps to a code set by rfc4492, or as 'explicit' parameters (underlying field prime or polynomial, equation coefficients, base point coordinates, order and cofactor). These produce the same EC computation but are NOT equivalent in SSL/TLS protocol. In particular in some cases libssl will successfully use a cert/key with the 'named' form curve (if agreed by the peer system, of course) but not one with the 'explicit' form of the same curve. Use a standard curve (i.e. don't generate your own) and be sure not to convert the parameters to explicit form. (update 2021-04) I didn't notice right away but OpenSSL 1.1.0l and 1.1.1d up (both in 2019-09) now recognize a cert with explicit-form parameters as matching the named curve.
EDIT 2017-10: belatedly found crossdupe https://security.stackexchange.com/questions/44251/openssl-generate-different-types-of-self-signed-certificate
2019-08: also similar https://security.stackexchange.com/questions/14165/do-you-require-a-special-type-of-certificate-for-using-diffie-hellman-as-the-key

Edit: Additional answer to question(s) in comment by Martin Del Vecchio which initially appeared similarly but is in fact completely different.
This new problem is not DH or even ECDH, it is ECDHE. I'm not sure exactly what you are doing so I'll just start from the beginning and work through.
DH and ECDH are different algorithms. They are based on similar mathematical concepts, but they use completely different data.
Classical or "integer" Diffie-Hellman uses a usually-smaller subgroup of the multiplicative group of integers modulo a large prime.
Elliptic-curve Diffie-Hellman uses a usually-maximal subgroup of the points on an elliptic curve over an underlying field.
A DH key or cert cannot be used for ECDH, and an ECDH key or cert cannot be used for DH.
ECDH and ECDHE are different protocols. SSL/TLS has three main key-exchange mechanisms that use the ECDH algorithm:
"fixed" or "static" ECDH, represented by just ECDH in cipher suite names; "ephemeral" ECDH represented by ECDHE; and "anonymous"
ECDH represented by ECDH_anon in the standard (RFC) names but AECDH in OpenSSL. The first two have variants depending on what
authentication is used; anonymous does no authentication, which in practical use on the internet isn't secure,
and thus is disabled by nearly all implementations including OpenSSL by default.
What Firefox offers: I don't use WebRTC, but for https my Firefox 39.0 offers 11 suites: 6 ECDHE
(3 ECDHE_ECDSA and 3 ECDHE_RSA, almost as you had in your comment except the sixth one should be c012 not a repeat of c013),
2 DHE_RSA suites (that's integer-DH not ECDH), and 3 plain RSA suites (not using any kind of DH).
I find it surprising NSS (which is what FF uses for SSL/TLS) would be different for DTLS than TLS;
perhaps it's because DTLS started at the same time and protocol level as TLS 1.1,
which is well correlated with ECC although it doesn't technically require it.
But even if ECDHE isn't required it's still preferable both in itself (PFS and efficient)
and because FF/NSS offers it in conjunction with GCM for the data cipher.
FF also offers only the 3 most popular "curves" from SECG/NIST: P-256, P-384, P-521. It might support others but it doesn't say so.
What ECDHE requires (any server): to support any ECDHE ciphersuite in SSL/TLS you do NOT need an ECDH cert, much less a DH cert.
You need two things in the server:

a privatekey and cert that allows signing, either RSA with a size acceptable to the client or ECC(ECDSA) on a curve supported by
and acceptable to the client (and the server), with the cert issued by a CA/chain trusted by the client (and not expired or revoked etc.) and any chain cert(s) either supplied by the server or dynamically available or both.
Best practice since the beginning of 2014 is that RSA must be at least 2048 bits, ECC at least 224 bits, and signing hash at least SHA-256. FF apparently doesn't check RSA-2k yet, and it doesn't enforce SHA-256 yet but it does give a warning in its optional console(s), but you should expect it probably will enforce these before very long for "proper" (CA-issued) certs; whether it will do so for selfsigned certs that necessarily must be manually trusted is less clear to me. By choosing the "top 3" ECC curves FF implicitly enforces more than ECC-224.

ECDH parameters -- not a key and definitely not a cert, but only parameters, and not DH parameters either.
ECC parameters are usually called a curve
because that's the interesting part although the actual parameters also include the base point, order and cofactor. The curve used must be supported by and acceptable to the client (and the server).

What OpenSSL server and selfsigned needs is more specifically:

privatekey and cert that allows signing either RSA or ECC (ECDSA). Lots of browsers and clients besides FF like P-256 so if you use EC use P-256 unless you have a strong reason otherwise. As noted in the first part of my answer, make sure you use the "named" form of the curve not the "explicit" form.
If you don't include the KeyUsage extension, it allows signing implicitly;
if you do include KU, the value must have the digitalSignature bit set.
Any selfsigned cert (for any ciphersuite and keyexchange not just ECDHE) will have to be manually trusted in FF.

"temporary" (ephemeral) ECDH parameters. You can:

call SSL_[CTX_]set_tmp_ecdh to set a specific curve
for future sessions (unless changed);

call SSL_[CTX_]set_tmp_ecdh_callback to set a callback function which will
be called for each session to select a curve (unless changed);

or in 1.0.2 (released Jan. 2015) call SSL_[CTX_]set_ecdh_auto
to have libssl automatically choose a curve suitable for each session.
As above use P-256, by calling EC_KEY_new_by_curve_name(NID_X9_62_prime256v1), unless you use auto.
(EC_KEY_new doesn't generate a key; it creates an object containing the curve which will be used to generate the key in libssl.)

SSL_k (and _a) bits cannot be in a cert. They are used only within OpenSSL as attributes of ciphersuites.
There are some different values sometimes used in some certs to represent information related to but different than
the SSL_k and SSL_a bits. But not for SSL_kPSK or SSL_aPSK; those never correspond to anything in a cert, because PSK never uses certs.
I'm not sure what you actually did here, but the above description is what is correct.


How to compute $m$ value from RSA if $phi(n)$ is not relative prime with the $e$? Here is some information we got :
We know the value of $n$, with size $1043$.
We know the value of $p$ (size $20$) and $q$ (size $1023$) as the factors.
$e = 65537.$
$\varphi(n)$ = $(q-1)(p-1)$
When I calculated $\gcd$ and $\text{modinv}$, I got :
$\gcd(e,\varphi(n)) = 65537$
$modinv(e,\varphi(n)) = 1 $
So we can tell that they are not relatively prime.
So, how to compute the d, and get the value of m?
I'm not that good with math, so I cant understanding well the theory.
so can anyone please make an example implementation or write a clear formula?

Well, if we assume that:

$e$ is prime (65537 is)
Only one of the primes minus one has $e$ as a factor; for example, $p-1$ is divisible by $e$, but $q-1$ is not.  For this discussion, we'll assume that $p$ is the prime with $p-1 \equiv 0 \bmod e$ (which might happen to be the size 1023 factor for you)
$p-1$ is not divisible by $e^2$
That the ciphertext was actually generated by computing $P^e \bmod n$ for some plaintext value $P$.

Then, one way to derive the possible plaintexts is to compute:
$$C^d \cdot L^i \bmod n$$
where:

$C$ is the ciphertext
$d = e^{-1} \bmod \lambda / e$
.  This is well defined, as $\lambda/e$ is an integer which is relatively prime to $e$.
$L = k^{\lambda/e} \bmod n$, where $k$ is an integer such that $L \ne 1$ (and any such value $L$ works); most values of $k$ work
$\lambda = (p-1)(q-1)/\gcd(p-1, q-1)$
$i$ is any integer $0 \le i < e$

Now, if we iterate over the possible values of $i$, this will give $e$ possible values for the plaintext (unless $C$ happens to be a multiple of $p$).  The original plaintext  will be one of these values.  All these values, when raised to the power $e$, will result in the ciphertext, hence we cannot distinguish from the ciphertext which one it is.


About the necessity simulators set adversary random-tape In the ideal/real proof paradigm we sometimes find simulators with the capacity of set adversary random tape.

My question: when do we have to consider the necessity of simulators set adversary random-tape?. We know that malicious adversary can substitute random-tape setup by whatever he want, but: are there cases where it's needed to consider this capacity with semi-honest adversary?

In the vast majority of cases, the simulator sets the random tape of the adversary simply because it has to (by the definition). So, the simulator sets it in the beginning to be uniform, and this is then ignored from then on.

There is one cases that I know of that this is actually really important, and this is non-black-box zero knowledge. Specifically, in Boaz Barak's thesis, he has a number of constructions. The construction which works for uniform verifiers has the property that the verifier has to have a short description. In order to make this work, the random tape of the verifier is actually chosen by the simulator pseudorandomly (rather than truly randomly) since this then has a short description.

I don't know of anywhere else that this is important. In general, choose it at random and ignore from then on...


Luby-Rackoff theorem for Generalized Feistel I was reading about Luby-Rackoff theorem from various sources: [1], [2], [3], which says you need at least 3 rounds of a $2$-branch Feistel network to get a PRP if the underlying $f$ function is a PRF. I also came to know about the Generalized Feistel Network which has more than two branches.

What will be the minimum number of rounds to get a PRP from a generalized $n~(>2)$ branch Feistel network, given the underlying function $f$ is a PRF?

As you probably saw in the reference linked, there are multiple types of "basic" generalized Feistel networks: Type-1, Type-2 and Type-3. As far as I can tell all of these were introduced at CRYPTO'89 by Zheng, Matsumoto, and Imai in "On the Construction of Block Ciphers Provably Secure and Not Relying on Any Unproved Hypotheses".

Suppose that your state is split into $k$ blocks, then the above paper does in fact prove  / claim security for these generalized Feistel constructions (with each and every PRF used in all rounds and all state parts of each round being independent):

For Type-1, security is proven for $2k-1$ rounds
For Type-2, security is proven for $k+1$ rounds
For Type-3, security is proven for $k+1$ rounds

The paper also proves / claims that these numbers of rounds are actually minimal.

For everbody's reference, here are the three basic types as a fancy graphic:
image source

As one can somewhat clearly see, the first two types are "special cases" of the third where a certain selections of PRF invocations and XORings is dropped. The paper does provide further analysis on the number of rounds to keep security when dropping these with certain patterns


Calculating the privacy that Renyi ($\epsilon, \delta$) Differential Privacy satisfies I add differential privacy (DP) to my machine learning models by using PyTorch-DP. PyTorch-DP supplies me with the values: $\epsilon$ and $\delta $. I know that the $\epsilon$ tells us something about the probability $\rho$ that the privacy of individuals in the dataset (DP) is broken. So, a $\rho$ of 0.5 might correspond to an $\epsilon$ of 2 (depending on the statistics that are released).
So now, my question is: With the implementation that PyTorch-DP uses (Renyi DP calculated by using the Moments Accountant method), to what $\rho$ does the $\epsilon$ correspond to? If I do not know this, how can I say something "meaningful" about the level of privacy $\rho$ that $\epsilon$ satisfies?

I don't think your interpretation of $\varepsilon$ in DP is correct. You can find a decent explanation of this parameter in this crypto.SE question and links therein.
The best intuition I have for Rényi privacy is that it bounds the average of the privacy loss) $L(O)$: instead of being a worst-case property, like DP ("for all outputs $O$, $L(O)$ is lower than $\varepsilon$"), Rényi privacy is an average-case property ("when we average $L(O)$ across all possible outputs $O$, the result is lower than $\varepsilon$"). The $\alpha$ parameter determines which kind of average we're using: used: $\alpha=1$ bounds the arithmetic mean of $L(O)$, $\alpha=2$ bounds the arithmetic mean of $e^{L(O)}$, $\alpha=3$ bounds the quadratic mean of $e^L(O)$, etc.


Difference between “ECDH with cofactor key” and “ECDH without cofactor key”? I need to use “ECDH with a cofactor key” for generating symmetric key. I have a fair idea on how ECDH works, but I don’t understand the cofactor part.

What is the difference between ”ECDH with a co-factor key” and ”ECDH without a co-factor key”?

Also, it would be great if you could point me to information related to the implementation itself.

First, a bit of background.  If we refer to the size of an elliptic curve group as $n$, we select an elliptic curve with $n = hq$, where $q$ is a large prime, and $h$ is a small integer called the cofactor; it is typically either 1, 4 or 8.  The values of $q$ and $h$ will be part of the curve definition.

As you know, with straight DH, we agree on a point $G$, Alice selects a random value $a$ and computes $aG$; Bob selects a random value $b$ and computes $bG$; they exchange values, and then Alice computes $a(bG)$, Bob computes $b(aG)$, and those are the same value.

When we use the cofactor variant of DH, the first part is exactly the same; Alice selects a random value $a$ and computes $aG$; Bob selects a random value $b$ and computes $bG$; they exchange values.  However, Alice then computes $ha(bG)$, and Bob computes $hb(aG)$.  That is, in the second phase, they internally multiply their random value by $h$ before doing the point multiplication.

Why do they do this?  Well, it helps avoid a small potential data leakage if Bob doesn't play by the rules.  If $h>1$, there are points with small order, we'll call such a point $H$ (there won't always be a point of order $h$, however to make this argument slightly simpler, we'll assume there is).  Then, suppose an attacker didn't give Alice the value $bG$, he gave him the value $bG+H$.  Alice would then compute $a(bG+H) = abG + aH = abG + (a \bmod h)H$.  As Bob knows the value $abG$ (he does his half of the second phase honestly), he can compute Alice's shared secret with $h$ different alternatives, and so recover $a \bmod h$.

By internally multiplying by $h$ in the second phase, this doesn't happen; we have $ah(bG+H) = abhG + ahH = abhG$ (as the point $H$ is of order $h$), independent of what $a \bmod h$ is.

This isn't the only possible way to defend against this; Alice could also compute $q(bG)$, and verify that it's the point at infinity ($q(bG + H)$ won't be), however that's fairly expensive, while the cofactor method just uses two or three point doublings over the computations we would be doing for ECDH anyways.

Now, if this is the only place that Alice uses $a$ (that is, if she is using ephemeral ECDH), this leakage doesn't matter a bit - Bob already knows the shared secret, and he can't leverage that into any knowledge of any other secret.  However, if Alice reuses her $a, aG$ pair for other exchanges, the leakage is there (and whether it's enough to worry about is another question entirely).

One last word of warning: when we compute the value $(ab)G$, we typically actually compute $(ab \pmod q)G$, as normally they're the same (and computing things $\bmod q$ makes things more efficient).  However, this is one place where we don't; we really do formally compute $(ah)bG$, even if $ah > q$.


Ideal way to profile/performance-measure cipher implementations I have implemented a bit-sliced version of two ciphers (Gibbon-120 and Hanuman-120, both part of the Primates family of ciphers: http://primates.ae/wp-content/uploads/primatesv1.02.pdf )

I now want to measure the increase in effectiveness that my bit-sliced ciphers have given me, compared to the reference implementations. Of course I also want to know my implementations performance/speed in a general context.

What I have tried so far, is to encrypt & decrypt 100byte, 100kbyte and 100mbyte 10 times, and then see what the average wall-clock time for encrypting and decrypting the different amount of data was.
I doubt whether this is the smart way to go about it though. While a bit-sliced implementation is constant in execution time, the reference implementations are another matter. They use lookup-tables and thus can gain in speed after the first encryption, due to cachehits from lookup-tables now being a possibility.
There is also the issue that if it is measured in wall-clock time, then background-processes on my computer could degrade or otherwise cause noise on the results.

On the other hand, I could count instructions in the compiled code (although I do not know how yet). This does not seem like the ideal way to go about it either though, as different instructions has different latency and throughput. If one cipher uses 10 additions and another uses 10 multiplication, then the former might be faster, despite them using the same amount of instructions.
This is the case for some of the AVX instructions I used in my bit-sliced implementation (a permute instruction if I remember correctly takes 3x the time a shuffle instruction takes).

What is the standard way to go about this? What is the defacto standard that cipher-performance is being measured in, when a new up to date cryptographic cipher-design or implementation is being published?

My implementations are written in C for whatever it is worth (and uses Intel Intrinsics for AVX).

It is unfeasible with newer CPUs to just count instructions, as newer CPUs can do multiple per cycle, and have multiple cores and likewise.

Cycles per byte is the usual way to measure performance these days.
Of course, to make it as fair as possible and comparable to others, the code is only ideally run on one core, turboboost and hyperthreading is turned off, etc.


Why does lattice KEX not require sampling with high precision? I was reading the NewHope paper, and I see that they are using Binomial distribution and not a discrete Gaussian distribution as was used by BCNS. I also remember hearing somewhere that lattice key exchange does not require a very high precision sampling, whereas signature schemes need high precision sampling. Why is this distinction? How does the sampling algorithm used affect the security in these schemes?

The way and the purpose in which gaussians are used in key exchange and digital signatures is completely different.

In public key encryption (and key exchange), we need computational-indistinguishablilty of (A,As+e) when A is a random matrix (over some ring) and (s,e) are vectors over that same ring with small coefficients.  To get the tightest security reduction based on worst-case hard problems, s and e should be gaussian, and this is why it is sometimes (falsely) believed that s and e should be gaussians for security.  In reality, they don't need to be -- the distinguishability problem seems to be just as hard in practice when s and e are "simpler-to-sample" distributions such as uniform or binomial.

In digital signatures (using the Fiat-Shamir transform), the signature is computed as z=Sc+y, where S is a secret matrix of small coefficients, c is a challenge vector (with very small coefficients) and y is some vector that is chosen during signing.  For security, one needs that z has small coefficients and is independent of the secret key S.  For z to have small coefficients, y needs to have small coefficients.  In order for z to be independent of S, we need to use rejection sampling so that the distribution of y "masks" the shift by Sc.  If we don't use high-enough precision here, then we may not get the distribution of z that is statistically independent of S, which will be disastrous for security.

In some recent papers, it was shown that the way to get the shortest possible z requires taking y to be a discrete gaussian, and so you need to be able to sample discrete gaussians with a high precision.  It should be mentioned that you can also create digital signatures by simply using the uniform distribution, but thy will be slightly longer.

For hash-and-sign signatures, it's again the same high-level idea as for Fiat-Shamir ones.   You want to make sure that the signature is independent of the secret key. The most efficient way we know how to create such signatures is to have them come from the discrete gaussian distribution.


How can encryption involve randomness? If an encryption algorithm is meant to convert a string to another string which can then be decrypted back to the original, how could this process involve any randomness?

Surely it has to be deterministic, otherwise how could the decryption function know what factors were involved in creating the encrypted string?

Well, the idea behind randomized encryption is that a single plaintext $P$ can encrypt into many different ciphertexts $C_1, C_2, ..., C_n$, and that when we encrypt, we pick one of those ciphertexts randomly.  Of course, because the decryptor has no way to knowing apriori which one we picked, it must be able to map any of those ciphertexts back into the original plaintext.

If the ciphertext $C_i$ was exactly as long as the plaintext $P$, then there would be an obvious problem; if the plaintext was $k$ bits long (and hence there are $2^k$ distinct plaintexts), and there are $n$ ciphertexts for each plaintext, we have $n2^k$ ciphertexts (which must all be distinct), and only $2^k$ bit patterns available to express them.

The obvious solution to this is that the ciphertexts must be longer than the corresponding plaintext.  In particular, if each ciphertext was at least $\log n$ bits longer, then everything fits nicely; we have $n2^k = 2^{k + \log n}$ ciphertexts and $2^{k + \log n}$ bit patterns to express them.

Now, the obvious question is: why does anyone bother?  The answer to that is, well, it provides better protection than deterministic methods.  It is generally the case that we'll send multiple messages with the same key.  If we happen to send the same message twice, deterministic encryption would make that obvious to the attacker (because the ciphertexts will be exactly identical), and that is information we'd rather the attacker not have.  Even if we'll never send the same message twice, we may send related messages.  While it is possible to design a deterministic encryption method that doesn't leak any information when given related messages, it's harder than you'd think.  In contrast, the goal behind nondetermanstic encryption is to make all the messages look perfectly random (even if we decide the send the same message multiple times); that turns out to be a rather easier goal to achieve.

One common way nondetermanistic encryption is implemented with CBC mode; the encryptor chooses a random block (known as an IV; 128 bits if he is using AES), and uses that to encrypt the message.  He sends the IV along with the encrypted message to the decryptor, who can uniquely decrypt the message.  One nice property about CBC mode is that it is easy to prove that if the IV is chosen randomly, and that the underlying block cipher is secure, then an attacker cannot distinguish the encryption from a random source.


Break HMAC-SHA256 of PAN with known hash? Imagine a database containing hashed (HMAC) Primary Account Numbers (PANs ) and associated identifiable information (e.g. transactions).
Consider a data breach. Prior to the breach, an attacker made specific transactions to make it easy to identify one or more hashed PANs. Could the attacker then work out the SHA256 key and easily brute force all the PANs?

Only for a trivial key.
You have HMAC(<key>, <secret₁>) = <hash>. The attacker knows <hash> and certain <secret>. Having a small search space, different <secret> values might be bruteforced.
However, with a proper (long, random) <key> the attacker won't be able to recover the other values. The HMAC-SHA256 itself is not reversible, and a long random <key> won't let them bruteforce them during their lifetime.
The real risk would be that during the data breach, in addition to the hashed values, the attacker also stole the <key>.


Converting R1CS to QAP - checking the last step from reading Vitalik Buterin's excellent post on creating a QAP from an R1CS, I understood to translate a function into three groups of vectors, the number of vectors being the number of "gates" or constraints in our flattened code, and the size of each vector being the number of variables.

I understood also that to convert to a QAP such a that we end up with another three groups of vectors, with each vector i containing the coefficients of a polynomial that was interpolated from the ith values of each of the linear constraints from the original group (you know what I mean).

I want to check my understanding of the next step, whereby we derive a single polynomial by creating a (s · A) * (s · B) - (s · C) = H * Z

In Vitalik's example, does that mean that we perform the calculation as:

( 1 * A1(x) ) + (3 * A2(x)) + (35 * A3(x)) .....

so that using his example it would be:

( 1 * 0.833x3 - 5x2 + 9.166x - 5 ) + (3 * A2(x)) ....

What I wanted to make sure is that at this point, I'm supposed to be performing a dot product between the witness (1,3,35,9,27,30 in his example) and the corresponding polynomial from each  and group and NOT the between the witness and the EVALUATION of the corresponding polynomial from each group.

So for example, I shouldn't be doing this:

( 1 * A1(1) ) + (3 * A2(3)) + (35 * A3(35))  + (9 * A4(9)).....

that is, substituting x for the corresponding value in the witness

( 1 * 0.833(1)3 - 5(1)2 + 9.166(1) - 5 ) + (3 * A2(3)) ....

There are both.
To produce a QAP system, you do dot-product witness and polynomials (no evaluation).
To verify a SNARK-proof, you do dot-product witness and polynomials evaluated at "toxic waste" multiplied by group elements.
Please note it's actually both public input and witness concatenated (all the variables).


Understanding MACs and why cleartext is sent over Assume both Alice and Bob have a symmetrical key, let's call it $k$.
They agree on a cryptographic hash function, let's call it $\mathsf{HASH}$.
Now Alice wants to send an authenticated message.
She sends $\left(\mathsf{msg}\parallel\mathsf{HASH}_\mathsf{k}(\mathsf{msg})\right)$ to Bob.
Bob calculates the hash from $\mathsf{msg}$ and checks whether it's equal to the hash he received from Alice.
My question is:

When Alice sends $\left(\mathsf{msg}\parallel\mathsf{HASH}_\mathsf{k}(\mathsf{msg})\right)$, Eve, an eavesdropper in the network, sees this packet in cleartext, which break the confidentiality?
How to protect the confidentiality?

My guess is: the whole MAC authentication $\left(\mathsf{msg}\parallel\mathsf{HASH}_\mathsf{k}(\mathsf{msg})\right)$ is wrapped in some kind of cryptographic function?

A MAC is used to ensure two properties, really: the message has not been altered and the message has been indeed be sent by Alice and not Eve. If the MAC is secure, then Eve cannot change the message and compute a valid MAC for the modified message. Eve can read the message, but in this scenario we only protect the messages against modification and we want to know it comes from Alice (as Bob believes only Alice has the key for the MAC, so is the only one, besides himself, to be able to generate and check the MAC). Such MAC-only networks could occur, if speed (avoid encryption overhead) and authenticity are your main concerns, e.g. in alarm systems, where you don't want the alarm messages to be modified by an attacker, but you don't care about it being private.

It is possible to combine it with another cryptographic primitive if privacy is desired. It's most common to encrypt the data and then compute a MAC over the ciphertext and send both (EncryptThenMAC), also possible, but possibly less secure: encrypt the plaintext and its MAC and send the resulting ciphertext (MacThenEncrypt), or compute a ciphertext over the plaintext, and send the ciphertext together with the MAC of the plaintext. (EncryptAndMac) This leaks some info, possibly. But all three have been done. Or use an authenticated-encryption mode of a block cipher like GCM or OCB mode. These modes mostly follow the EncryptThanMac paradigm, as that has the better security proofs.


Advantages of combined PRNGs This question is related to this one in intention, and this one in scope.

Would I be guarding myself against future attacks on a single PRNG if I combine two (or more) together?

I am thinking of using the Fortuna PRNG together with AES in counter mode, each initialised by a different source of entropy (now exactly what the two sources will be is an open problem). The output of each will be combined with the XOR operation, they will run on a separate thread and computational power is not a problem.

My (informal) thinking is that, as long as one function remains unpredictable (in polytime), the output is secure (in polytime).

The answers may address Fortuna or AES specifically, or they may treat the generators as abstract functions. Is there a flaw in this design?

It should not be possible to attack this scheme itself. The XOR function will work like a one time pad, where the output of each PRNG can be either the plaintext stream or the key stream. So the output of the function should be random as long as one of the two streams can be thought to be a secure and well seeded PRNG.

In real life scenarios the main cause for concern is not the PRNG itself; the source of entropy (seeding) is much more of a concern. In this scheme entropy is exchanged for a more secure PRNG. It is questionable if this is worth the cause. Using the same entropy is for both PRNGs is not a good idea, it may open the scheme to attacks and will certainly invalidate any security proof.

Furthermore, synchronizing the streams generated by the threads may require large buffers which are effectively representing the state of your new PRNG. It is required to deal with thread synchronizing issues and overhead as well and it is important not to leak any state while doing any of this. It may be easier to put the two functions in the same thread to maintain a small state.

In conclusion, I don't think there are theoretical issues with your scheme, but I don't see how it would be a practical scheme. Most importantly it seems to solve an issue that is not really present. You trade entropy and speed for a more secure PRNG, which is not likely to be a cause of concern in the first place.

Note that I don't see how the results of Boneh and all apply to the new PRNG. Their results are used when multiple hash functions are used on the same data, possibly using XOR. I don't see how it would apply on generating a key stream. That said, it is questionable if any attacks on the underlying hash function translate to the PRNG anyway.

You are likely better off using the additional entropy to reseed more often.


Is there an alternative AES schedule? I'm currently reversing an AES implementation for disk encryption. The odd thing I'm stumbled about is a key schedule where the encryption round keys are not the same as the decryption round keys (in "reversed order"). Altough the first 4 bytes, i.e. the first round key for the encryption, and the last 4 bytes, i.e. the last round key for the decryption, are the same. The other round keys are totally different.

Is there an optimization that requires the round keys to be computed in a different manner?

If you look at the algorithm description, you see that, at a high-level, the encryption algorithm looks like this:

            addRoundKey(0);
            for (int i = 1; i < rounds; i ++) {
                    subBytes();
                    shiftRows();
                    mixColumns();
                    addRoundKey(i);
            }
            subBytes();
            shiftRows();
            addRoundKey(rounds);

The decryption algorithm will then look like this:

            addRoundKey(rounds);
            for (i = 1; i < rounds; i ++) {
                    invShiftRows();
                    invSubBytes();
                    addRoundKey(rounds - i);
                    invMixColumns();
            }
            invShiftRows();
            invSubBytes();
            addRoundKey(0);

Now, if you view the 16-byte state as a vector in space (Z2)128, then the ShiftRows() and MixColumns() transforms are linear, and so is the addition of a round key (addRoundKey() -- really, a bitwise XOR). Moreover, the ShiftRows() is byte-oriented, therefore it can commute with SubBytes() (since SubBytes() works on each state byte independently). Therefore, it is customary for AES implementations to combine SubBytes(), ShiftRows() and MixColumns() into a single step with 8->32 lookup tables (you need four of them, for a total of 4 kB of tables). This optimization is what the Wikipedia page alludes to.

If you try to do that with decryption, in the loop above, you will see that the addRoundKey() step happens between invSubBytes() and invMixColumns(), which is inconvenient. The solution is to move the addRoundKey() one step down, but then the round key must be modified to account for the move (in simple words, if you add the round key after the invMixColumns(), then you must add a round key that has been already "invMixColumnsed"; it works because of linearity).

In that case, decryption becomes:

            addRoundKey(rounds);
            for (i = 1; i < rounds; i ++) {
                    invShiftRows();
                    invSubBytes();
                    invMixColumns();
                    addRoundKeyAlreadyInvMixed(rounds - i);
            }
            invShiftRows();
            invSubBytes();
            addRoundKey(0);

With that new algorithm layout, the invShiftRows(), invSubBytes() and invMixColumns() steps are again together, and can be optimized into a single set of lookup tables. However, this requires the "inner" subkeys (all but the first and last one) to be preprocessed with invMixColumns() so that the computations still work.

I believe this is what you observe in the implementation you are inspecting.


Test vectors for Ed25519 My apologies if this is obvious, but the truth is that I am confused about this.
I am looking into RFC 8032 for test vectors for Ed25519, and I have some doubts concerning the information presented in section 7.1 in that document. At the top of this section one can find the following data:
SECRET KEY:
   9d61b19deffd5a60ba844af492ec2cc4
   4449c5697b326919703bac031cae7f60

PUBLIC KEY:
   d75a980182b10ab7d54bfed3c964073a
   0ee172f3daa62325af021a68f707511a

My understanding is that the secret key is a randomly generated string of 64 bytes, the first 32 bytes of which are then further manipulated. The resulting string is interpreted as an integer, according to some rules described in that RFC, and then used to obtain the public key by adding the selected base point to itself the number of times specified by the secret key.
My questions are the following:

As displayed in the RFC, is the secret key meant to be interpreted as an integer? If so, is the integer already displayed in left-to-right form - that is, with 9 being its most significant hexadecimal digit, and 0 its least significant one?

Regardless of whether it is displayed as an integer or a string, is this supposed to be after the bit manipulations that the RFC specifies that should be applied to the 64 bytes obtained by hashing 32 randomly generated bytes?

To put the two questions above in a different way, is the public key obtained by adding the base point 0x9d61b19deffd5a60ba844af492ec2cc44449c5697b326919703bac031cae7f60 times to itself?

As for the public key, my guess is that what is displayed is the point in the curve obtained by adding the base point to itself as mentioned above, but subjected to the compression technique described in the document. Is this correct?

Encoding is Little-Endian ( section 5.1.2.)

All values are coded as octet strings, and integers are coded using
little-endian convention, i.e., a 32-octet string h h[0],...h[31]
represents the integer h[0] + 2^8 * h[1] + ... + 2^248 * h[31].

Key Generation (section 5.1.5)

Hash the 32-byte private key using SHA-512, storing the digest in
a 64-octet large buffer, denoted h.  Only the lower 32 bytes are
used for generating the public key.

Therefore you have 32-byte private key that needs to be hashed with SHA-512.

Prune the buffer: The lowest three bits of the first octet are
cleared, the highest bit of the last octet is cleared, and the
second highest bit of the last octet is set.

This is for the lower 32-byte output of the SHA-512

Interpret the buffer as the little-endian integer, forming a
secret scalar s.  Perform a fixed-base scalar multiplication
[s]B.

Public key (5.1.5)

The public key A is the encoding of the point [s]B.  First,
encode the y-coordinate (in the range 0 <= y < p) as a little-
endian string of 32 octets.  The most significant bit of the
final octet is always zero.  To form the encoding of the point
[s]B, copy the least significant bit of the x coordinate to the
most significant bit of the final octet.  The result is the
public key.

Python Sample (Section 6)

   # Points are represented as tuples (X, Y, Z, T) of extended
   # coordinates, with x = X/Z, y = Y/Z, x*y = T/Z

    def point_compress(P):
        zinv = modp_inv(P[2])
        x = P[0] * zinv % p
        y = P[1] * zinv % p
        return int.to_bytes(y | ((x & 1) << 255), 32, "little")

    def point_decompress(s):
        if len(s) != 32:
            raise Exception("Invalid input length for decompression")
        y = int.from_bytes(s, "little")
        sign = y >> 255
        y &= (1 << 255) - 1

        x = recover_x(y, sign)
        if x is None:
            return None
        else:
            return (x, y, 1, x*y % p)

    ## These are functions for manipulating the private key.

    def secret_expand(secret):
        if len(secret) != 32:
            raise Exception("Bad size of private key")
        h = sha512(secret)
        a = int.from_bytes(h[:32], "little")
        a &= (1 << 254) - 8
        a |= (1 << 254)
        return (a, h[32:])

    def secret_to_public(secret):
        (a, dummy) = secret_expand(secret)
        return point_compress(point_mul(a, G))


Why are ECB CBC and CFB parallelizable? I guess I do not understand the word 'parallelizable'. Why are ECB CBC and CFB parallelizable?

It would be nice if someone could explain it in a short way.

By parallelizable, what we mean is that the encryption/decryption process can be broken down into multiple tasks that can be run at the same time. For block cipher modes, this means that if we have multiple copies of the block cipher, we can use that to go faster.

For example, in CBC decryption mode, the decryption transform of several adjacent blocks is defined as:

$$P_i = C_{i-1} \oplus D_k( C_i )$$
$$P_{i+1} = C_{i} \oplus D_k( C_{i+1} )$$
$$P_{i+2} = C_{i+1} \oplus D_k( C_{i+2} )$$

($C_i$ is the $i$th ciphertext block, $P_i$ is the $i$th plaintext block, and $D_k$ is the block cipher run in decryption mode)

Now, we assume that we see the entire ciphertext, including $C_{i-1}$ through $C_{i+2}$ at the same time.  So, if we have three hardware implementations of $D_k$, then we can feed each one with $C_i, C_{i+1}, C_{i+2}$, have them perform the decryption, then do the xor's, and thus produce $P_i, P_{i+1}, P_{i+2}$ all at the same time.

So, by having three hardware implementations, we can decrypt three times as fast.

On the other hand, let us consider CBC mode encryption.  Here, the standard definition for this is:

$$C_i = E_k( C_{i-1} \oplus P_i )$$

$$C_{i+1} = E_k( C_i \oplus P_{i+1} )$$

$$C_{i+2} = E_k( C_{i+1} \oplus P_{i+2} )$$

Here, we run into a problem when we try to run it in parallel.  To generate $C_{i+1}$, we need to have the value $C_i$ before we can start encrypting.  Hence, to generate the next encrypted block, we have to compute the previous one first.  Hence, if we have three encryption engines, we can't take advantage of them; we end up only using one at a time.


Pairing - Is it possible to map two $r$-torsion points to a $r^2$-torsion point? Let $E(\mathbb F_{q^k})$ be an elliptic curve on finite field $\mathbb F_{q^k}$, where $\mathbb F_{q^k}$ is an extension of $\mathbb F_q$ with $k>1$. Let $e: G_1 \times G_2 \rightarrow G_t$ be a bilinear pairing, and $G_1$, $G_2$ are some subgroup of $E(\mathbb F_{q^k})$ of order $r$, where $r| \# E(\mathbb F_q)$ and $r^2 | \# E(\mathbb F_{q^k})$, and $G_t$ is subgroup of order of $\mathbb F^*_{q^k}$.

Is it possible to modify (Weil or Tate) pairing such that the order of $G_t$ be $r^2$? In other word, is it possible to map (with keeping bilinearity property) two $r$-torsion points to a $r^2$-root of unity?

No, it is not possible.

By the definition of bilinearity, we have $e( kG, H ) = k \cdot e( G, H )$.  If the order of $G$ is $r$ (that is, $rG = 0$, we have $e( rG, H ) = e( 0, H ) = r \cdot e(G, H)$.  We know $e(0, H) = 0$ (as bilinear functions maps the identity to the identity), and hence we have $r \cdot e(G, H) = 0$; that is, the order of $e(G, H)$ must be either $r$, or some divisor of $r$.


Message encrypted with a LFSR based stream cipher I am learning about LFSR sequence and I came across this question:
A 16-bit message consists of two ASCII characters. This message was encrypted
with a one-time pad, and the key for the one-time pad was an LFSR sequence (mod 2) given
by $x_0 = 1$, $x_1 = 0$, $x_2 = 1$ and $x_{n+3} = x_{n+2} + x_n$ for $n \ge 0$.
The ciphertext is 1111000000001000. Decode the message.

I'm a lost as where to begin on this one. I am not looking for anyone to just give me the answer, but some guidance (step by step preferably) on what my starting steps should be would be greatly appreciated!

I will try to not directly answer your question, but this exercise is so simple that it gets hard to help you without doing that.

You are going to use a symmetric cipher (One-Time Pad - OTP), thus your initial step is to compute your key. This is given by the execution of the LFSR as you described, until a key-stream of the length of the message is obtained. Then, simply apply the OTP decryption step (*) into your pair (key, ciphertext).

(*) I hope you know what the OTP decryption step looks like! ;-)


How to break AES CBC PADDING with chosen ciphertext attack I'm doing a penetration testing for a web application that uses AES CBC PADDING encryption for the parameter ?email=ciphertext then it's printing the plaintext email on html body.

I would like to know if is there any possibility to :

Crack the IV or the KEY using chosen plaintext attack?
Can i encrypt a given plaintext?

I believe you can deduce the IV by passing in a chosen ciphertext. This ciphertext should be of the form C = C0||C0, where C0 is the first ciphertext block, and || is the concatenation operator. In other words, send the same block twice!

This will get you two blocks of plaintext, P0||P1. We have that

Decrypt(key, C0) ^ IV = P0
Decrypt(key, C0) ^ C0 = P1

Therefore,

P1 ^ C0 = Decrypt(key, C0)
P0 ^ P1 ^ C0 = IV


HMAC-SHA1( secret key ) with header of a transmitted file Given:
an AES-128 secret key (ASecKey) encrypts a file (CBC mode).
(Assume good random)

Is is insecure to append (include) an HMAC-SHA1 of ASecKey to file?

Purpose:
The receiver can then quickly verify if the shared secret key was used to encrypt.

It's probably better to use a KBKDF as that doesn't need a key as input. You can use the KDF as key check value or KCV. If you use a block cipher based KBKDF from NIST SP 800-108 then you could reuse the AES algorithm to calculate the KCV.

You could however also make it easy for yourself and use a SHA-1 or SHA-2 over the key as KCV.

Note that the PKCS#11 method allows for calculating a KCV by encrypting a block of all zero's; this method should not be used.


How is the SPI determined/negotiated in phase 2 of IKE (v1)? While I am aware that the SPI (along with destination IP and protocol) is used to uniquely identify an incoming SA on a peer, for the life of me I am not able to understand how that particular SPI value is determined and agreed upon by both peers during IKE phase 2 message exchanges, for both the incoming and outgoing SA that are established on each of them. I have come across sources stating the below:

  The SPI is a 32-bit number that is chosen by the initiator to uniquely identify the outgoing IPSec SA that is generated as a
  result of this negotiation in its database of security associations.
  The responder, upon seeing the SPI, makes sure that it is not the
  same as one of the SPIs it is using and starts using it for its
  incoming IPSec SA. It also proposes an SPI for its outgoing (and the initiator's incoming) SA, which the initiator agrees to after
  checking.

The above scheme seems more like a trial and error than a negotiation. Logically, I would expect the responder to chose a value for the SPI that is not currently in use for its incoming SA, and send that over to the initiator to record in its SAD and encode the same in all future AH/ESP payloads it sends to the responder over this SA. My questions are as below:

Is the above description actually how it takes place?
If yes, what happens in case the responder receiving the SPI from the initiator finds out that the SPI value is already in use?

Is the above description actually how it takes place?

No; it works as you suspect.  Each side chooses the SPI to use for the incoming SA; that is, how the other side marks encrypted packets that are encrypted with this SA; in the initial quickmode message, the initiator specifies the SPI that will be used for encrypted packets going to the initiator, in the response packet, the responder specifies the SPI that will be used for encrypted packets going to the responder.  This is done specifically so that, in either case, the decryptor can select SPI values that are convenient to look up; for example, it may chose to place an index into a 'decryption table' into the lower 16 bits, say (and yes, there are implementations that do that).

  If yes, what happens in case the responder receiving the SPI from the initiator finds out that the SPI value is already in use?

While (as above) the assumption behind this question is wrong, there is a nontrivial answer here, and so I'll answer that.

As above, the initiator selects its SPI first (that is, the SPI for its incoming packets), and the responder then selects its SPI.

Because of how IKEv1 derives keys, if the responder selects the same SPI as the initiator, the keys for the two SAs (going in the opposite directions) will be the same; depending on what transforms are negotiated, this can be disastrous.  I don't believe there's any requirements, but I know of at least one implementation that will, as a responder, always select a different SPI then the initiator, and as an initiator, if it sees the responder selected the same SPI, automatically close the connection without encrypting anything.


Since the sbox is affine, you can view $s(v)=mv+b$ where $m$ is a 8-by-8 matrix and $b$ and $v$ is a dimension 8 vector over $F_2$. I will show you how  to find $m$ and $b$ in Pari-GP. If it is not clear how to use that combined with the description of AES to create an even bigger linear equation and solve, ask.

Write $\mathbf{0} =(0, 0, 0, 0, 0, 0, 0, 0)$.
Note that $s(\mathbf{0}) = b$, so all that is left to do is find
$m$. Define
$$l(v) = s(v) + s(\mathbf{0}) = mv + b + m\mathbf{0}+b=mv + b + b = mv$$
Note this is a linear function:

s(n) = sbox[n+1] \\ pari-gp is 1-indexed
l(n) = bitxor(s(n), s(0))
a = 10
b = 37
print(  bitxor(l(a),l(b)) == l(bitxor(a,b))  )

will output 1 (True in Pari-GP). To find out what the matrix is,

m = matrix(8, 8, {j}, {i}, {
    ei = 1 << (i-1);
    ej = 1 << (j-1);
    bitand(s(ei), ej) == ej
})

print(m)

which outputs

[1, 0, 0, 0, 0, 1, 0, 1;
 0, 0, 0, 1, 1, 0, 0, 1;
 1, 1, 0, 1, 1, 0, 1, 0;
 0, 0, 1, 0, 0, 1, 1, 0;
 0, 1, 1, 0, 0, 1, 1, 1;
 1, 1, 1, 0, 1, 0, 0, 1;
 0, 0, 1, 1, 0, 1, 1, 0;
 0, 0, 1, 0, 0, 1, 0, 1]

Note that because of how the indices work it is a little weird to read. The 128-th entry in your sbox, which corresponds to the vector $(0, 0, 0, 0, 0, 0, 0, 1)^T$ is 179, and the last column is $(1, 1, 0, 0, 1, 1, 0, 1)^T$ and binary(179) = [1, 0, 1, 1, 0, 0, 1, 1].


cryptographically signed streaming data On a high level the question is: how does one cryptographically sign streaming data?

Here is the context:

a number of people are continuously streaming data to me
the data is public and does not necessarily need to be encrypted
I would like to confirm that it is indeed them sending the data
I would like to compensate them (perhaps a payment on a blockchain to a public address)

What is the general strategy (or is there a standard?) to achieve this?  Here are some rough thoughts:

Alice signs contiguous chunks of data with her private key, I confirm it comes from her with her public key and can encode some rules to pay her (as identified by her public key).

Are there papers or further reading or I'm I on the wrong track?

This is very similar to establishing transport security with entity authentication. In other words, this would be much like TLS, except that in this case the client seems to require authentication rather than the server.

Still, using TLS with client authentication would probably solve your needs. Sure, it would also encrypt the streams, but that should not necessarily pose a problem. Otherwise you could replace the encryption and authentication with just HMAC and skip encryption.

Otherwise it would be a very good idea to study the TLS handshake and work out how the entity authentication works and how the shared session keys are established. Once the session keys are established they can be used to authenticate the records / messages in the stream. These are just blocks of data that together form the stream.

Beware that designing / implementing transport security is fraught with danger and should not be attempted without a very good understanding of the subject.

Note that SSH is usually more geared towards client authentication rather than TLS, which requires server authentication. So SSH might be a better transport security protocol when it comes to fulfilling the requirements. I'm however less at home with the current security details of SSH.

Another option would be to sign the data before sending (application level security rather than transport security). This would let you verify that the stream was delivered by a certain entity even after transport. If this is a valuable property depends on your usage scenario; it might be a very dangerous one as well - others would also be able to verify that it was delivered by the entity that signed it after all.

This seems to be the current road you're on; however in this scenario you might as well sign the whole stream / file rather than blocks. Otherwise you would just be designing a pretty bad transport mode security without forward secrecy, a lot of overhead and a proprietary messaging layer.


What is the difference between 'completeness' and 'soundness' in ZKP? I'm reading Matthew Green's great blog, especially the Zero Knowledge Proofs: An illustrated primer post and I'm wondering what is the difference between completeness and soundness?

In the post, there is this part:

Completeness If Google is telling the truth, then they will eventually convince me (at least with high probability).
Soundness Google can only convince me if they're actually telling the truth.

Can I have some explanation? I don't understand the difference.

The two notions are not specific to ZK, so it is in fact better to try to understand it in the context of general proof systems.

Soundness: the proof system is truthful, so whatever it proves, it is true.

Completeness: the proof system is comprehensive, so it can prove all true statements.

You can have completeness without soundness: if the proof system proves everything including falsity, obviously it is complete but not sound.

You can have soundness without completeness: if the proof system proves nothing, obviously it is sound (after all, it never proves any falsity), but not complete.


For a hash over a finite space without size reduction, is a public permutation sufficient? Suppose the application is a Lamport signature scheme.

Is the following a secure hash $\{0,1\}^n \rightarrow \{0,1\}^n$?
$$
H(x) = x \oplus P(x)
$$
where $P$ is a public permutation that permutes an input of length $n$.

Lamport's signature requires a hash function $H$ that is a one-way function. So your question is whether $H(x) = x \oplus P(x)$ is one-way when $P$ is a public permutation.

I will assume that $P$ is a public random permutation (a.k.a., an ideal permutation). In that case, yes the construction is one-way. It is very closely related to the Matyas-Meyer-Oseas (MMO) construction of a collision-resistant hash function from an ideal block cipher.

To hash a sequence of blocks $m_1 m_2 \cdots$, the MMO construction works by iterating the function $s \gets E(s, m_i) \oplus m_i$, where $s$ is the continuously updating internal state and $E$ is an ideal cipher. If you could find inverses in $H(x) = x \oplus P(x)$, for a public permutation $P$, then you could easily find collisions (even second preimages) in an MMO hash. Since MMO hash is provably secure in the ideal cipher model, this impiles that $H$ is one-way:

Consider a 2-block message $m_1 m_2$ and its hash which is computed as:

$s_1 = E(s_0, m_1) \oplus m_1$
$s_2 = E(s_1, m_2) \oplus m_2$

To find another message that collides with this one, pick $m_1' \ne m_1$ arbitrarily and set:

$s'_2 = E(s_0, m_1') \oplus m'_1$

If you had an $m'_2$ that satisifed

$s_2 = E(s'_1, m_2') \oplus m'_2$

then $m'_1 m'_2$ would be the desired collision. Note that everything in this expression is known except $m'_2$, and so $E(s'_1, \cdot)$ is a public random permutation. So the task reduces to that of finding preimages of a function of the form $x \mapsto P(x) \oplus x$, where $P(x) = E(s'_2,x)$.


How are Rijndael's S-Boxes generated? Wikipedia: Rijndael's Forward S-box

I'm writing C Code to generate S-boxes but I'm stuck.

Would you mind explaining one entry of the S-box? (say for x = 0x2). Here is what I got.

The inverse of $2$ in $GF(2^8)$ for polynomial $x^8 + x^4 + x^3 + x + 1 = 142$ (in decimal). Now if I apply the affine equation, it results in $86$ (0x56). What's wrong with my approach?

The additive constant for S-Box = 0x63.

In case it helps and/or makes sense, here's my C code.

In your code you use the modular inverse with the respect to the modulus 0x11b, which is an operation quite different from taking the inverse in the field GF(2^8).

For getting an idea what you have to do instead, take a look at finite field arithmetic in the wikipedia.


ECDSA signature of a random 32 byte number vs. the hash of the number I'm working on an application that involves signing a 32 byte random number generated by the OS. Assuming the RNG works as intended, is it safe to sign the random number itself rather than a hash of the random number?

I'm asking because time is an issue and -if possible- I would like to avoid the few ms it takes to do the hashing.

Thanks!

Yes, but you probably need to use a cryptographically secure RNG from your OS. Otherwise the input to the signature generation function may be mathematically linked, and the security of the system is not guaranteed. It is of course wise to use a 256 or higher curve, otherwise the security provided by the random number may be lowered.

Besides compressing the input, the hash is used to generate pseudo-random input to the signature generation function. It removes any mathematical links between the input values as cryptographic hash functions are one-way. However, using a small enough, random / independent values should already meet these requirements.

Random number generation by the OS is likely to be significantly slower than performing a single hash over a single block of input.

In that sense you could think of using 128 bit numbers instead of 256 bits and perform full ECDSA on that. You could also think of using deterministic ECDSA as specified in RFC 6979. These changes may well have a larger impact than removing the relatively fast hash from ECDSA. And you'd still be standard-compliant to boot; all of the security requirements on ECDSA would still be met.


How can I generate key scheduling for AES 256 bit key I want to implement AES algorithm,instead of 128 bit key encryption I wanted to do it for 256.But I’m stuck at point creating scheduling for 256 key generation.
Can anyone help in this.

I agree with @poncho, you have to read FIPS 197 (https://nvlpubs.nist.gov/nistpubs/fips/nist.fips.197.pdf). You should look on paragraph 5.2 Key Expansion. This one have a pseudo code. Also you can look on implementation in Go's runtime (https://github.com/golang/go/blob/master/src/crypto/aes/block.go).


RSA: Does it matter if you use e or d to encrypt? In RSA: Suppose I have already chosen p,q and constructed phi(n).

Now my question is if it’s important whether I encrypt with e or with d?
I don’t think so, e.g. because when encrypting I take plainoneofthe2numbers = cipher and then decrypting I take ciphertheotherofthe2numbers = plain, which is the same as taking plainoneofthe2numberstheotherofthe2numbers, which is the same as plainoneofthe2numbers * theotherofthe2numbers and since in multiplication both sides can be switched there doesn’t seem to be any possible difference whether e or d was “oneofthe2numbers”.

However our lecturer said that e is to encrypt and d is to encrypt (might have said so for pedagogical reasons), so now I’m unsure.
In addition his slides say that when signing a message the roles are reversed. So that you encrypt/sign with d, but decrypt/verify with e. However if there really is no mathematical difference in their role in the decryption/encryption process this differentiation wouldn’t really be needed. (I realize that when signing “key-knowledge” is reversed, meaning the key to encrypt is secret, and the one used to decrypt is public, but my question only concerns the mathematical aspect.)
Thanks for any answers

EDIT: It has been said now by both commenters that knowing d and n, with the secret key being a small e it would be possible to factor N.
Can somebody explain how? Aside from brute-forcing phi(n) and then going from there?
(Pls note that I never suggested using a small e as the private key, but was just interested in the mentioned hypothetical.)

Yes it matters if one uses $e$ or $d$ to encrypt. One must use for encryption whichever of $e$ or $d$ is published as part of the public key, and the other exponent must not be chosen small.

There is however no problem in choosing $d$ small (or large and random), publishing it, and computing $e$ from $d$ and the known factorization of the public modulus $N$; that will in all likelihood make $e$ large, for otherwise correct choice of $N$ and $d$; that is merely changing the letters used to name the exponents.

Update per comment: whatever $e$ or $d$ is chosen first, successfully computing the other exponent such that $ed\equiv1\pmod{\varphi(N)}$ insures that both $\gcd(e,\varphi(N))=1$ and $\gcd(d,\varphi(N))=1$. Thus if we choose large enough $N$ of known secret factorization, then $e$ large and random with $\gcd(e,\varphi(N))=1$, compute $d$, publish $(N,d)$, then it is fine to use $d$ to encrypt and $e$ to decrypt; we have only changed the letters used to name the exponents, and tested that the published $d$ verifies $\gcd(d,\varphi(N))=1$ in a slightly unusual way.

In RSA, a public key is made public, hence its name. Usually that is taken to be $(N,e)$. It is critical that encryption is with the exponent in that public key, because encryption must be public, and decryption private.

Also: as pointed by SEJPM's comment, $e$ is often chosen small ($e\le65537$ is typical); that makes $e$ is guessable; hence publishing $d$ and using it for decryption would allow anyone to decipher by guessing $e$ . As an aside, knowing $d$ and $N$, and that $e$ is small, it is possible to factor $N$ . Therefore, if in this comment "construct two new keys" is about reusing $N$ after $(N,e)$ or $(N,d)$ was published and the other exponent was small, published, or otherwise leaked, that's insecure.

Note: contrary to the question's statement, encryption of plaintext $M$ should not be as $M^e\bmod N$. One reason is that a guess of $M$ can be checked by anyone knowing $(N,e)$, that is by hypothesis any adversary; which can be a disaster e.g. when $M$ is a name on the public class roll. That's why we use RSA random encryption padding (e.g. RSAES-OAEP).

Final note: $p=3$, $q=5$ makes a much too small example for RSA: raising to the power $e$ or $d$ modulo $N=15$ has the exact same effect for all valid choices of $e$ and $d$, which all verify $e\equiv d\equiv1\pmod4$ or $e\equiv d\equiv3\pmod4$ ! In fact, until $p$ and $q$ have at least a few dozen decimal digits each, $N$ can be factored easily, thus there's no security, and size requirements on $e$ or $d$ are pointless.


Understanding how to proof an encryption scheme is perfectly secret Consider each of the following encryption schemes and state whether
  the scheme is perfectly secret or not. Justify your answer by giving a
  detailed proof if your answer is Yes, and a counterexample if your
  answer is No.

  Consider an encryption scheme whose plaintext space is
  $\mathcal{M}=\{m\in\{0,1\}^\ell \mathrel{|} \text{the last bit
of $m$ is $0$}\}$ and key generation algorithm chooses a uniform key from
  the key space $\mathcal{K}=\{0,1\}^{\ell-1}$. Suppose $\mathit{Enc}_k(m)=m
\oplus (k\parallel 0)$ and $\mathit{Dec}_k(c)=c\oplus (k\parallel 0)$.

$\newcommand{\given}{\mathrel{|}}$The definition of perfectly secret which states:
An encryption scheme $(\mathit{Gen}, \mathit{Enc}, \mathit{Dec})$ with message space $\mathcal{M}$ is perfectly secret if for every probability distribution over $\mathcal{M}$, every message $m\in \mathcal{M}$, and every ciphertext $c\in \mathcal{C}$ for which $\Pr[C=c]>0$: $$\Pr[M=m\given C=c]=\Pr[M=m].$$

We first compute $\Pr[C=c\given M=m']$ for arbitrary $c\in \mathcal{C}$ and $m'\in \mathcal{M}$.
\begin{equation*}
\begin{aligned}
\Pr[C=c\given M=m'] & =\Pr[\mathit{Enc}_K(m')=c]=\Pr[m' \oplus (K\parallel 0)=c] \\
& =\Pr[(K\parallel 0) = c\oplus m']=2^{1-\ell}\quad (1)
\end{aligned}
\end{equation*}
where the final equality holds because the key $K$ is a uniform $\ell-1$-bit string. Fix any distribution over $\mathcal{M}$. For any $c\in \mathcal{C}$, we have
\begin{equation*}
\begin{aligned}
\Pr[C=c] & = \sum_{m'\in\mathcal{M}} \Pr[C=c\given M=m'] \cdot \Pr[M=m'] \\
& = 2^{1-\ell} \cdot \sum_{m'\in \mathcal{M}} \Pr[M=m']=2^{1-\ell}\cdot 1=2^{1-\ell}\quad (2)
\end{aligned}
\end{equation*}
where the sum is over $m'\in \mathcal{M}$ with $\Pr[M=m']\neq 0$. Bayes' Theorem gives:
\begin{equation*}
\begin{aligned}
\Pr[M=m\given C=c] & = \dfrac{\Pr[C=c\given M=m]\cdot \Pr[M=m]}{\Pr[C=c]} \\
& = \dfrac{2^{1-\ell} \cdot \Pr[M=m]}{2^{1-\ell}} = \Pr[M=m]
\end{aligned}
\end{equation*}
Hence we conclude that this encryption scheme is perfectly secret.

MY QUESTION: I tried to follow the set up for the proof of the One-Time Pad being perfectly secure. However, I don't really understand the logic behind the proof (assuming what I did was correct). Can someone clear up why this technique is correct?

Where is the problem? Your reasoning seems correct, but you obviously are uncomfortable with probability (at least).

You used the definition of the encryption scheme in (1) and then the standard expression of a probability with respect to the set of messages forming a partition in (2), which is valid since it includes all the messages with nonzero probability and their probabilities must sum to 1.

You then applied Bayes theorem. Standard stuff, really. Maybe you need a refresher in probability.


Pad ciphertext with arbitrary number of bits I have a symmetric-key encryption scheme. I think the output from this scheme (MAC + IV + CBC ciphertext) should already be practically indistinguishable from random, but I would like to pad the output to an arbitrary number of bits and have it still look like noise (I will be using the output for steganography). It would also be fine to pad the input.

What is the best cipher to use for this?

It seems to be difficult to do with AES without putting a plaintext length somewhere in the output. Perhaps I could use a stream cipher where I can decrypt part of the message to find the length?

After a bit of additional reading I realized that appending noise to the ciphertext doesn't affect decryption of the plaintext part. The solution is therefore quite simple:

Encrypt length + plaintext with AES, then pad the ciphertext with as many random bits as necessary. HMAC the result including the random bits.

To get the plaintext back, first validate the MAC, then trim the ciphertext down to the nearest AES block size. You can then decrypt the result back to length + plaintext + garbage.


AES Secure key generation and storage I have a client-server application, which is transferring data between its components in a secure way. I currently use AES algorithm with CBC mode to transfer data and file. This is the scenario: Client ask for data(file or plaintext), server takes the request and encrypt data with a iv/key pair and sends encrypted data to the client. Client always stores data encrypted. Client is a per user application. So for this reason, client should open the files, should read data even in offline mode. (Server application is .Net based, Client is Delphi)

What I need is a secret key generation mechanism, that is secure and changeable between client and server, something that is related to the current user ('user1', 'user2' etc). I'm not experienced in cryptography, So I will be waiting for the experienced one's advices.

Thanks in advance

Edit: I will try to explain my problem in more details. We have a client application, that is opening some files in some format (say 3dsmax). Those files are downloaded from  a database in server and only authenticated user can download this files. But even if authenticated user download this one, files shouldn't be copied to other computers, disks. because those files contain strictly worked models (say 3d models) and need to be encrypted; and there is another case that when client sqlite database need to be updated, we send scripts to the client  in an encrypted way and client decrypts and executes, saves values encrypted.

We do all of this work. Perhaps I asked the question not in a proper way. By key generation I mean that, how do we create a mechanism to securely and consistently exchange the data? Preferably without key storage but some mechnaism that creates the key in runtime but in both sides by using userids, licence keys etc... we store user information both in client and server. I hope I could explain

In practice you should use the tools already provided.  SSL/TLS and by extension HTTPS are very powerful tools that provide proper implementations of key exchange, authentication and privacy.  As far as I can tell this solves all of your problems.

AES-CBC alone is problematic.  As Thomas pointed out you lack authentication.  A common solution to this problem is using an HMAC and here is a good discussion of HMACs and encryption.


Triple DES in Firefox - in practice Reading about triple DES and understanding the principles, I am still curious how Firefox defines their three keys for the encryption/decryption.
Suppose that the user saves his passwords in the browser without a master key, are the default keys randomized and saved to the separate file?
Also, if the user enters a master key for the encryption, which of the three keys will the master key be and why?

I'm a developer myself and technical details in a programming sense would be greatly appreciated.

I've been fooling around with a helper I found for cracking passwords in FF and added it to my program, but it really bugs me that I have no real knowledge what is going on.

Thanks, please don't flame me too much!

I assume you are asking how the password a user enters to unlock their saved user data is translated into the keys used by 3DES?  According to this link DES-EDE-CBC, which is only two-key 3DES.  The first and third keys are set equal to each other, resulting in two keys of 56 bits or a total size of 112 bits.

To get that key material from a password, a Password Based Key Derivation Function (PBKDF) is usually used.  The details differ depending on the algorithm, but the key idea is to take the password and run it (one or more times) through a cryptographically secure hash function, which has a fixed size output.  The output is usually longer than what you need, so you just take the first $k$ bits to make a key of size $k$.

Again accoring to the link, Firefox appears to use a SHA1 HMAC with a random salt as the key.  This would output 160 bits, of which you only need 112.

If the user does not set a master password, then the password is actually blank, but with a random salt.  That is equivalent to what you said, i.e. having a random key saved to a file.


Create big random number from 2 smaller numbers? If I have  2 true random numbers from atmospheric noise or a different source.
Suppose $x= 299$ and $y= 499$.
Is it possible to create a bigger number with $x$ to the power of $y$?

Can I use different sources like, pressure sensor + light sensor + movement sensor and calculate $x^{y^z}$ for a true random number?

Raising to powers isn't how you'd want to go about it. For instance, lets say my true random number generator gave me x=3 and y=5, and lets say it usually generates numbers between 0 and 7. That's 3 bits of randomness per value. If I generate two of them, I will have 6 bits of randomness. If I output x^y as the result, then it has the potential to output anything from 1 to 823543 (7^7). This is around a 20 bit value coming from only 6 bits of entropy (the technical term for randomness). This will be very biased.

A better way, if your RNG (random number generator) outputs with a range of a power of 2 (1 to 8, 0 to 15, 20 to 23, etc), then you can get the random bits and simply concatenate to get a larger number. For example, from the earlier example, 3 can become "011" and 5 can become "101". The resulting number can then be "011101" or 29. This (assuming the RNG is uniform across 0 and 7) will be uniform across 0 and 63.

However, if your RNG is biased, or outputs with a range that's not a power of 2, then you can use a cryptographic hash function to "mix" the randomness. If your RNG outputs uniformly between 0 and 99 (a range of 100), then each value is 6.6439 ( $log_2(100)$ ) bits of entropy. You can collect enough values to have at least 256 bits (in this case, 39 values) and run them all through a 256 bit hash function (such as SHA256). The output of this will be 256 uniformly distributed bits.

In the last example, it's important to put a delimiter between the random values before hashing them. For instance, if you get the values 3, 6, 5, and 1, then hash "3,6,5,1" not "3651".

Of course, this all assumes you want the output to be truly random. If you're okay with pseudorandom, then you can use the output of your RNG as the seed of a PRNG at a much greater speed.


Proof that a encrypted file has the same content as an (existing) original Assume that Alice has a file F which she is going to send, in encrypted form, to Bob. Alice possesses F and the public encryption key K of Bob in form of an X509-certificate.
She generates the file E using the encryption algorithm CNT_3DES, BitsInKey = 192 (RSA PKCS#1 encryption method).
She sends to Bob the file E through a certified mail system which will get a digital signature and a time stamp from an external authentication authority. Therefore it is possible to include in the body of the mail any information, including hash codes, that will be accepted as well known before the creating time of the mail.

After some time Alice has to proof to Mike that the file E send to Bob has the same content of the file F. But Mike does not have the private key of Bob for decrypting the file. And encrypting the file F now produces a different file than E since encryption adds a random padding on encryption stage. How can this proof be given from Alice to Mike?
As explained, it is possible to include in the body of the mail any useful information that will be necessary for this proof.

I hope that I explained my problem in a sufficiently clear way. And sorry for my poor English.

Retaining the 3DES encryption key would probably do it. Now simply use the same IV as before and encrypt the file; the IV is only random when it is initially chosen. Alice could also encrypt the key and store it together with the message.

You'd have to prove that you used the same key. That's no problem for larger messages in CBC mode where the possible plaintext is known, but for good measure, I'd include a MAC over the IV and ciphertext in the mail header.

Alternatively, and possibly better than using a MAC, is to transmit the random padding with the message and store the secret key. That way you can regenerate the wrapped key by pairing the padded key with a raw RSA operation, proving that it was that specific key you used.

It might be better in the sense that creating a covert channel is harder if all the information is shown to Mike. It has the drawback that it requires access to raw RSA operation, which may not be directly available to you.


SHA-1 colission resistance proof I'm searching Why the SHA-1 is collision resistance? Anybody could help me with the proof or say me where I can find this proof?

There is no such proof, on the contrary it has been proven that SHA-1 does not possess the ideal 80 bit collision resistance. Rather it is down to around 61 bits of resistance, uncomfortably close to being practically exploitable, and even if no further weaknesses are found advances in computing power are almost guaranteed to make it reasonably practical within a decade or two.

This weakness is only to collision attacks, that is attacks where the attacker can construct two different data pieces that has the same hash value, and thereby break some security measure, in some use cases that is relevant and SHA-1 is therefore problematic, in other cases it isn't and we can afford to be a bit more relaxed about the use of SHA-1 as its pre-image resistance doesn't seem likely to drop to a critical level any time soon.

In any case though, for new applications you are best advised to avoid using SHA-1 and earlier, instead use for instance one of the SHA-2 functions.

As for the theoretical foundation, SHA-1 is a Merkle–Damgård construction, such a construction is proven to be a perfect hash given that the one-way compression function it is built on can give some similar guarantees. It was presumably for this reason that Merkle–Damgård constructions became popular, but ultimately it is the one-way compression function that is the critical part, the Merkle–Damgård proof only tells us that the much simpler container format is not borked. You can find loads of cryptanalysis reports for any popular hash function, but unless you are a pretty sharp mathematician with a lot of time to kill they are probably not going to be of any use to you.


Security of a block cipher if double encryption $E_{K_2} \circ E_{K_1}$ is always single encryption $E_{f(K_1,K_2)}$ If there always existed a $k_3$ such that $\operatorname{DES}(k_2, \operatorname{DES}(k_1, M)) = \operatorname{DES}(k_3, M)$,  how would that affect the security of $\operatorname{DES}$?

This question was tested years ago by Kaliski at. al Is the Data Encryption Standard a group? (Results of cycling experiments on DES as;

Is DES closed under functional composition?

They applied the cycling test and concluded that DES is not a group. Therefore, we don't expect  that $$\operatorname{DES}(k_2, \operatorname{DES}(k_1, M)) = \operatorname{DES}(k_3, M)$$

As noted in the article, if there was such functional composition then a known-plaintext attack with $2^{28}$ would be able to break DES, on average.


NIST implementation of the Lucas primality test The NIST standard FIPS 186-4 describes an implementation of the Lucas primality test in section C.3.3.

I can follow the algorithm but I am puzzled by step 6.2:

$V_{temp}=\frac{V_{i+1}^2+DU_{i+1}^2}{2} \bmod C$

Where does this expression come from?

I do understand this is the step that computes $V_{2n}$ from $V_n$ and $U_n$. However, all relations I can find for Lucas sequences of any use in the binary expansion are in the form:

$V_{2n} = V_n^2 - 2Q^n$

Is there perhaps a way to go from this expression to the one used in the NIST implementation (with $Q = \frac{1-D}{2}$ and $D$ taken from the sequence $[5,-7,9,-11,\dots]$)?

Thanks to the references provided by @fgrieu I found the relevant equation in "New
Primality Criteria and Factorizations of2^m+-1" by Brillhart-Lehmer-Selfridge.

In there, Equation (14) says:

$2V_{r+s} = V_rV_s+DU_rU_s$

Which is trivial to demonstrate, given that $D=(\alpha - \beta)^2$.


Find out which keying option is being used in Triple DES? As far as I know, there are three standard options for the three keys $K_1$, $K_2$ and $K_3$ used by 3DES:

Three distinct keys.
The first and last key are equal: $K_1$ = $K_3$.
Three equal keys: $K_1 = K_2 = K_3$

I wonder whether there is a way to find out which one of these options is (most likely) being used, given a set of known (plaintext, ciphertext) pairs. The attack does not need to reveal the keys; the goal is simply to find out which keying option is being used.

Currently, the only method I could think of consists of trying to recover the key. That is, apply known attacks on the third and second keying options. For example, a brute-force attack of complexity $2^{56}$ followed by a chosen plaintext attack of complexity $2^{57}$.

So the question is really: is there a way of doing this more efficiently, without having to figure out the keys. If that's not possible, (how) can the above mentioned method be optimized?

Actually, there's no known way (assuming practical amounts of computing power) to distinguish keying methods 1 and 2.  You mention a "brute-force attack of complexity $O(2^{56})$ followed by a chosen plaintext attack of complexity $O(2^{57})$", there's no obvious way to frame an attack against either of the first two options in this matter; you can't do a brute force attack on one of the keys, because there's no obvious way to confirm a guess on a potential key (other than immediately doing a brute force attack on another of the keys, in which case you're really talking about an effort of $O(2^{112})$.

On the other hand, it is feasible (if moderately difficult) to distinguish the third option from the other two.  This third option is essentially DES; a brute force search of all possible $2^{56}$ DES keys will distinguish it given a single plaintext/ciphertext pair.  In addition, with sufficient known plaintext/ciphertext, linear cryptanalysis can make the distinguishing effort moderately easier.

The best work I known on linear cryptanalysis is this paper; using approximately $2^{43}$ plaintext/ciphertext pairs (that is, a few trillion), they are able to distinguish DES from a random permutation with about $O(2^{39})$ DES computations, which is moderately cheaper than simple brute force.


Converting RSA.pub keys to word list RSA keys are notoriously blobs. I'm looking to make something more human readable.
I want to take the mathematical operation and convert it to a number that can be easily expressed as a series of words against a set indexed wordlist.
The first step is converting the RSA.key file to a binary number. Next step is subtracting, or adding one, and dividing by 24. Number theory.

Once that number is obtained, the words that make up the dictionary, and their respective numerical value, or even the raw value of the word, depending on its position, say for instance, "helpful" could have an index value of 1171 or could be given a value of "85121662112" based on a concatenation of the index value of the letters against a standard alphabet. These words are operated on, exponents, multiplication, division, addition, etc., until the original value of the RSA key can be recreated. This should allow the RSA keys to be easily checked for manipulation and verify the authenticity, or easily communicated by phone.

Any thoughts?
It isn't exactly pure cryptography, but cryptographic adjacent.

My question is "Does anyone have any input on pseudocode or python implementation?"

I think the comments bring up some good points that make this potentially intractable.  However, I figured I'd give the initial thoughts that come to mind.

This immediately reminded me of Bitcoin BIP-39, which might be a part of your impetus for asking, since it's pretty much identical to what you described, but since you didn't mention it and its reference implementation was in Python, it seems worth calling out.

The obvious downside to this approach is that it would take a considerable number of words to encode an RSA key.  And I know from experience that even the 24 words for a Bitcoin private keys (256 bits) are a pain to communicate verbally.

Something like Base58Check encoding would perhaps be a bit more compact, and still lend itself somewhat to be communicated verbally (in terms of minimizing/auto-correcting mistakes), but would still very long.

You could potentially look into compressing the public key and then using some sort of encoded like the above options, but the answers to that question still don't get you down to 256 bits which, again, is already cumbersome to communicate verbally.

All-in-all I think it depends on the level of effort you're expecting users to put in and the level of technical knowledge they having.  Two technologists communicating a very long Base58Check string would be a huge pain but would likely work.  With any other scenario I expect a mnemonic phrase might be better, but you'd probably have to find something better than the BIP-39 definition.  And even then I'm not sure you'd get to a level that wouldn't cause people to switch to another method (e.g. emailing a PEM file).


Save the last cycle in GCM GHASH calculation I need to implement GCM GHASH in hardware, using FPGA. The data bus is 640 bits, so I will use 5 adder/multiplier blocks in parallel. The message size is fixed and AAD is 0.

A little example: message = 5 x 640 bits.

cycle 1: process 640 bits (add/multiply)
cycle 2: process 640 bits (add/multiply)
cycle 3: process 640 bits (add/multiply)
cycle 4: process 640 bits (add/multiply)
cycle 5: process 640 bits (add/multiply)
cycle 6: process Len 0||C (add/multiply) and xor all results

In the above example, for 5 cycles of data I need 6 cycles to calculate GHASH. The extra cycle is necessary to insert LEN(0||C) in the data flow.

Problem is, I have a continuous data flow and I cannot interrupt it to insert LEN 0||C.

Is it possible to manipulate the GHASH in a way that the processing of LEN(0||C) could be made in advance and just added to the end of processing, saving one processing cycle?

Just to explain better, my architecture is based on this paper:
http://ieeexplore.ieee.org/xpl/articleDetails.jsp?tp=&arnumber=5619894&queryText%3DFPGA+parallel-pipelined+AES-GCM+core+for+100G+Ethernet+applications

The add/multiplied data from each adder/multiplicator is saved on a Q memory that have 4 positions. So, at the end of the data, the Q memories positions are xored. The 5 results are then xored and we have the GHASH(CYPHER_TEXT).
I have a C model that processes the len_C adding it to the end of the flow, so I know the GHASH(CYPHER_TEXT) result.

In my verilog model, I have almost the same Q memories contents at the end of the data processing, the only difference is caused by the len_c processing.
The values are:

C model ghash: 0x72a61c9521a6f05da7b16d8fb6b2e115
Verilog model GHASH without processing Len_C: 0x3f1cdbad43034cbfc4d09060e08678e7
My Len_c (bit mirrored to work with my architecture): 0x00980000000000000000000000000000
H: 0x6909696eb6211e31212d7d0a3e07b836

I tried the calculations you proposed but it not works. You guys could please take a look?

Well, the GCM tag can be rearranged as $Tag = (Len(C, A) \times H) \oplus \textit{Other Stuff}$; if the length of your ciphertext (and additional authentication data) is consistent, you could precompute $Len(C, A) \times H$, and xor that in along with everything else in the final step.

One note: the (add/multiply) that you do in cycle 6 has the side effect of multiplying the result of the GHASH from the ciphertext by $H$; if you eliminate that multiply, you'd need to somehow get the same effect.


Generate an insecure public / private key pair I am looking for a way to generate an "insecure" public key pair. and by insecure I actually mean a pair that is breakable using brute-force (or other encryption) methods.

As far as I know PGP started with 128bit-keys. and at this point I can only find tools to generate keys using 1024bit or more.

Is there a way to generate a key pair with lets say 56bit (or even less) that will still generate a valid Certificate than can be used in PGP messages?

I am not sure to fully understand your question, but what you can do is the following: take $r=2^{512}$, and compute $p=r+\delta$ and $q=r-\delta^\prime$ such that $p$ and $q$ are prime numbers, and $0\leq \delta, \delta^\prime < 2^{32}$. Then you have an RSA key at you disposal that can be broken by a brute force search on $\delta$, which should take strictly less than $2^{32}$ trials.


Is there a security analysis of CryptDB? It's interesting to see critical thinking being applied to CryptDB in contrast to all the hoopla around it here. CryptDB is not a major theoretical breakthrough but potpourri of technologies to make it work. But then: I am curious whether there has been a formal security analysis done on CryptDB. All over the web it is just being praised without seemengly any thorough analysis.

On a side note: If there is none, I would like to take it up, but I am new to security analysis, so: Is there a good reference paper for carrying out security analysis on some crypto implementation?

A quick glance at their most recent paper shows some security analysis. Secton 2 talks about some different threats, what guarantees they can provide, etc. Section 8.3 also evaluates the security of the system. This may or may not be what you are looking for, you'd have to decide for your self.


Good key update algorithms for key evolving schemes In schemes like SAKE(Symmetric-key Authenticated Key Exchange) , the master keys (used to authenticate parties and generate session keys) are evolving, ie undergo transition $K=update(K)$.

What is a good candidate for $update(.)$ function?

Would $K=\operatorname{AES}(K, S)$ have "good properties", with $S$ being arbitrary block-length constant?Author of the algorithm state that $update(.)$ should be irreversible function.

AES is not irreversible, at least not when the key is known. I'd rather look at a PRF (Pseudo Random Function) rather than a PRP (Pseudo Random Permutation) such as AES.
A good PRF is HMAC. HMAC also has the nice properties of having no limit to the input message and a rather large, although statically sized output.

Even more specifically you might want to use a Key Based Key Derivation Function (KBKDF) such as HKDF - which is based on HMAC. A HKDF specifically takes input keying material to create output keying material.
It might be that KDF functions are e.g. present in hardware devices. This means that they keying material could stay into the hardware device, while ciphertext or HMAC values are commonly exported.


How can I control the output of a hash function to output to specific data according to similarity? I do not know if the question lies exactly in that field but I'll give it a try unless rejection.

I want to study methods of applying LSH functions to feet in a specific area of digest values. Briefly i would like to control the results of hash functions such as "similar" inputs (similarity is defined by an LSH algorithm given a distance metric – i.e:hamming distance) fall to a specific value. That is, I want to control the output of LSH to result in a specific range of values.

Well, if the question is 'how do we select inputs to a cryptographical hash function so that the outputs are within a specific range', well, you're pretty much limited to:

Rejection methods -- that is, you hash the input with some salt, and if the resulting hash value isn't in the range you want, you keep on trying different salt values until it is.  For example, if you want the MSBit of the hash to be zero, you keep on trying different salt values until you find a hash with has an MSBit of zero.
Postprocessing methods -- that is, you hash the input as usual, and then map it into the range you want.  For example,if you want the MSBit of the hash to be zero, you simply take the result of the crpytographical hash function, and set the MSBit to zero.

If you're looking for a more efficient method of selecting hash inputs to constrict the hash output, well, they're not known to exist for cryptographical hash functions.  In fact, if there was a large, easily computable subset of inputs that generated a biased hash output, that would imply a cryptographical weakness of the hash function.  For example, to find a collision in the hash function, one could just take inputs from the subset, and hash those; if there was a bias in the hash outputs, one would find a collision with probability $0.5$ with a number of hashes strictly less than $1.17741 \cdot 2^{N/2}$ attempts (where $N$ is the size of the hash function); this is a weakness (although a small one if the bias is small, or it takes a large amount of computation to find elements in the subset).