Is Blowfish strong enough for VPN encryption? I'm looking at an OpenVPN connection between two sites configured to use 128 bit Blowfish in CBC mode, and trying to figure out how to assess the strength, but I just don't know enough of the maths.

I could ask this over on Sec.SE, but there I think the focus might be on whether it should use 3DES instead of Blowfish – here I guess I'm hoping for guidance as to relative strength of the algorithm, and whether a break is realistic when used this way.

Thomas mentioned some "theoretical weaknesses" that can happen with $2^{32}$ blocks of data with CBC mode and an 8 byte block cipher; I will explore more about what that weakness is, and its practical relevance.

In CBC mode, we effectively send randomized data through the block cipher.  However, there is a chance that it happens to encrypt the exact same data twice with the same key; this results in the exact same ciphertext block appearing in the encrypted output twice.  If an attacker finds this, then he can deduce the exclusive or of the corresponding plaintext blocks.

How likely is this to happen?  Well, after about $2^{32}$ blocks of data ($2^{35} = 34$ Gigabytes of data), the expected number of times for it to happen is about 1 (it might not happen at all, or it might happen 2 or 3 times); if you encrypt more data, it's expected to happen more often; if you encrypt less, it can still happen (but with a reduced probability of happening).

How much effort will an attacker have to go through to find those colliding pairs?  Well, not very much; the biggest difficulty that the attacker would have is just dealing with the multigigabytes of data, and that's quite feasible for a determined attacker.

How much is this information leakage a security concern?  Well, that depends entirely on the nature of the plaintext.  The attacker will see the exclusive or of pairs of 8 byte segments, however he has no control over where they might appear.  8 bytes might be enough for him to guess the underlying plaintexts (and then, it might not), and even if he did, we might not care if he can deduce 16 bytes of data out of 34 Gigabytes.  On the other hand, maybe we do care -- that's really up to the application.

Now, block ciphers with 16 byte blocks (such as AES and Twofish) don't have these concerns (this same weakness can be expected to take place after $2^{68}$ bytes of encrypted data; we will never need to encrypt that much data with a single key).  This is one of the reasons we advise people to use more modern ciphers; this observation might not be a concern for a particular user, but with a modern cipher, we know it's not a concern for anyone.


How to use cryptography to protect video from forgery? As Deepfake and other technologies make video anti-counterfeiting very difficult, I want to design a scheme based on cryptography to verify that a video is actually captured by the camera. At the same time, I hope this video supports truncation. For example, I have a video that takes one hour long, and if I intercept one minute without any other changes, then the video for this one minute is true.
A simple method is to use digital signature. The video stream or video frame captured by the camera is signed with private key, so that other people can verify it. However, in my application scenario, I hope anyone can capture a segment of the video and prove that the captured video is actually recorded rather than forged. It seems that the digital signature method is not suitable for this scene, because only when the video is complete, we can prove its integrity.
Message authentication codes (MAC) can also prove authenticity, but this requires the distribution of a secret.
Do you know any cryptographic primitives or schemes that can be used in this scenario?

Most video formats generate periodic key frames where the entire picture is rendered and then specify subsequent frames which are differences from the previous image.  This is beneficial because this dramatically reduces the amount of data that needs to be transmitted, while still allowing periodic seeking.
It would be possible to embed a cryptographic signature covering the previous or current key frame and its subsequent data, but the video format would have to support it.  This would be the least invasive way of doing the operation because without transcoding, a user cannot efficiently seek to any point in the stream other than a key frame.  Sometimes these offsets are stored in an index at the end of the file, and, assuming the format supported it, you could add an additional index for that purpose.  I cannot speak to the contents of video formats that would support this.
You would want to include as part of the signature some additional metadata, such as a stream ID and a key frame count or timestamp to avoid unexpected out-of-order editing and splicing.  You are also probably going to want to include the full header data and any other structural data as well.  The data included in the MAC of TLS is a good example of protecting the full record appropriately from tampering.
And, of course, all this verifies is that someone with the private key created the signature, not who that was or whether the data is accurate.  If your camera is not sufficiently tamper resistant, malicious parties will be able to extract the private key.  If the camera is tamper resistant but is presented with a false or misleading image to record, it will of course record false or misleading data.  Cryptography and security cannot prevent people from presenting false or misleading data as fact.  You'd definitely want to consult with a suitable expert in tamper-resistant systems to make the system as secure as is practically possible.


Elliptic Curve SSL performance: ECDHE and/or ECDSA? I have a question about the performance benefits (in terms of server-side CPU load) of ECC (Elliptic Curve cryptography) cipher suites in SSL/TLS.

It is a known fact that ECC is very good for performance, it offers a good "security / key length" ratio.

But ECC kan be used for 2 things in SSL/TLS sessions:

ECC key establishment: ECDHE algorithm.
ECC authentication: ECDSA algorithm with ECC server certificate.

So I am wondering: do you need the 'full' ECC package (ECDHE + ECDSA = ECC key establishment + ECC server certificate) to get a substantial performance gain with SSL, or does ECDHE (ECC key establishment) already provide the largest portion of the possible performance gain?

Or, to make this question less abstract, let's consider 3 SSL cipher suites:

a) Non-ECC cipher suite: TLS_DHE_RSA_WITH_AES_256_CBC_SHA256 (DHE-RSA-AES256-SHA256).
Here ECC is not used at all.

b) Partial ECC cipher suite: TLS_ECDHE_RSA_WITH_AES_256_CBC_SHA384 (ECDHE-RSA-AES256-SHA384).
Here ECC is used for DH key establishment, while RSA is used for server authentication (RSA server certificate).

c) Full ECC cipher suite: TLS_ECDHE_ECDSA_WITH_AES_256_CBC_SHA384 (ECDHE-ECDSA-AES256-SHA384).
Here ECC is used both for DH key establishment and for server authentication (ECC server certificate).

I assume that scenario C is better (performance wise) than scenario B, which in turn is better than scenario A.
But: where exactly would scenario B be positioned?

If scenario A = 1% (bad performance: high server CPU load) and scenario C = 100% (good performance: low server CPU load), then how far can you get with scenario B: 10%, 50%, 90% ...?

I hope the question is clear and that someone knows the answer or can point me to some documentation about this subject.

Thanks in advance!

Bert

It is hard to give a precise percentage as you expect because performances depend on the hardware platform. But let's get into the subject.

The only difference between TLS_ECDHE_ECDSA_WITH_AES_256_CBC_SHA384 and TLS_ECDHE_RSA_WITH_AES_256_CBC_SHA384 is the signature algorithm.

Whatever, one will have to generate an ECC key pair on the fly in order to perform an ECDHE. Then, this key pair will be signed using the certificate private key. If the certificate contains a RSA public key, then the generated ECC public key will be signed using RSA. Otherwise (i.e. if it contains an ECDSA public key) it will be signed using ECDSA. Also note that one will have to verify the peer signature on top of generating his own.

So your question is equivalent to comparing RSA to ECDSA, I suggest you to take a look at How do RSA and ECDSA differ in signing performance? and Signatures: RSA compared to ECDSA.


SIMON implementation, decryption issues I've been trying to implement the new SIMON block cipher in Ruby as a personal challenge. The spec didn't include a pseudocode version of the decryption but I thought I had it figured out. The code I wrote is located at https://github.com/Rami114/Personal/blob/master/Simon/Simon.rb

I've based this on the spec available at http://eprint.iacr.org/2013/404.pdf

Currently my encryption does not work (at all I'd say) which may be due to code issues or do to math failure on my behalf. Could someone please help me validate if the decryption is correct. Most notably the inversion of the rounds:

# f(x) ((LCS(x,1) & LCS(x,8)) ^ LCS(x,2))

def self.f (x, block_size)
  ((lcs(x, block_size, 1) & lcs(x, block_size, 8)) ^ lcs(x, block_size, 2))
end

def self.round_inv (x, y, k1, k2)
  x ^= k2
  x ^= f(y, N)
  y ^= k1
  y ^= f(x, N)
  return x, y
end

And the decryption function which I won't fully paste here as it's defined in the link above (the whole thing is only 200 lines long total so not a monster to read).

I have a stackoverflow question up at the moment which is specific to the way I'm currently converting strings to bignums and back (to accommodate the circular shift) but I didn't think that would be appropriate to this SE site.

Are there any glaring errors in my implementation? I'm by no means an expert in this.

E: the stackoverflow question I have up for code concerns: https://stackoverflow.com/questions/17785691/string-to-bignum-and-back-again-in-ruby-to-allow-circular-shift

From a quick read, there are a couple of potential issues.

decrypt_128_256 is iterating rounds in the same order as in encrypt_128_256, so the round keys are being applied in the wrong order on decrypt.
decrypt_128_256 needs to iterate through the round keys starting from the last round and working backwards.
68 rounds are being used for Speck128/256 (should be 72) - this won't stop it being symmetric, but it will stop it passing test vectors.

A reference you can run against is a really good idea - I tend to instrument all of the intermediate calculations on the reference and new implementations, pipe both sets of output to files and diff the output to see where things need fixing up.

As you've discovered the Simon/Speck algorithms are a wee bit short of reference code - I managed to bootstrap off the Speck128/128 example at the end of the spec to a working implementation of the Speck variants, and Simon was straightforward after that.

I've just pushed my Java implementations of Simon (and Speck), which you can use for comparison or runtime reference (it's in a feature fork of Bouncy Castle, so you should be able to build from the root with little trouble).


Is it possible to generate an infinite number of collisions given an infinite amount of strings? Let us assume that we have a string $w$ such that it belongs the set $C$, where every member of $C$ is not null, and contains every string of characters that can be permuted (numbers, letters etc.). For a secure crypto-hash function such as SHA-512, is it possible to generate an infinite amount of hash collisions given an unbounded amount of time and computation for every possible string $w$?

Yes and no.

SHA-512 is by definition limited to strings of at most $2^{128}$ bits long.  So there is only a finite set of possible inputs, not an infinite set.  But you're guaranteed to have many collisions even in that finite set, because there are only $2^{512}$ holes to put $2^{2^{128}}$ pigeons into.

SHA3-512,* in contrast, is not limited to any finite input space.  So there are collisions of infinitely many strings, in principle.

But you're not likely to find any.  Unless you know something about SHA-512 or SHA3-512 that I don't, you would have to try approximately $2^{256}$ before you would be likely to find a single collision.  I assure you most decidedly that ain't nobody got time for that.

* It's also silly to use SHA3-512 for any purpose.  Its design was selected for political, not technical, reasons after certain well-known news in 2013.  There's no substantive reason to use it instead of SHAKE256-512.


What's the difference between "HashX-512" and "HashX-1024"? I need to make a Skein hash's, specifically, Skein-1024; however, I only have access currently to Skein-512.  Is there any way to utilize a Skein-512 function to get the result of a Skein-1024 hash?

What's the difference between the two?

Internally, Skein-1024 uses the Threefish-1024 compression function and is extended to 1024 bits of internal state whereas Skein-512 uses the Threefish-512 compression function. There are a few additional changes but they are very similar (just like SHA-256 and SHA-512 are, for instance).

The tweak handling is, however, the same since all Threefish variants have the same 128-bit tweak size, so if you do have access to the Skein-512 source code, you should be able to modify it so that it calls Threefish-1024, make the necessary length adjustements, and it should work without too much pain.

Other than that, no, there is no parallel between the two functions that will let you compute a Skein-1024 hash from a Skein-512 one. The two Threefish functions have different constants & number of rounds.

Why do you need Skein-1024, by the way? Unless you really need the 1024-bit internal state, which is unlikely and overkill, you can just use the "arbitrary output length" feature of all Skein variants, which allows you to produce a digest of arbitrary length. It is described in the Skein paper and is hopefully available within your Skein implementation. If it isn't, the implementation is incomplete.


Collision in SHA-1 first 8 bytes I'm trying a Birthday Attack to randomly generated strings and its $\mathop{SHA-1}$ hashes using a Mapped table of values in order to find a collision on only the first 8 bytes. With the first 4 or 5 bytes it was easy, but the problem now with 8 bytes is I'm running out of RAM memory as I'm storing the values, and I don't think generating all the possible hashes and storing them in a file is a solution. Any ideas to make it memory-efficient/faster?

About the memory requirement

Your target is 8 bytes long i.e. $2^{64}$ possibilities.

The probability to have a collision is given by the formula:
$$P(n,N) \approx 1 - e^{-n^2/2N}$$
Where $N$ is the size of the output space and $n$ the number of values you try. By inverting the equation you get:
$$n \approx \sqrt{-2N\ln (1 - p)}$$
For $p = 0.5$, you get :
$$n \approx 1.2\sqrt{N}$$
Thus with $N = 2^{64}$, $$n = 1.2\times 2^{32}$$
Therefore you will need to generate about $5\ 000\ 000\ 000$  values of 8 bytes. The memory requirement is therefore of $40 GB$.

If you target $p = 10\%$ in order to reduce the memory requirement (you will just need to do the experiment a bunch of times), you will need $0.46\times 2^{32} \approx 2\ 000\ 000\ 000$ values and about $16 GB$ (which is a bit less constraining.

What you are doing is actually called a multi-target attack. I would also suggest you to have a look at this question : What are the memory requirements for this type of search if the hash function has an output length n bits?

Some optimisations:

You might want to avoid the random generation part. You could just take a seed $s$ and iterate from it using an array of values such that
$$\forall i, h[i] = \mathop{SHA}(s + i)$$
This will divide the memory space required by 2 (as you don't need to store the value because it is the array index of the hash).

You might also want to consider the time complexity of your search (for each value you need to check that there are no previous collision). From my point of view, this really looks like in $O(n^2)$...

Another possibility would require you to look at differential cryptanalysis of $\mathop{SHA1}$ and look for differential trails where the 8 first bytes of the last difference are being composed only of $0$.


Elliptic Curves of different forms Looking at http://safecurves.cr.yp.to/ to find a safe curve, I find that most curves described here are of a different form from that generally used.

In Bouncy Castle, for example, FpCurves take curves of the form $y^2 = x^3+ax+b$ (Weierstrass), whereas the (safe) curves found on the above linked have different forms, such as $y^2 = x^3+ax^2+x$ (Montgomery) - how do I translate between the two? How do I use the second form of curve with, for example, Bouncy Castle?

(Or do I simply have to accept that no safe curves of the Fp form exist?)

What else have I tried? Guide to Elliptic Curve Cryptography (Hankerson et.al.) covers curves of the forms $y^2 = x^3+ax+b$ for fields with characteristic > 3, and only offer alternatives (that are not interchangable with the safe curves, either) for lower characteristics, that are not very useable in my situation. Even then, some curves on the safe curves website are of forms that I cannot immediately find explained anywhere.

The idea of "safe curve" is somewhat overrated. What you really want is a safe implementation which won't leak secret information when employed in some practical context. Leakage may occur in a variety of ways; some examples include timing attacks and implementation behaviour when encountering anomalous input. This is not an exhaustive list, and, depending on the context, such leakages may or may not apply.

The so-called "safe curves" are curves with equations which, supposedly, make it easier to implement them safely. Note the operational term: easier. A "safe curve" does not automatically imply that any implementation will be sound and safe (a prime example is how OpenSSL botched at least twice their code for binary curves, while using the "safe" Montgomery ladder as adapted by López and Dahab to binary curves). Conversely, an "unsafe curve" can still be implemented safely. It would be wrong to place some anathema on "unsafe curves", as DJB's site seems to imply with its "safe/unsafe" terminology and conspicuous green and red labels (but only seems, mind you).

For an elliptic curve user, e.g. the designer of some protocol which relies on some elliptic curve cryptography implemented by a third-party library, the important matter is that the library is good, which is only loosely correlated with whether the base curve is called "safe" or "unsafe".

As for translation between curve equations, this may or may not be feasible, depending on the actual curves. For instance, proponents of "safe curves" usually mean using Montgomery curves whose equation is: $$By^2 = x^3 + Ax^2 + x$$ for two constants $A$ and $B$. A curve which follows this equation necessarily accepts the point $(0,0)$ which has order $2$ (that point, when doubled, yields the "point at infinity"). It follows that the order of a Montgomery curve must be even. Therefore, standard curves like P-256 with a prime order (thus odd) cannot be converted to a Montgomery equation. Other curves might be convertible, or not.

The Handbook of Elliptic and Hyperelliptic Curve Cryptography describes Montgomery curves in section 13.2.3. It discusses the conversions from Weierstraß to Montgomery equations and back, when that is possible at all. Notably, while Montgomery curves allow for a point multiplication algorithm which is both efficient and relatively easily amenable to "safe" implementation (the famous "ladder"), section 13.2.3.b points to an article from Brier and Joye who showed how a ladder algorithm can be applied to the generic case of the Weierstraß equation $$y^2 = x^3 + ax + b$$ albeit with a somewhat higher computational cost -- but nothing critical in most usages. This would make P-256 a "safe curve" as well, if we want to cling to that terminology (there are other criteria for a curve to be called "safe" but the main point remains: "safety" is ultimately a property of the implementation, not of the curve).

Indeed, if a basic PC or even a smartphone is implied, then the hardware can do thousands of point multiplications per second. For most if not all applications running on that kind of hardware, it makes no detectable difference whether a given ECC implementation can do 3000 or 30000 signatures or decryptions per second (if it did a difference for you, you would not even contemplate using a Java-based implementation like BouncyCastle; you would have gone straight to optimized assembly code).


Why blinding integer $r$ needs to be co-prime with $N$ in blind RSA signature According to blind RSA signature wiki the random value $r$ in $m^\prime=mr^e \bmod N$ needs to be relatively prime to $N$.

Why is this a requirement?

A follow up a related question: after $s$ (unblinded signature) and $m$ (original message) are revealed, can anyone (and not only the signing authority) check the validity of the signature by checking $s^e=m \bmod N$?

Why is this a requirement?

Well, if $r$ has (say) $p$ as a factor, then it makes the unblinding step rather difficult.
The original $m$ has $N = pq$ possible, as does $m^d$; if $r$ is a multiple of $p$, then $mr^e$ has only $q$ possible values; if we pass it to the signer, it'll come back to us with a value $m'^d$ that also has only $q$ possible values.  We cannot map $m'^d$ back to $m^d$ (as a single $m'^d$ value would map back to $p$ possible $m^d$ values, and we don't know which one it is.

A follow up a related question: after $s$ (unblinded signature) and $m$ (original message) are revealed, can anyone (and not only the signing authority) check the validity of the signature by checking $s^e=m \bmod N$?

Yes, anyone with the public key can validate it.  This is generally true for public key signature algorithms.


About random self-reducibility of DDH In Section 8 of this, Lindell presents a construction of an oblivious transfer protocol which is secure in the malicious model under the following variant of the DDH assumption (page 53):

  [F]or every probabilistic-polynomial time non-uniform distinguisher $D$ there exists a negligible function $\mu$ such that
  $$|\mathrm{Pr}[D(\mathbb{G},q,g_0,g_1,(g_0)^r,(g_1)^r) = 1] - \mathrm{Pr}[D(\mathbb{G},q,g_0,g_1,(g_0)^r,(g_1)^{r+1}) = 1]| \le \mu(n)$$
  where $\mathbb{G}$ is a group of [prime] order $q$ with generators $g_0$, $g_1$.

It is then stated that this assumption "follows easily from the standard DDH assumption" using its random self-reducibility property (as described for example by Naor and Reingold).

As I understand it, random self-reducibility means that from any fixed instance we can generate a random one, which can then be solved by an assumed algorithm solving a random instance. Thus no particular instance can be harder than the average case, and so in particular the worst case is exactly as hard as the average case.

However, this does not seem to preclude a particular case from being easier than the average case, and in particular the case $(g^a,g^b,g^{a(b+1)})$, so I fail to see how the hardness of the average case (which is the "standard DDH assumption") implies the hardness of this particular case.

You are absolutely right! The random self-reducibility goes in the other direction, and this variant of the DDH assumption does not follow from it. I have no idea what the author was thinking when he wrote it :-). In any case, the paper has now been updated in ePrint and fixed. Thank you for catching this.

I include the proof of this variant here:

Consider the following DDH variant that states that for every probabilistic-polynomial time non-uniform distinguisher $D$ there exists a negligible function $\mu$ such that
\begin{equation}
\left|\Pr[D(\mathbb{G},q,g_0,g_1,(g_0)^r,(g_1)^r)=1] - \Pr[D(\mathbb{G},q,g_0,g_1,(g_0)^r,(g_1)^{r+1})=1]\right| \leq \mu(n)
\label{eq:ddh}
\end{equation}
where $\mathbb{G}$ is a group of prime order $q$ with generator $g_0$, $g_1\in\mathbb{G}$ is a random group element, and $r\in\mathbb{Z}_q$ is randomly chosen. This assumption can be proven to be to be true if the standard DDH assumption holds. In order to see this, observe that by the standard DDH assumption
\begin{equation}
\left|\Pr[D(\mathbb{G},q,g_0,g_1,(g_0)^r,(g_1)^r)=1] - \Pr[D(\mathbb{G},q,g_0,g_1,(g_0)^r,(g_1)^s)=1]\right| \leq \mu(n)
\label{eq:ddh1}
\end{equation}
where $g_1\in\mathbb{G}$ and $r,s\in\mathbb{Z}_q$ are randomly chosen. In addition, observe that the distribution over $(g_0,g_1,(g_0)^r,(g_1)^s)$ is identical to the distribution over $(g_0,g_1,(g_0)^r,(g_1)^{s+1})$. Thus, a straightforward reduction to the standard DDH assumption gives that
\begin{equation}
\left|\Pr[D(\mathbb{G},q,g_0,g_1,(g_0)^r,(g_1)^s)=1] - \Pr[D(\mathbb{G},q,g_0,g_1,(g_0)^r,(g_1)^{r+1})=1]\right| \leq \mu(n).
\label{eq:ddh2}
\end{equation}
In order to see this, a distinguisher $D'$ receiving $(g_0,g_1,h_0,h_1)$ can run $D$ on $(g_0,g_1,h_0,h_1\cdot g_1)$. If $D'$ received $(g_0,g_1,(g_0)^r,(g_1)^r)$ then it generates a tuple of the form $(g_0,g_1,(g_0)^r,(g_1)^{r+1})$, and if $D'$ received $(g_0,g_1,(g_0)^r,(g_1)^s)$ then it generates a tuple of the form $(g_0,g_1,(g_0)^r,(g_1)^{s+1})$, which as we have mentioned is identical to $(g_0,g_1,(g_0)^r,(g_1)^s)$. Thus, if $D$ can distinguish with non-negligible probability in this last equation, then $D'$ can use $D$ to solve the standard DDH problem. Combining these last two equations, we obtain that the first equation (which is the DDH variant assumption) holds.


How to encrypt files using AES256-GCM cipher under Linux? I'm struggling to implement AES256-GCM on a Linux machine to encrypt files outgoing to another party.

We're usually exchanging files using PKI, but this particular party insists on AES256-GCM and will not allow PKI.

However, I've been struggling to make it work. We'd like to implement it on a Linux machine and to be able to automate encryption. It seems like the other party is okay with doing this manually on a Windows desktop, but we'd like to avoid that possibility.

I tried to do it using openssl, but I get this:

$ openssl aes-256-gcm
AEAD ciphers not supported by the enc utility

When I tried GPG, I get:

$ gpg --version
...
Cipher: IDEA, 3DES, CAST5, BLOWFISH, AES, AES192, AES256, TWOFISH,
        CAMELLIA128, CAMELLIA192, CAMELLIA256
...

The other party just suggested using what they have, which is some Windows EXE with BouncyCastle libraries, so I started investigating using BouncyCastle for this, but it's in Java, and I'd like to avoid using Java if possible.

I'd have to add a JDK to that particular server or set up another virtual machine just for the purpose of encrypting these files, which is completely non-optimal. Browsing BouncyCastle's documentation, it's not very helpful, at least I haven't found any real examples, and I must be doing something wrong, because even when I did a full text search looking for a reference to GCM, Galois Counter, or anything similar, I found nothing (do I have the wrong files?).

I figure I might work it out, but we've been given a tight deadline and we can't force them to use PKI. I hate to waste time looking in the wrong places, but I would really want to avoid using the simplistic manual process in Windows if it's at all possible.

Edit:
The expected format is IV+ciphertext(plus, I presume, tag). I received a copy of their Java source code for a simple encrypt/decrypt utility and it's very simplistic with no allowances for complex encoding routines or anything, it's just meant to encrypt (or decrypt) a single file or a single zip package of multiple files. That's all.

The worst thing is that I saw references to being able to encrypt using OpenSSL (which is just an interface for enc, after all, so it should also work with gpg, for instance), and the best one I found was this:
https://security.stackexchange.com/questions/128883/basic-question-regarding-openssl-and-aes-gcm

I guess I'll try that tomorrow and see if I can get it to work.

LibreSSL supports AEAD ciphers, including aes-256-gcm:

$ openssl enc -aes-256-gcm -nosalt -p -in file.in -out file.out
enter aes-256-gcm encryption password:
Verifying - enter aes-256-gcm encryption password:
key=A744E1091C25BABD36B50E40FB8D311A672722729CEA6E217AD9FA8AF23CAF57
iv =BDEEA37B93BB989C6C40665B

If you don't mind writing your own software, there are plenty of crypto libraries supporting AES-GCM, such as OpenSSL itself (even if not available from the command line tool). Libsodium also provides AES256-GCM and may be easier to use.

That being said, using a common and trusted tool such as GPG would be way safer than implementing your own software, even if the resulting files are not encrypted using AES-GCM.


OpenSSL not producing messages of expected size I have a 16 byte file, and after encrypting it, its size weirdly changes.

> hexdump -C 1.txt
00000000  61 61 61 61 61 61 61 61  61 61 61 61 61 61 61     |aaaaaaaaaaaaaaa|
0000000f

> openssl enc -v -aes-128-ecb -nosalt -base64 -in 1.txt -out 2.txt

...

bytes read:    16
bytes written: 45

It becomes 45 bytes.

Why is it not a multiple of 16, since AES has 16-byte blocks?
If OpenSSL adds a header of some sort, how large is it, and is it fixed size? I can't find anything in the documentation that mentions this.

You have 16 bytes to encrypt in your file. You did not set -nopad option, therefore, the OpenSSL will use the default padding, PKCS#7. This padding adds characters so that the input is multiple of the block size. If the input is already multiple of the block size then an additional block is added that contains byte 10 16 times. The rule can be simplified as

$$paddingSize=b−(messageLength \bmod b)$$ where $b$ is the block length and padding char is char(paddingSize). This will make the input 32 bytes and with the ECB mode, the output (ciphertext) will be 32 bytes, too.

Next, you set the option -base64 this will convert the output to base64. The base64 converted output length can be calculated by formulas. The unpadded base64 output size is $\lceil 4 \cdot n / 3 \rceil$ where $n$ is the number of characters. $\lceil 32*4/3 \rceil =  42$ and this will round up to the multiple of 4 that makes 44 bytes. The below is the hex dump of the output file;

$hexdump -C 2.txt
00000000  33 53 37 53 43 56 33 4b  69 63 2b 38 65 69 4a 39  |3S7SCV3Kic+8eiJ9|
00000010  34 6a 69 77 76 76 58 2f  67 48 45 6d 62 54 38 57  |4jiwvvX/gHEmbT8W|
00000020  6a 4b 55 6c 64 57 51 43  5a 39 51 3d 0a           |jKUldWQCZ9Q=.|
0000002d

The missing $45-44=1$ byte is the 0a character at the end of the ciphertext, it is the line feed character.

Note: Since this is Cryptography, we must say something about the ECB. If there isn't a really special issue to use the ECB, don't use the ECB mode, this is insecure leaks patterns and enables frequency attack. In modern Cryptography we prefer Authenticated Encryption (AE) modes like AES-GCM. To use it with OpenSSL, use -aes-256-gcm option instead of -aes-128-ecb. AE modes provide Confidentiality, Integrity, and Authentication. And, your obligation for the AES-GCM, is never using an IV again. Even a single AES-GCM nonce reuse can be catastrophic.


Reordering non-block-aligned parts with DES in ECB mode I was given a ciphertext file which was encrypted using DES in ECB mode. It is known that the plainttext that was encrypted has the following form:

Each line of text consists of a payroll followed by a name (no spaces):

32 characters for the name;
8 characters for the pay amount;
1 newline.

An example plaintext file would be:

abcdefghikabcdefghikabcdefghikab00000000
abcdefghikabcdefghikabcdefghikab10010010
abcdefghikabcdefghikabcdefghikab10010010
abcdefghikabcdefghikabcdefghikab10010010
abcdefghikabcdefghikabcdefghikab10010010
abcdefghikabcdefghikabcdefghikab10010010
abcdefghikabcdefghikabcdefghikab11111111

and it was encrypted using this command (of course the key was not given, for obvious reasons):

openssl enc -e -des-ecb -nosalt -in plaintext.txt -out ciphertext.enc

The ciphertext file is of size 288 bytes since there are 6 newline ('\n') characters and DES encrypts in 64 bit blocks it's easy to tell that there are 7 entries in this payroll list.

The Objective: exchange the first line with the last.

If all the entries were on one line with no spaces this would be an easy task as DES in ECB mode you can move around the 64 bit blocks without being detected. All I would do is take the first 40 bytes and exchange them with the last 40 bytes. However since there is a '\n' character at the end of every line this approach does not work. I feel a bit stuck. All I'm looking for is a point in the right direction.

If the plaintext format is indeed as you describe, then you're out of luck: the insertion of the newlines and the consequent shifting of the plaintext records is enough to disrupt any structure in the ciphertext.  If the plaintext were longer, say, 8 records, then it could work, but with just 7 records there's no way to switch the first and last record simply by shuffling ciphertext blocks.

However, I suspect you're mistaken about the presence of newlines in the plaintext.  Specifically, since the encryption command you were given does not include the -nopad option, the openssl enc command applies PKCS #5/7 padding to the plaintext before encrypting it.  In order to be unambiguously reversible, this padding scheme always increases the length of the plaintext by at least one byte — in particular, it causes any plaintext length between 280 and 287 bytes inclusive to produce a ciphertext of 288 bytes.

Thus, I suspect that your data actually has no newlines, and simply consists of seven 40-byte fixed length records, plus 8 bytes of padding.  Keeping the last 8 bytes of the ciphertext in place, and switching the first and last 40-byte chunk of the ciphertext preceding it, should do the trick.


Differences between NewHope-CPA-KEM and NewHope-CCA-KEM According to the web page for NewHope, an R-LWE post-quantum key encapsulation mechanism (KEM) candidate for standardization, it comes in types that are IND-CPA or IND-CCA secure. I know what CPA and CCA security are, but I don't understand the difference between the two types of NewHope and why there needs to be a choice between one or the other (unlike, say, RSA-OAEP which provides both).

Well, it turns out that a straight-forward implementation of LWE key exchanges is vulnerable to chosen ciphertext attacks, in the case that one side reuses the same private value $a$ multiple times.

In this straight-forward implementation, Alice generates a private vector $a$, and sends his key share $a M + \epsilon$.  Then, when Bob receives this key share, he generates a private vector $b$ and sends his key share $b M + \epsilon'$ and a reconciliation vector.  This reconciliation vector is needed because the vectors that both sides compute won't be precisely the same (because of the error vectors $\epsilon, \epsilon'$), and advise Alice how to do the rounding.

The best known attack involves the attacker sending incorrect bits in the reconciliation vector, which (over a number of exchanges) can yield individual values from the $a$ vector.

In the CPA version, they assume that you'll never reuse the same public value over multiple exchanges, and so this attack is irrelevant.

In the CCA version, they can't make this assumption.  What NewHope team has decided to do is to use to have Bob generate his key share from a seed in a deterministic way and encrypt that seed as a part of the ciphertext, and so when Alice gets it, she can decrypt the seed and then regenerate what Bob's key share should be (based on the seed), and see if that's the value she got; this prevents attacks (like the above) which are based on sending illegitimate keyshares.

Of course, all this extra checking slows things down; that's why the CCA version is slower.


Pseudo-random generators and pitfalls I've read the Chapter "Randomness" from the Serious Cryptography book and it raised some questions. Namely:

It is written that Mersenne Twister is proved to be cryptographically irreliable. And that is it used by some languages, especially by Python. I have seen a lot of project with different languages when secure random stuff (like keys, token, sessions and so on) were generated just by taking random bits from a standard library.

I have not seen a situation when someone takes care of entropy level.

How to know that generating (pseudo) random keys is secure? Especially, I don't see implementation of pseudorandom generator that return error (for example when entropy is not sufficient). Could tell me something about my doubts and recommend me any book/article that covers that subject more specifically.

First, If the source isn’t explicitly labeled as “secure” or “crypto” in its name, you must assume it is insecure.

For example, in C#, the System.Random is insecure while System.Security.Cryptography.RandomNumberGenerator is obviously intended to be a secure RNG.

Second, you’ll need to actually do some research to ensure that it is, in fact, going to be a secure RNG in the version you are using, and in the target deployment environment. Will you have an entropy source when it is deployed?

Most languages let you access the operating system’s secure RNG in some way; these should be preferred over any user-space generators to ensure fork()-safety. User-space RNGs are also far more likely to have bugs or their state compromised by bugs in user-space applications, which history shows are innumerable.

For example, Pythons os.urandom() doesn’t mention security in its name, but it does call the operating systems secure RNG directly (/dev/urandom on Linux and CryptGenRandom on Windows). When you use the OS generator you also don’t need to evaluate the security of a particular language’s generator user-space algorithm choices or implementation quality.

The OS generator on any recent mainstream OS can be trusted, unless you’re deploying into an environment with no entropy source (such as an embedded Linux device with no user inputs and no hardware RNG).


Is there a way to prove knowledge of a limited resource like a phone number just to the people who already know about it? For instance, let's say Bob's phone number is X and Alice has somehow identified that Bob's phone number is X.
Now she doesn't have a direct way to contact Bob, so she wants to post in a public forum with proof that she knows Bob's phone number.
This almost seems impossible since phone numbers are a very limited space and solutions like hashing would not be effective. One possible solution is to have an extremely slow hash (let's say one that takes hour(s) to compute), but this has issues both practically (Bob likely won't bother checking) and theoretically (It's still not difficult for a determined person to find out).
Are there any cryptographic solutions to this, even if they are imperfect? We can assume that there is a period of time after which this information can be made public.
Note: This sounds like something like "proof of knowledge" to me, but since that's not a tag, I'm tagging it as zero-knowledge-proof. Please let me know if this is incorrect.
This was inspired by this but I'm hoping we can get more theoretical answers that answer this specific question.

As you mention, phone numbers have low entropy. Someone who "doesn't know" a phone number at the time of the proof can easily obtain the phone number later. You won't be able to find a non-interactive solution to this problem -- an attacker can always run a dictionary attack and use your "proof" as a test for whether they've found the right number.
For an interactive solution, this problem is often known as the socialist millionaire's problem. Two parties each have a private string, and they want to simply test whether their strings are equal while revealing nothing in the case that the strings are different. The secret strings do not have to have high entropy. You can also achieve this functionality by a symmetric password-authenticated key agreement (PAKE) with explicit mutual authentication / key confirmation. With PAKE, the two participants agree on a random key only if they hold the same secret (low-entropy) "password". Mutual authentication means that the parties are notified if their passwords don't match (instead of simply walking away from the conversation with unrelated keys).
Since these protocols are interactive, it only matters what password (phone number in your case) they use during the interaction. Someone who doesn't know the password only gets one shot to guess it. Using some password $pw$ in the protocol does not leave a way to later test whether a different password $pw'$ was the correct one.


Lattice Crypto worst case to average case I am currently reading the ETSI white paper Quantum Safe Cryptography and Security

On page 24 one finds the following statement:

  Lattice problems also benefit from something called worst-case to average-case reduction, which means that all keys are as hard to break in the easiest case as in the worst case when setting up any of the parameters of a lattice based cryptosystem. In a crypto system like RSA, generating keys involves picking two very large random numbers, that should be prime and should yield a hard instance of the factorization problem, but there is a certain degree of probability of choosing wrong and resulting in a weak security level. In lattice-based cryptography, all possible key selections are strong and hard to solve.

This puzzled me, because I had a different understanding of worst-case to average case reduction in lattices.
According to my understanding it means the following:

  A lattice cryptosystem on the average (i.e. with randomly chosen keys) is as hard as the hardest problem of the underlying lattice problem. This does not imply that all possible key selections are strong and hard to solve.

Now, who is wrong? Me or ETSI ?

You are right.  A worst-case to average-case reduction from problem P to a distribution D over instances of problem Q would mean roughly that $$\Pr_{q\leftarrow D(Q)}[q\text{ is hard} ~|~ \exists~\text{any instance of P that is hard}]>1-\text{negligible}.$$ So even if the support of distribution D is the entire set of instances of problem Q, this does not of course imply that every instance of problem Q is hard.

As an aside, it should be pointed out that the way in which parameters are set for lattice problems does not result in a particularly meaningful worst-case to average-case reduction because the reduction is not tight -- the dimension of the lattices in problem P is smaller than in problem Q.

Still, the big utility of having had such a reduction was that it was this reduction that led people to the problems of (Ring/Module)-SIS and (Ring/Module)-LWE and distributions over these problem instances (uniform) that are currently used in practical lattice cryptography.  Analyzing the hardness of random instances of these problems became an independent matter.


Blowfish, Sboxes and the digits of PI, and the P_Array I am trying to use the Blowfish algorithm, however, I am trying to understand SBoxes that were used in the algorithm. I saw that it uses the hex digits of PI. I looked around in the web and found some codes that implements Blowfish and saw that they're using hardcoded SBox int arrays.

For example, in here:
https://www.schneier.com/code/constants.txt

Since it was stated that sboxes contain the digits of PI, so I am guessing that the first five entries of sbox0 correspond to 31416.

If so, how did 0xd1310ba6L came from 3?

I am asking this because I am experimenting if I can use a random set of integers for the sboxes. After all, I saw that sbox values were supposed to be random.

Also, if I did change the values of the sboxes, can I still use the same set for the P_Array?

Another unbreakable encryption from Bruce!  His words.

Yes the boxes come from π.  However, it's not the way you think.  It's not a literal base change of the decimal expansion.  You have to calculate π from scratch in hexadecimal.  If you were to use your approach and simply change the base of the decimal expansion, you'd be putting 10 values into 16 bins for each digit. In hex, π is just:-

3.243F6 A8885 A308D 31319 8A2E0 37073 44A40 93822 299F3 1D008 2EFA9 8EC4E 6C894 52821 E638D 01377 BE546 6CF34 E90C6 CC0AC

which are your digits.

You do understand that the P and S boxes don't contain π?  They are initialised with π digits, but then amended in a key related fashion.  The π bit is what's know as nothing up your sleeve numbers (NUMSN), and there are many answers here relating to such initialisation.  In summary, you have to initialise a variable with something or zero. The purpose of NUMSN is to create a dissociation between the numbers you start with and the way the algorithm works so that there cannot be any possible adverse relationship.  There is some expansion here.

On that basis, yes you could initialise with anything.  Even just  zeros.  Although, I've never seen security analysis of an algorithm with and without the NUMSN.

  After all, I saw that sbox values were supposed to be random.

This is a contentious issue.  For a super dooper efficient algorithm, s boxes are very cleverly designed with several security parameters in mind.  There is an s-box tag that will highlight a pile of appropriate questions.  Uber efficiency isn't always necessary.  Brute force can be used instead by increasing the number of rounds.  As Blowfish recalculates it's S and P boxes dynamically, such security pre design clearly isn't used in that case.  I believe that this technique works for both the S and P boxes.


Encrypt a file for multiple persons with different keys? I thought a problem and want to ask if there's a more elegant solution.

The scenario:
A company with a fileserver, which hosts encrypted documents.
The files need to be accessible by about a dozen employees.
Now the condition is, that each employee has different key material but all the employees can still access the file (even though they have different materials).

The most naive approach would be to give everyone the symmetric key that's it. This violates the condition.
The next way would be to store the file's key in a header, which is encrypted with each employee's symmetric key. The problem with this is, that everyone none can create new files without knowing the keys of the others.

The most optimal solution I'm aware of is to use asymmetric encryption to encrypt the file's key in a header for each employee using his corresponding key. This would enable everyone to create new files for the group and it would let everyone have different keying material (which can even be stored on a smartcard).

Now my question:
Is there a way to solve the above problem, without the overhead for the additional headers (maybe using some more esoteric protocol or algorithm)?

I'd prefer an answer which doesn't only give a name for the class of algorithms, but also instantiations, which are considered secure (based on blockciphers, asymmetric encryption schemes, ...)

Now the condition is, that each employee has different key material
solve the above problem, without the overhead for the additional headers

Based on your requirements - you must have the different key material for each user... which obviously has to be stored somewhere.  You don't want it in headers ... so it either needs to be in a different file / database, or in the meta-data.
We had a similar problem which we solved using Extended File Attributes instead of additional headers.  The symmetric file key was encrypted for each authorized recipient using the recipients RSA Public Key and the result was stored in the file meta-data.
https://en.wikipedia.org/wiki/Extended_file_attributes
Some filesystems have default limits on the amount of meta-data you can store. You may need to configure those.


Math to replace s-boxes - Good or bad idea? The following was going through my brain for the past week. If my thoughts are generally known to the cryptographic community would someone provide a link or two. Even if I’m making a classic newbie mistake.

Cryptographic internal functions operating like $x=f(x)$ can be table lookup s boxes with the inverse s box as a separate table.  A 16-bit sbox and its inverse can be implemented with a little math and no tables. Use the prime $m = (2^{16})+1$. Then pick constants $p$ and $q$ such that the recursion

Seed = Seed * p % m;

touches all values, 1..$2^{16}$.  Then select $q$ such that $p * q ~~mod~~ m = 1$.

p = 49374; // example values
q = 32065;
y = ((x+1) * p % m)-1; // forward
x = ((y+1) * q % m)-1; // reverse
// x+1 puts the 16-bit x into the range (1..2^16) where the recursion works.
// the -1 at the end makes the result fit in 16 bits.

There are over 32000 values of $p$ for which the recursion touches all $2^{16}$ values.

“Mod 0x10001” can be implemented with little more than a subtract. No actual division is required. Is this a reasonable part of a good encryption algorithm? Perhaps to replace 2 8-bit s box tables?

Getting carried away - - 32-bit (non invertible) sbox

Because $m=2^{32}+1$ is not a prime there is no full ($2^{32}$ term) sequence recursion of the form

Seed = Seed * const % m

This % m operation can also be formed with only a subtract if we don’t care to be super accurate. Or a test and subtract 1 it we want to be accurate.  Thus encryption code performing

z ^= ((x+1) * const % m)-1

can be performed in decryption to recover the prior value of $z$.

Is this “32-bit sbox” a useful concept?

The S-boxes in quite many encryption algorithms (for example, in AES) have been already built with math (the AES S-box is an inversion function in $GF(256)$ plus an affine transformation). The lookup tables exist solely to ease the implementation. In fact, modern Intel/AMD CPU are already equipped with AES round function instructions, so the tables are not needed at all.

When people design new S-boxes, the first question to answer is Why? and the next one is What properties do they have compared to the existing ones?. Until there are reasonable answers, the proposals are not used and even not being analyzed.


Why is calculating the discrete logarithm harder than calculating the public key? A noob question, I know, but given n in range [0,q-1], and given an elliptic curve point P, we calculate the public key Q=nP. By doing so, we calculate P+P=2P, 2P+P = 3P, and so we get the values P,2P,3P,...,nP. For the person trying to solve the discrete logarithm, P and Q is known. The brute force way would be to calculate P,2P,... until the result equals Q. Why is this harder than generating the public key? Where is the error here in how I think?

There are actually much more efficient algorithms to calculate the public key, such as the double-and-add method which calculates the public key in at most $2 \times \log_2(n)$ steps. For example, if $n = 11$, instead of calculating $P, 2P, 3P, ...$ up to $11P$, we can repeatedly double the current point or add $P$ to get to $11P$:

$$2P = P + P$$
$$4P = 2P + 2P$$
$$5P = 4P + P$$
$$10P = 5P + 5P$$
$$11P = 10P + P$$

This method has a running time of $O(\log(n))$, while a brute force attack has a running time of $O(n)$. For a $256$ bit key, the double-and-add method takes at most $512$ point additions, while a brute force search would take up to $2^{256}$ point additions.


How can I break a Vigenère cipher with partial plain text? I have an exercise to do regarding Vigenère encryption.

I've got the cipher text: WNZTNVIEEGTJYKRRWYUELWNZTNV
and a partial plain text: S''''R''R''''R''''PASS'''''

The key length is unknown.

The question is: is it possible to find the key and the plain text?
Regarding what I've seen in class, I don't think it's possible.

But I was wondering if it was possible in some way with a computer to find the rest of the plain text and the key?

PS: neither the plain text or the key are in English.

First guess the key length(Just try every plausible length, there aren't many).

Then for each position where you know both plain- and ciphertext, calculate the key char. If you get a contradiction, the guessed key length was wrong.
If the key length is short enough compared to the number of known pairs this will probably give you a large part of the key.


does TLS 1.3 use ECDSA-Sig-Value encoded signatures for Ed25519 / Ed448? Quoting The Transport Layer Security (TLS) Protocol Version 1.3:

  ECDSA algorithms  Indicates a signature algorithm using ECDSA
        [ECDSA], the corresponding curve as defined in ANSI X9.62 [X962]
        and FIPS 186-4 [DSS], and the corresponding hash algorithm as
        defined in [SHS].  The signature is represented as a DER-encoded
        [X690] ECDSA-Sig-Value structure.

  ...

  EdDSA algorithms  Indicates a signature algorithm using EdDSA as
        defined in [RFC8032] or its successors.  Note that these
        correspond to the "PureEdDSA" algorithms and not the "prehash"
        variants.

ECDSA-Sig-Value is defined thusly:

ECDSA-Sig-Value ::= SEQUENCE {
  r  INTEGER,
  s  INTEGER
}

RFC8032: Edwards-Curve Digital Signature Algorithm (EdDSA) says the following about the signature format:

  Form the signature of the concatenation of R (32 octets) and the
     little-endian encoding of S (32 octets; the three most
     significant bits of the final octet are always zero).

I don't see why ECDSA-Sig-Value couldn't be used with EdDSA in TLS 1.3 but that doesn't mean that it is. Indeed, I'm guessing that it isn't and that you're supposed to use the RFC8032 construction?

EdDSA is a family of signature schemes defined precisely on strings of bytes, including its extension to more curves like edwards448.  This generally avoids failures of security theorems in the real world arising from a mismatch between powers of an adversary on a system of strings of bytes and powers of an adversary on a system of idealized mathematical objects.  The choice was motivated by failures of exactly that type in HMQV observed by Menezes.

Any software implementing Ed25519 will generally be byte-for-byte compatible.  The TLS stack need not know anything about its mathematical structure.  It is enough to know that a secret signing key has a standard 32-byte representation, that a public verification key has a standard 32-byte representation, that a signature has a standard 64-byte representation, and that the definition of Ed25519 entails the precise relations between these byte strings.  In contrast, ECDSA leaves needlessly complicated details to the caller to sort out—or to botch with additional ASN.1 attack surface and logic to interpret the mathematical structure in ECDSA.

In this specific case, although the parts of a signature may be named by the letters ‘r’ and ‘s’ in both ECDSA and EdDSA, and although they may be represented by integers, they actually represent different types of object with different rôles in the signature verification equation.  For an elliptic curve $E/k$ over the field $k = \mathbb Z/q\mathbb Z$ for some prime power $q$, with $k$-rational group $E(k)$ of order $h\ell$:

An ECDSA signature is some representation, with whose details the caller must be concerned, a field element $r \in \mathbb Z/q\mathbb Z$ and a scalar $s \in \mathbb Z/\ell\mathbb Z$.  It is valid on a message $m$ under a public key that is a curve point $A \in E(k)$ if and only if $$r \equiv x([H(m)\cdot s^{-1}]B + [r s^{-1}]A) \pmod p,$$ where $B$ is the standard base point.
An EdDSA signature is a standard byte string representing of a curve point $R \in E(k)$ and a scalar $s \in \mathbb Z/hl\mathbb Z$.  It is valid on a message $m$ under a public key that is the standard encoding of a curve point $A \in E(k)$ if $$[8 s]B = [8]R + [8 H(R\mathbin\|A\mathbin\|m)] A,$$ where $B$ is the standard base point.


Estimate Security level of the Rabin Signature I'm trying to figure out how long the modulus $n$ has to be in the Rabin Signature scheme, to provide 128 bit security.

We assume that the used hash function is "secure enough". Then the naive approach would be the following:

Since forging a signature is prooven to be as hard as factorization of $n$, the security level of the signature scheme is approx. equal to the bit length of $n$. Therefore for 128 bit security, $n$ should be at least a number,such that the fastest factoring algorithms take 2^180 tries. But how long is such a number?

Of course I know, that its said that RSA keys should  be around 3072bit to achieve 128bit sec. On the other hand RSA has no tight reduction to number factorization in contrast to Rabin.

Can someone therefore explain how to estimate Rabin modulus size?

With proper choice of key and padding, the most efficient purely cryptographic known attack on Rabin signature and RSA (encryption and signature) is the same: factoring the public modulus. Therefore, size recommendations for the public modulus are the same. If 3072-bit RSA achieves 128-bit security by some criteria, Rabin does.

Beware that there can be implementation attacks specific to Rabin and its Jacobi computation, that do not apply to RSA. Also, Rabin signature is unforgiving to some poor padding (especially deterministic): it can degenerate into a total break (factorization of the public modulus), when it remains an existential forgery in RSA signature.


Sensitivity of probability measure in differential privacy I know that we need some sort of sensitivity(global, local) to calculate noise that needs to be added for differential privacy. The noise is the maximum difference between two neighboring datasets. However, if I am working in probability spaces, i.e. my values are bounded by 0,1. My sensitivity would be 1, which seems too large for adding noise to the probabilities.

I tried looking up any relevant literature that provides any tighter upper bounds, but no success. I am only interested in adding noise to the probabilities, not to the mechanism that they are generated from.

Do you need local differential privacy (i.e. no central server knows the real data of individuals) or global differential privacy (where you have all the real data, and want to generate differentially private statistics out of it)?

In the former case, you need to add a significant amount of noise (typically Laplace noise) to each probability, and there's basically no better way of doing it. This will mean that every data point will be very noisy, but if you have enough of them, you might be able to retrieve some information. The "amount of noise" will be similar to the randomized response mechanism described here or here.

In the latter case, it depends on what you're computing. If you're computing the average probability, the noise you add can be scaled by $1/n$, where $n$ is the total number of users. See for example the methods presented here, in the "summing or averaging numbers" section.


How can Cleve's 1/r lower bound on the bias of coin-flipping protocols hold if parties can output random bits? I was reading Richard Cleve's 1984 paper on coin flipping protocols, and he says that in the case where parties may abort prematurely and the honest party is forced to output a bit, then the honest party can be forced to be biased by at least 1/r where r is the number of rounds.

Recently Moran, Naor, Segev showed that this bound is asympotically tight.

Although I roughly understand Cleve's proof, I don't understand the premise that the chosen bit that a party outputs when the other party aborts is deterministic. Since they are PPTs, and they are notified when the other party abort, can't the honest party just flip a random coin and output that?

In a multi-party protocol, if every honest party just outputs a random bit, it's likely they won't all output the same bit and the protocol would be incorrect.

With two parties, the corrupt party can still bias the output. Suppose the corrupt party aborts in the last round whenever the actual protocol output would be 1. If an abort occurs, the honest party outputs a random bit. Then we have two cases, which each occur with $1/2$ probability:

Abort, output random $b \leftarrow \{0,1\}$
No abort, output $b=0$

Clearly the probability of outputting 0 is $3/4$, so there is still bias.


How do you prove that if f(x) and g(x) are negligible, then f(x)/g(x) is not? I can use an example: the case where we have $x$ such that $f(x)=g(x)$. The quotient is $1$, a non-negligible function. However, we can't conclude that all functions $f(x)/g(x)$ are also negligible.

How can I formally prove this?

This is false, take $f(x) = 2^{-2x}$ and $g(x) = 2^{-x}$.


How can I validate a given Server-Certificate behind a HTTPS-connection? I know more or less about how TLS works in principle.

But how can I be sure, that the certificate behind a server's web site (e.g. tele-banking from my bank) has been issued to my bank and not to someone else.

Let's say there is a faked tele-banking portal, to which I get connected accidentally. If they got a certificate issued by a CA, everything works and my data are transmitted to the fake site.

So I would have to check the certificate every time I use the portal.
But how? My bank says:

  The Bank XXX login pages are encrypted and therefore begin with
  "https://". Always check the owner of the security certificate, which
  must be "XXX Bank XXX" with the Internet address is
  highlighted in green color prior logon to your OnlineBanking.

Now, virtually everybody can get a signed certificate with owner="UniCredit Bank Austria" from a CA. Does CA-1 know about other certificates issued by any other CA-2? I cannot imagine that this is the case. But how can I be sure, that the certificate I want to rely on is not a fake?

OK, so let's step through this, but first:
CAs have exactly one raison d'être and that is to attest the link between a domain, a public key and optionally an entity.

As an overview, a CA validation of this set of information can go as follows:

You register with the CA, so they can attribute actions made from a specific account to you.
You request validation that your account represents a given entity (this can be a natural person or a legal person like a bank). Note that only validated information will be placed in the certificate.

This may include copies of official documents (passport, driver's license, governmental ID) if you want to validate as a person.
This may include an attestion letter of the CEO of the company.
If you are really interested, read the CA-Baseline Requirements (section 3.2) and the EV-Guidelines (section 11).

You request validation that you control a certain asset (usually a domain).

This means that you have to prove control over the asset, which can be proven by placing a file on a webserver or by clicking on a link sent to an email strongly associated with the domain owner (like the hostmaster entry in the WHOIS database)

You send the CA your public key and they give you a certificate.

This usually uses a PKCS#10 certificate signing request (CSR). Note that CAs keep track of whom they issued which certificate for which domain(s).

So what if a CA doesn't do its job properly? Well if it violates the CA-Baseline requirements or the EV guidelines for an EV certificate, it will be untrusted by the browsers and operating systems and thus can no longer issue default-trusted certificates, ie it is out of business. Historically, this did happen, for example with Diginotar but also with StartSSL and WoSign. They all failed to adhere to the baseline requirements and thus got marked "untrusted" to varying degrees.

Also note that the browser will validate the domain name, the public key and the signature chain of the certificate automatically and will display you an error message if any step of this process fails. So you can trust the fact that the certificate the browser presents you is the right one for the domain you're on.


Can a zero nonce be safely used with AES-GCM if the key is random and never used again? I could generate a random nonce and prepend it to the ciphertext, but storage space is at a premium and the only constraint AES-GCM has on the nonce (if I'm reading correctly) is that the same nonce must never be paired with the same key for a second encryption.

The encryption key is randomly generated, used for a single encryption, split using Shamir's Secret Sharing Scheme, and discarded. When the key is reconstructed for decryption, there is no chance that it can be fed back through to encrypt again; a new random key is always generated for each encryption.

If that's the only constraint, then twelve zero bytes are as safe as twelve random bytes prepended to the ciphertext. I'm reading that the AES-GCM nonce is used as the IV for AES in CTR mode. It's okay to use a zero IV for AES-CTR as long as the key is never reused, but I don't want to assume without confirmation that AES-GCM does nothing relevant with the nonce besides passing it to AES CTR. Am I missing anything?

Usually. However, if you are using 128-bit AES in CTR mode (remember that GCM is essentially just CTR with authentication), then a kind of attack called a multi-target attack can become possible. This attack is realistic when an attacker has a huge amount of stored ciphertext, each with a random key. While breaking a specific key requires performing up to 2128 operations, breaking any key is significantly easier. This attack can be mitigated either by using a larger key size, or by using a random nonce.

From the above-linked blog post by DJB:

  What the attacker hopes to find inside the AES attack is a key collision. This means that a key guessed by the attack matches a key chosen by a user. Any particular guessed key has chance only 1/2128 of matching any particular user key, but the attack ends up merging costs across a batch of 240 user keys, amplifying the effectiveness of each guess by a factor 240.


Reasons for components of AES I started reading "Cryptography: theory and practice" by Stinson, and I am trying to understand the reason behind the choices for the different components of AES since they seem quite arbitrary.

In the beginning ADDROUNDKEY is performed, why does this not allow for perfect secrecy: the key and plaintext are same key length and xor'd one at time in a stream cipher manner, why is the condition $P[c|p]=P [p]$ not met?
Why does finding the Galois field inverse of an element in the field provide non-linearity, is there a reason behind this type of design?
I read that the reason for block ciphers having rounds is due to the theory behind product ciphers, by why is this secure and how does it counteract the issue with question 1.

Thank you

I can make a few comments regarding points 1 and 3:

If you are going to encrypt only one block, your first assumption is not that misled. However, you will almost always need to encrypt a file longer (maybe way longer) than the key length (let's say 128 bits). Without considering encryption modes, that means that for every block of 128 bits, you will encrypt with the same key. There are $2^{128}$ ways to encrypt the first block, but once you choose one, you have no freedom to choose the second.

(As a note, if you were to use different keys for each block, you would face the similar practical difficulties that make One Time Pad unpractical).

About rounds, the shortest answer is that the higher the amount of rounds, the "more scrambled" the text can get, but after a certain point, the improvement obtained by an additional round is not worth the overhead in performance.

There are two basic "operations" in cryptography. I have seen them by different names, but I first saw them as substitution and transposition. Substitution is like Caesar's cipher: you assign a different value for a character, but the value of every position is not affected by the others ( $E(M_1M_2M_3)=E(M_1)||E(M_2)||E(M_3)$). Transposition is like an anagram, or a Spartan scytale: the positions of the characters change, but the characters are untouched.

The aim is to mix this two techniques in such a way that the outcome yields no information about the original message. As you will see, each Feistel round will only have a small effect: a given bit will only affect a few bits on the ciphertext. Your target is that all bits of the plaintext affect all parts of the ciphertext.

Up to a certain amount (I believe 9), rounds are insufficient and they leak information. In cryptography, you do not want to live with the bare minimum, so several additional rounds were added.


Is AES-256 a post-quantum secure cipher or not? We know Grover's algorithm speedup brute-force attacks two times faster in block ciphers (e.g brute-forcing 128-bit keys take $2^{64}$ operations, not $2^{128}$).
That explains why we are using 256-bit keys to encrypt top secrets. But latest practical attack on AES shows brute-forcing AES-256 take $2^{100}$ operations.
Does this attack work with Grover's search to make AES cipher quantum unresistant?

Biclique cryptanalysis is the current best-known attack on AES. It reduces the security of AES-256 from $2^{256}$ to $2^{254.4}$. Related key attacks are not practical attacks, as they should never occur in the wild. They are symptomatic of poor implementation and contrary to the recommended use of AES.

The best known theoretical attack is Grover's quantum search algorithm. As you pointed out, this allows us to search an unsorted database of $n$ entries in $\sqrt{n}$ operations. As such, AES-256 is secure for a medium-term against a quantum attack, however, AES-128 can be broken, and AES-192 isn't looking that good.

With the advances in computational power (doubling every 18 months), and the development of quantum computers, no set keysize is safe indefinitely. The use of Grover is just one of the gigantic leaps.

I would still class AES as quantum resistant, so long as the best-known attack is still some form of an exhaustive search of the keyspace.

As for your question about using different attacks: Combining attacks rarely works as you need all of your attacks to reveal exclusive bits of the key. Given that the best attack on AES doesn't even reveal 2, you will be hard pushed to make a reasonable attack like this.


Is it possible to perfom quadratic residues attack on elgamal cryptosystem? I understand how this attack work on mental poker, but i am unable to see how can i apply it in Elgamal.

First, some background on Quadratic Residues:

A Quadratic Residue (QR) is a number $x$ such that there exists some number $y$ with $x \equiv y^2 \pmod p$ (where $p$ is the modulus we're talking about - I'll make it implicit here on out), and it doesn't matter what $y$ is, only that whether such a $y$ exists.
There exists an efficient test where we can determine whether any value $x$ is a QR or not.
The value $x \times y$ is q QR if either both $x, y$ are QRs, or neither is.  If one is a QR and the other is not, then $x \times y$ will not be.
The value $x^n$ is QR if either $x$ is a QR or $n$ is even (or both) - if $x$ is not a QR and $n$ is odd, then $x^n$ will not be a QR either.

With that in mind, the El Gamal encryption of a message $m$ is the pair:

$$(g^r, h^r \times m)$$

where $g$ is publicly known generator, $h$ is the public key (which we assume that the attacker knows, and which will be $g$ raised to some unknown power), and $r$ is a random number selected by the encryptor (and hence unknown).

What we do is determine whether $h^r$ is a QR or not (which might sound a bit tricky, as we don't know the value of $h^r$, and so we can't use our efficient test).  However, we can deduce it based on the following cases:

If $h$ is a QR, then $h^r$ will be as well.
If $h$ is not a QR, that implies $g$ is not a QR either (because $h$ is $g$ raised to some power).  In this case, we check if $g^r$ is a QR or not - if it is, then $r$ is even (and so $h^r$ is a QR).  If $g^r$ is not a QR, then $r$ is odd (and so $h^r$ is not a QR).

Once we have determined that, we then check if $h^r \times m$ is a QR.  If the QR-ness of $h^r$ and $h^r \times m$ are the same (that is, both are a QR, or neither is), then $m$ must be a QR.  If they differ, $m$ must not be a QR.

Hence, in all cases, we can determine whether $m$ is a QR or not, by examining the ciphertext and the public key.


Why the basis is reduced in nearest plane algorithm in solving CVP In Babai nearest plane algorithm(solve approximate version of CVP), given the basis as input first step is to find the reduced basis(using LLL reduction algorithm). Why the reduced basis is used for further steps?

Short answer: If the basis is not reduced, then there are no guarantees on the distance between the target and the output, compared to the distance between the target and an actual closest vector. By LLL-reducing the basis you can bound this distance, and therefore Babai's nearest plane algorithm solves CVP to a certain approximation.

Take a look at the second step of Babai's nearest plane algorithm, where $t$ refers to the target vector.

$ b \leftarrow t$
for $i = n$ to 1 do
$\quad b \leftarrow b - c_i b_i$ where $c_i = \lceil \langle b, \tilde b_i \rangle / \langle \tilde b_i, \tilde b_i \rangle \rfloor$
end
output $t-b$

Where the tilde denotes the Gram-Schmidt orthogonalization of the basis. Essentially, it looks for an integer combination of the basis vectors that is close to the target vector.

Now, if $t \in$ span$(B)$, you can see that you can bound the distance between the output and $t$ by the sum of $\langle \tilde b_i, \tilde b_i \rangle$. LLL gives us a bound on these values. For an arbitrary basis, these norms could be very large, meaning the second step could be very, very off.

In the case that $t \notin$ span$(B)$, you can use a similar argument on the projection of $t$ onto span$(B)$.

For the exact details of how the LLL properties of the basis are used to prove the correctness of the algorithm, see this lecture.


Doesn't d6 to binary for 256-bit bitcoin private key generation produce biased results? If the mapping table looks like:

1: 000

2: 001

3: 010

4: 011

5: 100

6: 101

Then you are guaranteed that your key will never have a chain of 4 or more 1s, much fewer chains of 3 ones than would be expected from truly random number generation, and no chains of 8 or more 0s. Unless you're using an unintuitive mapping from d6 to binary (e.g. alternating 0 and 1), your dice would have to be $2^n$ (2, 4, 8, 16, etc.) sided in order to produce unpredictable binary results. On https://www.swansontec.com/bitcoin-dice.html suggests using d6 as an alternative to Hex dice, is this insecure? Wouldn't a deck of cards (1-10) have the same problem?

Yes, the method you describe above would indeed produce a key with only about $\frac{256}{3} \cdot \log_2 6 \approx 220.6$ bits of entropy.  (I say "about" because 256 is not divisible by 3, so the last die roll will only contribute one bit to the key, and the amount of entropy that bit will have depends on which of the three bits you choose.)

However, that's not what the script suggested on the page you linked to actually does.  Rather, it takes 100 rolls of a six-sided die (with a total entropy of $100 \cdot \log_2 6 \approx 258.5$ bits), interprets them as a base-6 number (after shifting the digits 1–6 to the range 0–5) between $0$ and $6^{100}-1$, and then converts this number to hexadecimal and takes the last 64 hex digits of it (which is equivalent to reducing it modulo $16^{64} = 2^{256}$).

This method will yield a key with almost 256 bits of entropy.  The reason it's only almost is because $6^{100}$ is not evenly divisible by $2^{256}$, so the modular reduction will introduce some bias.  In particular, $6^{100} \mathbin/ 2^{256} \approx 5.64$, so the lower 64% of the range of possible keys will be 6 / 5 times as likely to be chosen as the upper 36%.  Thus, the actual entropy of a key generated by this method will be approximately $$0.64 \cdot 2^{256} \cdot \tfrac{6}{6^{100}} \log_2 \left( \tfrac{6^{100}}{6} \right) + 0.36 \cdot 2^{256} \cdot \tfrac{5}{6^{100}} \log_2 \left( \tfrac{6^{100}}{5} \right) \approx 255.995 \text{ bits}.$$

BTW, simply rolling the die 99 times to generate a number between 0 and $6^{99} \approx 2^{255.91}$ and using that number directly as the key would yield a key with 255.91 bits of entropy, only about 0.08 bits less than the method used by the script.  Just to explicitly state the obvious, such differences of a fraction of a bit are completely insignificant — for all practical purposes, both methods will produce keys that are as good as a perfectly random 256-bit key would be.

In any case, even a key with 220 bits of entropy, as generated by the method described in your question above, should still be perfectly adequate for resisting brute force guessing attacks by any known or foreseeable adversary (at least using classical computers — but then, if large-scale quantum computing ever takes off, it will be bad news for elliptic-curve crypto regardless of key size anyway).

If you're worried about the special structure of the key (i.e. the avoidance of two digits out of eight when written in octal) possibly enabling some unknown class of attacks, just feed it through a hash function like SHA-256 before using it.  For that matter, you might as well just take a series of 100+ six-sided die rolls and feed it through SHA-256 to get a key that's effectively indistinguishable (assuming that SHA-256 is secure) from a perfectly random one.


Are there reference implementations of ECQV implicit certificates? I am interested in exploring ECC implicit certificates, specifically using the ECQV protocol. While the actual implementation would not difficult to perform using building blocks provided by most ECC capable libraries, I really would like to compare my application with a reference implementation.

Does anyone know of a reference implementation of ECQV?

For the sake of moving this question off of the "unanswered" list, the answer seems to be no. I spent time looking as implicit certificates are relevant to a project we are beginning to work on.

SECG, which has the draft standard for ECQV, does have a future project for test implementations of their standardized primitives/protocols.

They have a mailing list, but I have not subscribed. You could ask there.


Does CTR mode yield a PRF? Can the keystream generated by CTR mode be considered a pseudo-random function?

I give more information. Assume $f$ is a PRF. We define a function which takes 2 inputs, the desired length, and an arbirtrary value:

$F_l(r):=f(r\cdot l \cdot 1) \cdot f(r \cdot l \cdot 2) \cdot \cdots\cdot f(r\cdot l\cdot l-1)\cdot f(r \cdot l \cdot l)$ where $\cdot$ denotes the concatenate operation.

Is $F_l$ a PRF ?

It is not accurate to say that the keystream from AES-CTR is a pseudorandom function. However, it is a pseudorandom generator. Furthermore, the construction that you gave is close to working but it's unclear where the key fits in. I will therefore elaborate on what we can exactly say.

Let $F$ be a pseudorandom function, and for simplicity assume that the key length, input length and output length are all the same (and of length denoted $n$). We denote by $F_k(x)$ the output of the PRF on input $x$, with key $k$. Then, we have the following two facts:

$G(k) = F_k(0)\cdot F_k(1) \cdot F_k(2)\cdots$ constitutes a pseudorandom generator.
$F'_k(x) = F_k(0 \cdot x) \cdot F_k(1 \cdot x) \cdot F_k(2 \cdot x) \cdots$ constitutes a pseudorandom function. Note that in this construction, $x$ has to be shorter than $n$ to provide "space" for the counter.

You want the first case when you want a PRG using AES. Especially when you have AES-NI this is a very fast option.

You want the second case when you want a PRF with input length $n$ and a larger output length. There are a number of ways of doing this. Another way is $F'_k(x) = G(F_k(x))$ where $G$ is any PRG.


RSA with composite numbers It has been said that RSA uses a modulus product of two prime numbers for security reasons. But does RSA even work correctly if we allow composite integers instead?

I think that the answer is "NO".

Define “work correctly” as:

allows encryption and decryption to be carried out as in normal RSA, yielding the original message (message padding and unpadding can remain unspecified, or absent as in texbook RSA);
a security level can be given in terms of the key generation process (which may have alternate requirements to testing that $p$ and $q$ are prime).

If we remove from RSA the requirement that the factors $p$ and $q$ of the public modulus $n=p\cdot q$ are prime, and instead allow composites, then depending on the definition of RSA used, the resulting cryptosystem works in the sense of allowing decryption either:

almost not (only for few messages or exceptional choices of $p$ and $q$); that's if we blindly apply one of the common definitions of the relation between the public and private exponents $e$ and $d$, including $d=e^{-1}\bmod((p-1)\cdot(q-1))$ and $e\cdot d\equiv1\pmod{\operatorname{lcm}(p-1,q-1)}$;
for some messages (often all or most); that's for relations like $d=e^{-1}\bmod\varphi(p\cdot q)$ and $e\cdot d\equiv1\pmod{\lambda(p\cdot q)}$, and if we compute Euler's totient function $\varphi$ (also noted $\phi$) or Carmichael's function $\lambda$ with knowledge of the factorization of $p$ and $q$;
for all messages; that's when in addition of using the above relations, $p$ and $q$ are coprime and squarefree, or otherwise said when all the factors of $n$ are distinct primes.

For an illustration of case 2., consider $p=187=11\cdot17$, $q=253=11\cdot23$, $n=p\cdot q=47311$, $\lambda(n)=\operatorname{lcm}(11-1,17-1,23-1)=880$, $e=3$, $d=e^{-1}\bmod880=587$. For any $x$ with $0\le x<47311$, $(x^e\bmod n)^d\bmod n=x$ holds when $x\bmod11\ne0$ or $x=0$, but all other $4300$ values of $x$ are exceptions; e.g. $42^{3\cdot587}\bmod47311=42$, $43^{3\cdot587}\bmod47311=43$, $44^{3\cdot587}\bmod47311=12947$.

Notice that choosing $p$ or $q$ as a huge random composite is unpractical: in order to compute a working $(e,d)$ pair we practically must know the factorization of $n$, and factoring a big-enough composite $p$ is seldom easy, and sometime entirely impractical. Also, this method of choosing $p$ and $q$ would lead to $n=p\cdot q$ that could be relatively amenable to factorization, making the cryptosystem unsafe.

By the definition of RSA per PKCS#1 after PKCS #1 v2.0 Amendment 1 of July 2000, RSA only requires that all the factors of $n$ are distinct odd primes $p_j$, and that $e\cdot d\equiv1\pmod{\lambda(n)}$, where $\lambda(n)$ simply reduces to the Least Common Multiple of the $(p_j-1)$. When there are more than two $p_j$, the cryptosystem is known as Multiprime RSA. It allows for faster computation of the private function, and is safe with proper choice of the $p_j$.


Is there a human readable easier version to represent PGP Private keys? I'm working on a distributed application, and we need a way to authorize clients. Every client has a PGP keypair associated with them, and we require them to enter their private key (which is not stored) through which their pubkey is derived and used to identify clients and modify their fields on the distributed database.

Now, considering user experience, entering a private key on a website whenever you need to do something is troublesome. But we also cannot maintain a central database for username/password based authentication as that creates a single failure point (not what the distributed application is meant to do)

I am hoping there is some way to get an easier to remember human readable descriptor of the private key which can be used to authenticate - if something like that exists. Any other ideas are appreciated too.

P.S. - For background, I am not a cryptographer, I am a computer developer, so I don't fully understand how PGP works - excuse me if this is a noob question.

Apparently this answer will be updated as OP develop an understanding of his application. I've never used PGP, but general public-key cryptography concepts are always applicable.

  entering a private key on a website whenever you need to do something is troublesome

You can let clients derive their keys through memorable string - the user agent first derive a seed using a secure key derivation function (KDF) from 1) the user-supplied string, and 2) a random salt, then the seed is fed to a cryptographic deterministic random bits generator (DRBG), then the key-pair generation is run using the just-seeded DRBG.

Normally a hard-to guess 16-character string with upper and lower case letters and digits is a minimum. The salt should be a string of at least 16 fully-random bytes.

  But we also cannot maintain a central database for username/password

If you don't have a database of users, how do you authenticate them (recognize actual users from outsiders)? There is a solution: Use primitives that binds the authenticator to the public key, such as ECQV implicit certificate scheme, or identity-based encryption (IBE). These are not commonly-used public-key cryptography functionalities, and their post-quantum equivalents are far from mature.


Which of the following hash functions is collision resistant? Let $H: M \to T\ $ be a collision resistant hash function. Which of the following is collision resistant: $
1.H'(m) = H(m \big\| m)$

$2.H'(m) = H(m) \big\| H(0)$

$3.H'(m) = H(m) \oplus H(m)$

$4.H'(m) = H(H(m))$

$5.H'(m) = H(0)$

$6.H'(m) = H(|m|)$

$7.H'(m) = H(m)[0,\ldots,31] $   (i.e. output the first 32 bits of the hash)

Is the answer functions 1, (2) and 4?

looks like it it is collision resistant, as hashes the message "twice"
Is collision resistant, as a part of the digest is collision resistant.
Is always $0$, so not collision resistant
Collision resistant, as it hashes the message twice and outputs a valid hash of a valid message (the hash of the message)
Always the same. Not collision resistant
Always the same for messages of the same length. Not collision resistant.
Depends on your definition of collision resistant. By itself it's a subset of a collision resistant hash function it is collision resistant if the subset is large enough. So from a theoretical point of view there's no faster attack than brute-force to find a collision, making it a collision resistant 32-bit hash function. From a practical point of view or if you consider it a n-bit hash function with n the digestsize of $H$ it's not collision resistand as one can find one with $2^{16}$ hash function calls.

So the answer is 1,2,4 and maybe 7.


Why does RSA 1024 provide lower security level than EC256? And why do we have to use big numbers for RSA? Is it because of some RSA restrictions like p=q=3 mod 4?

There are some more efficient algorithms (still super-polynomial time, not enough to actually break them) to solve discrete logarithm problems and integer factorization problems, hence keys based on these problems are longer than EC based cryptographic keys which provide equivalent security, in which no such algorithms significantly better than birthday attack are known.


Finding all polynomials up to a given degree to generate a bit sequence Consider the following bit sequence:

00100000110

Using Berlekamp-Massey algorithm we can find the following minimal degree polynomial:

$P(x)=x^6 + x^5 + x^4 + 1$

Now, is there a way to find all polynomials up to a given degree 8 that can generate the same bit sequence?

Given any finite sequence $(a_0,a_1,\ldots,a_{N-1})$ we may be interested in generating exactly that sequence, or generating the minimal degree (periodic) sequence which has that sequence as its' starting bits.

Trivially, the circulating shift register of length $L$, initially loaded by $(a_0,\ldots,a_{L-1})$, will generate this sequence, by implementing the recurrence

$$x_{t}=x_{t-L},\quad t\geq L,$$

i.e., give the characteristic polynomial $X^L+1.$

The polynomial that Berlekamp Massey (BM) yields is the minimal degree polynomial which matches this initial segment. Your sequence $$(a_0,\ldots,a_{10})=(00100000110)$$ has length $N=11$ and BM gave you a  degree $6$ polynomial.

In general, there will be a set of polynomials that can generate an initial segment. If the minimal recurrence (i.e., the minimal degree polynomial generating your sequence) has degree $n$, $2n$ bits are required to uniquely determine it. So to get a unique polynomial of degree 8 which generates a sequence, 16 bits are needed.

If you specify less than 16 bits, you will in general get more than one generating polynomial. You have 5 bits "free" to go from 11 to 16 bits so you may get up to 32 different polynomials, corresponding to all these possibilities, barring any linear dependencies in the resulting polynomials.


Replacing elliptic curve diffie-hellman primitive with elliptic curve cofactor diffie-hellman for specifc curves? From what I've read about elliptic curve Diffie-hellman with and without cofactor (I am pretty new to the whole thing so I am not able to understand everything) is that when the cofactor of the curve $h$ is $1$, Both should give the same result. So for curves such as secp256r1 (which has $h=1$) both should give the same result. Unfortunately, when I am coding it using some third party libraries for Diffie-Hellman primitive without cofactor, I am not getting the expected result of Diffie Hellman with the cofactor. At this point, I am not sure if I have understood the theory incorrectly or if there's some issue with my code. Could someone verify or refute my understanding?

Just to close this question . Yes, both ( ECDH with cofactor) and (ECDH without cofactor)  give the same result if the cofactor of the curve is 1. After using another third party source I am getting the correct result. There was an issue in the code


SSL pinning - how to safely hide the certificate? We are doing an iPhone app and read multiple forums which says SSL pinning makes it possible to avoid man in the middle as we trust our web services server through the certificate which will be pre bundled along with our app to appstore.

How can i protect the certificate ? We tried storing inside the app in base 64ed DER format but the string commands on the binary executable prints that data. Is there a way where the certificate is hidden from the attacker so that the IPA file is not vulnerable from giving up the certificate.

You don't need to hide the certificate at all. The certificate only contains the public key and additional info of the owner (in this case the server). It shouldn't contain any private information. What you need to do is to store the certificate in such a way that you can trust the origin of the certificate.

So what you need to think about is certificate management. For instance, what happens if you need to replace the certificate? Is an update of the software enough?

The private key is not part of the certificate. This may not be obvious from certain API's such as the Microsoft API. You must make sure that you only export the X509 certificate(s) excluding the private key. If you are exporting a PKCS#12 (PFX) file then you may be doing something wrong.

The key pair should be generated on the system where you intend to use the private key. Access to the private key should be kept to an absolute minimum. The public key and certificate may be distributed freely.


Known plaintext attack on 3 round SIMON block cipher I am attempting to write a program to perform a linear approximation attack on a reduced round version of the SIMON block cipher, but I am stuck on how to actually apply the linear approximation to get the subkeys for each round. I found this paper, in which the following high-bias linear approximations are listed:

P[ F(X)_i = X_(i-2) ]                        = 3/4
P[ F(X)_i = X_(i-2) ^ X_(i-1) ]              = 3/4
P[ F(X)_i = X_(i-2) ^ X_(i-8) ]              = 3/4
P[ F(X)_i = X_(i-2) ^ X_(i-1) ^ X_(i-8) ]    = 1/4

Where F(X) is the nonlinear function in the SIMON algorithm and F(X)_i is the ith bit of the output of said function, and X_n is the nth bit of the input to the function. This all makes sense to me. I am stuck, however, on how to leverage these linear approximations to derive the subkeys for each round. How do I go from the linear approximation to a program that finds the subkeys? If anyone could help me close the gap in my understanding, or at least point me in the right direction, I would be very grateful. Thanks so much!

Edit: originally posted on Stack Overflow

The paper also discusses linear characteristics for multiple rounds:

We present several approaches to produce linear characteristics for
SIMON32/64 and present the best known linear characteristic for
11-round SIMON 32/64 with the bias of $2^{-16}$. We then extend this
characteristic to 13 rounds of the cipher.
We present several
approaches to produce an LC for SIMON32/64, as a case study, and
present the best known 11-round LC for this cipher with the bias of
$2^{-16}$ (expendable to 13 rounds of the cipher).

The linear approximations you list seem to be from equation 3. SIMON is a Feistel cipher. By combining the equation that describes one round of Feistel, the authors of the paper get the following linear expression for an entire round:
$$ (P_R)_2 \oplus (K^1)_2 \oplus (X^1_L)_2 = (P_L)_0, $$
which holds with probablity $3/4$. Here $X^1 = X^1_L || X^1_R$ is the output of the first round, and $P = P_L || P_R$ is the plaintext. The notation $(X)_i$ is used for the $i$th bit of $X$.
Note that the expression is written here for the first round, but it equally applicable to any round $i$, when written in the following form:
$$ (X^{i-1}_R)_2 \oplus (K^i)_2 \oplus (X^i_L)_2 =  (X^{i - 1}_L)_0, $$
where we replaced $P$ by $X^{i - 1}$ and $X^1$ by $X^i$.
This can of course also be written as
$$ (X^{i-1}_R)_2 \oplus (K^i)_2 \oplus (X^{i - 1}_L)_0 = (X^i_L)_2. $$
This is still true with probability $3/4$.
If we "substitute" (pile up) this last equation into a 3 round Feistel network (shown by Figure 3 in the paper), we get:
$$(X^{i - 1}_R)_2  \oplus (K^i)_2 \oplus (X_L^{i -1})_0 = (X^{i + 2}_R)_0  \oplus (K^{i + 2})_2 \oplus (X_L^{i + 1})_2,$$
or:
$$\Sigma_K \oplus (X^{i - 1}_R)_2  \oplus  (X_L^{i -1})_0 \oplus (X^{i + 2}_R)_0 \oplus (X_L^{i + 1})_2 = 0,$$
with $\Sigma_K = (K^i)_2 \oplus (K^{i + 2})_2$.
The paper goes on to use this expression for more rounds, but we can stop here. The above expression is a linear characteristic for 3 rounds of the cipher. Since we know with which probability the above expression holds (depending on the parity of $\Sigma_K$), we can start obtaining key bits.
This document explains that part well:

The process followed involves partially decrypting the last round of
the cipher. Specifically, for all possible values of the target
partial subkey, the corresponding ciphertext bits are exclusive-ORed
with the bits of the target partial subkey and the result is run
backwards through the corresponding S-boxes. This is done for all
known plaintext/ciphertext samples and a count is kept for each value
of the target partial subkey. The count for a particular target
partial subkey value is incremented when the linear expression holds
true for the bits into the last round’s S-boxes (determined by the
partial decryption) and the known plaintext bits. The target partial
subkey value which has the count which differs the greatest from half
the number of plaintext/ciphertext samples is assumed to represent the
correct values of the target partial subkey bits. This works because
it is assumed that the correct partial subkey value will result in the
linear approximation holding with a probability significantly
different from 1/2. (Whether it is above or below 1/2 depends on
whether a linear or affine expression is the best approximation and
this depends on the unknown values of the subkey bits implicitly
involved in the linear expression.) An incorrect subkey is assumed to
result in a relatively random guess at the bits entering the S-boxes
of the last round and as a result, the linear expression will hold
with a probability close to 1/2.

The above applies to SPNs, but for a Feistel network the prinicple is the same.


How many perfect secrecy systems are there? How many non-trivial*, interesting perfect secrecy systems are there other than the one-time-pad?  Does it seem that the one-time-pad and perfect secrecy are synonymous, but are there any other cryptosystems that have perfect secrecy aside from the trivial examples?

*Here the non-trivial means; the simple type that may be created by, say, picking a set of integers, and randomly corresponding each of those integers with a 0 or 1 (the key), then sending some permutation of the integers as cipher-text.

How many non-trivial*, interesting perfect secrecy systems are there other than the one-time-pad?

Infinitely many.

Let $\mathbb G$ be a group (written multiplicatively). Then

$\operatorname{KeyGen}(1^n)=k\stackrel{\$}{\gets}\mathbb G^n$, that is the key is a vector of $n$ independently random group elements.
$\operatorname{Enc}(k,m):\mathbb G^n\times \mathbb G^n\to\mathbb G^n:(k,m)\mapsto m\cdot k$, that is the plaintext is a vector of group elements and the ciphertext is simply the element-wise multiplication of each message element with the corresponding key element.
$\operatorname{Dec}(k,m):\mathbb G^n\times \mathbb G^n\to\mathbb G^n:(k,c)\mapsto c\cdot k^{-1}$, that is we simply combine each ciphertext element with the inverse of the corresponding key element.

Note that the above defines an encryption scheme for each group there is and that's at least countably infinitely many ones (as $(\mathbb Z_n,+)$ works for all $n\in\mathbb N$). In particular it also works for non-abelian (i.e. non-commutative) groups.

The above scheme can be proven secure under a similar argument to the traditional one-time-pad and in fact the traditional one is simply this with the group $(\mathbb Z_2,+)$.