Logjam: "composite order subgroups" explained for TLS developers and system admins? I have read the recent logjam paper Imperfect Forward Secrecy:
How Diffie-Hellman Fails in Practice.

On page 11 in the Recommendations section, they state:

  Avoid fixed-prime groups In the medium term, employing
  negotiated Diffie-Hellman groups can help mitigate some
  of the damage caused by NFS-style precomputation for very
  common fixed groups. A current IETF draft [18] proposes
  a negotiated group extension to TLS. However, we note
  that it is possible to create trapdoored primes [43] that are
  computationally difficult to detect. At the very least, primes
  should be checked to be safe primes, or groups should use
  a verifiable generation process such as the one proposed in
  FIPS 186 [37], and the process for generating primes within
  the TLS session should be fixed so as to thwart the risk of
  trapdoors.

While this is lighter on the math than the section Attacks on Composite-Order Subgroups, I still don't know what that means in terms of implementations, algorithms, and libraries.

Further down that page they also state

  A key lesson from this state of affairs is that cryptographers
  and creators of practical systems need to communicate better.

So, as a software guy working on a project which involves in-house implementations of TLS, I would love for a mathematician / cryptographer to explain to those us without group theory backgrounds  (if possible) what is mean by "choosing safe primes", and choosing a generator $g$ which "generates a group with at least one sufficiently large subgroup order" (pp. 6, Attacks on Composite-Order Subgroups), and what that means for the code that I write, algorithms I implement, and libraries that I call. A layman's explanation, or pointers to group theory-related algorithms for generating DHE parameters would be great.

A safe prime is a prime number $p$ for which $(p-1)/2$ is also prime. The order of an element $g$ of the group $\mathbf{Z}^*_p$ (the integers modulo $p$, excluding 0) is the smallest integer $n$ such that $g^n\equiv 1\pmod{p}$; this is always a factor of $p-1$. The orders of the subgroups of the group generated by $g$ are the factors of the order of $g$; what's important for security is that at least one of the prime factors of the order of $g$ is large (for safe primes, if the order of $g$ isn't 1 or 2 then it has a prime factor of $(p-1)/2$, which is large). If you pick a prime that's not a safe prime, you need to make sure the order of $g$ is a multiple of at least one large prime; it's also important to try to make sure it's not a multiple of many small primes, and/or to pick a large exponent.

You can find good safe primes in RFC 3526. You could also generate your own; just try a lot of large odd numbers and check if both $p$ and $(p-1)/2$ are prime. You then pick $g$ such that $g^2\not\equiv 1\pmod{p}$, and you're good (since that means the order of $g$ is a multiple of $(p-1)/2$). With a safe prime, the worst that happens is that the last bit of your exponent leaks, which isn't a big deal with decent-sized exponents (so you don't even need to pick too big an exponent to be secure).

The following is more detailed background on why this is important. I tried to explain the math behind it in a way you could follow without prior background, but am not sure how well I did so.

Group theory

Diffie-Hellman key exchange is done in a group, which is a set of elements and an operation that has a bunch of nice properties. In Diffie-Hellman, this group is the integers modulo a prime $p$, excluding any multiples of $p$ (so, the numbers between $1$ and $p-1$ are the elements of the group), with the operation being multiplication. A group has a set of elements associated with it; if there's a subset of those elements that is a group under the same operation, this is called a subgroup.

Diffie-Hellman more specifically happens in the subgroup generated by the generator $g$, meaning the smallest subgroup containing $g$. This subgroup consists of everything that can be written as $g\times g\times\cdots\times g$ (or $g^n$). The order of this subgroup (also called the order of $g$) is the number of elements in the subgroup, which is equal to the smallest $n$ where $g^n\equiv 1 \pmod{p}$ (once you get to 1, you start repeating yourself). The order of this subgroup is always a factor of the order of the main group (which for Diffie-Hellman is always $p-1$); this is true for all groups and subgroups.

Lastly, a number theory fact: If the order of $g$ is $r$, then $g^x\equiv g^y\pmod{p}$ if and only if $x\equiv y\pmod{r}$. This means that brute-forcing $e\equiv g^x$ just requires trying all values of $x$ between 0 and $r-1$.

Composite orders

A composite order subgroup is what it sounds like: the order of the subgroup generated by $g$ is not a prime number. In this case, if you have $e=g^x\pmod{p}$ and are trying to find $x$, you can break the problem up into solving the discrete log problem on smaller subgroups.

Suppose, for instance, that the order of $g$ is 220. Then $e^{44}\equiv (g^x)^{44}\equiv (g^{44})^x\pmod{p}$. The order of $g^{44}$ is $220/44=5$ (because $(g^{44})^5=g^{220}\equiv 1$). So, any $y$ for which $(g^{44})^y\equiv e^{44}$ is congruent to $x$ modulo 5. We can solve the discrete log problem on this order-5 subgroup to find the remainder of $x$ modulo 5. Likewise, we can find $x$ mod 11 by solving discrete log on an order-11 subgroup. Because the order of $g$ is a multiple of $2^2$, we need to essentially solve two order-2 discrete log problems: the first to get $x$ mod 2, then using that we solve another one to get $x$ mod 4.

Once you have the value of $x$ modulo all powers of all prime factors of the order of $g$, the Chinese remainder theorem says that you have enough info to uniquely determine the value of $x$ modulo the product of those powers of primes (i.e. modulo the order of $g$). It's actually extremely quick to do so (this is incidentally also the basis of an attack on textbook RSA with multiple recipients, in which you get $m^e$ modulo a lot of different values and can compute the real $m^e$). So, instead of having to solve discrete log on a 220-element group, you solved it on an 11-element group, two 2-element groups, and a 5-element group.

Also, as the order of $g$ is a factor of the order of the group, factoring the order of the group (i.e. $p-1$) lets you attack any generator in that group. That means that an attacker can do work in advance that lets them attack any use of Diffie-Hellman with a given value of $p$.

Mitigation

The solution to this is to make sure that one of the prime factors of the order of $g$ is very large; your strength is essentially the strength given by the size of the largest prime factor of the order of $g$, so you want to maximize that. The easiest way to do this is to pick a safe prime -- one for which $(p-1)/2$ is also prime. With a safe prime, the order of any element (which, remember, has to divide $p-1$) is either 1, 2, $(p-1)/2$, or $p-1$. It's easy to check that your generator doesn't have order $1$ or $2$, and if it doesn't then its order has a large prime factor ($(p-1)/2$).

If things aren't safe primes, you can still have secure choices of $g$ if you have a large prime factor in the order of $g$. However, all small factors of the order of $g$ leak some information about your exponent; if you have lots of small factors and pick a smallish exponent (which is normally perfectly fine), you can end up leaking lots of information about your exponent. Safe primes mean there's at most one small factor of the order of $g$, so you don't leak much information without having to try lots of possible values of $g$ to get one without many small factors or with a large factor.


How to get ramdom number between 1 and 2048 from /dev/hwrng? I am (perhaps naively) evaluating the security considerations of using the following code to create BIP39 seed phrases (on a read-only and offline Raspberry Pi).
Apparently, using jot -r 1 1 2048 is not ideal and I would like to leverage the HRNG (/dev/hwrng) on Raspberry Pi hardware.
printf "%s\n" "Create random 24-word BIP39 seed phrase…"
seed=()
for i in $(seq 1 24); do
  seed+=($(sed "$(jot -r 1 1 2048)q;d" "/path/to/bip39.txt"))
done
echo ${seed[@]}

$ cat bip39.txt | head
abandon
ability
able
about
above
absent
absorb
abstract
absurd
abuse

Edit: this approach would not work given BIP39 seeds use last word as a checksum (see spec).

There are different versions of jot, and they use different sources of randomness. The Debian man page states:

Random numbers are obtained through random(3).

s defaults to a seed depending upon the time of day

random is not cryptographically secure. This is not explicitly mentioned in the documentation, so it's a good guess that it isn't¹. Even if it was, The seed being the time of day is very predictable. So jot on Debian is not at all suitable to generate a key or anything else that needs to be secure.
The OpenBSD man page states:

Random numbers are obtained through arc4random(3). Historical versions of jot used s to seed the random number generator. This is no longer supported.

arc4random on OpenBSD is secure, as documented in the man page². So on OpenBSD, your script generates a passphrase securely, with $24 \log_2(n)$ bits of entropy where $n$ is the length of the word lists (assuming the word lists has no duplicates).

If you have GNU utilities, use shuf. It can be instructed to use secure randomness:

--random-source=file
Use file as a source of random data used to determine which permutation to generate. See Random sources.

By default these commands use an internal pseudo-random generator initialized by a small amount of entropy, but can be directed to use an external source with the --random-source=file option. (…) The set of available sources depends on your operating system.

On Linux, /dev/urandom is secure except on a freshly installed system that doesn't have a hardware random generator. Since your platform has a hardware random generator, you don't need to worry about the initial seeding of the system random generator.
So with GNU coreutils, your script can just be
shuf --random-source=/dev/urandom -r -n 24 <bip39.txt

¹I confirm that guess.
² Historically, arc4random used RC4, which is now broken. The output is biased, which would reduce the entropy of the resulting key, but not enough to break it. In any case OpenBSD switched to a different algorithm (currently ChaCha20), so arc4random is safe. Other modern BSD variants have switched arc4random to be secure as well, but beware that older releases of FreeBSD and NetBSD were insecure..


reduces the coefficients of a modulo 3 on NTRU i'm still don't understand about 'reduces the coefficients of a modulo 3' on NTRU tutorial

  $a = f*e = 3 - 7X - 10X^2 - 11X^3 + 10X^4 + 7X^5 + 6X^6 + 7X^7 + 5X^8 - 3X^9 -7X^{10}  \pmod{32}.$
  Note that when Bob reduces the coefficients of $f*e \bmod{32}$, he chooses values lying between -15 and 16, not between 0 and 31. It
  is very important that he choose the coefficients in this way.

  Next Bob reduces the coefficients of a modulo 3 to get
  $b = a = - X - X^2 + X^3 + X^4 + X^5 + X^7 - X^8 - X^{10} \pmod{3}$.

how can you get polynomial $a \bmod{3}$ is : $- X - X^2 + X^3 + X^4 + X^5 + X^7 - X^8 - X^{10}$?
what i know on 'polynomial $a \bmod{3}$' means every coefficient mod 3, so coefficient on $-X^8$ should be $2$ ($2X^8$) not $-1$ ($-X^8$), because $5 \bmod 3 = 2$?

Reducing mod 3 means indeed reducing each coefficient mod 3, and again we choose the representatives symmetrically around 0, so each coefficient becomes -1,0 or 1 (instead of, which is also possible, 0,1, and 2, or some other choice).

$-7X$ becomes $-X$ because $-7 \equiv -1 \mod 3$. The starting constant 3, becomes 0, and disappears, $-10X^2$ becomes $-X^2$ (adding 9), $-11X^3$ becomes $X^3$, as $-11 \equiv 1 \mod 3$ (add 12 to the left) etc. etc.

Your final example $5X^8$ could become $2X^5$, but also (subtracting 3 again, to get a representative from $\{-1,0,1\}$) the actually used $-X^8 = (-1)X^8$.

So mod 3 is actually a bit more restrictive: replace each coefficient by its unique equivalent value in among -1,0 and 1, not just any representative that would be equivalent to it. As your quote says "It is very important that he choose the coefficients in this way" (not only for 32, also for 3).


With wrong IV at receiver side, the CFB in better than OFB? Assume the receiver have a wrong IV (initialization vector), in the CFB mode only the first block of plaintext is wrong but in OFB mode the second and all blocks will be affected.

Is that correct? If it is, what is the meaning of the OFB mode compared with CFB mode?

Yes, it is correct. Just follow the bits in the decryption pictures on the Wikipedia page about modes of operation. Modes of operation don't have to have a meaning compared to other modes of operation. I don't see CFB or OFB used too much anymore. OFB with partial feedback has been shown to be less secure, so that shouldn't be used anymore.

Currently the cryptographic community doesn't seem to care too much about error propagation anymore. Instead, everybody tries to make sure that an authentication tag over the IV and ciphertext is present. If that is the case then errors can be detected and the message can be discarded. One of the reasons is that it is often possible to alter the ciphertext in transport protocols (e.g. when open WiFi hotspots are used), and few protocols handle partially correct data that well.

So you are much better off looking at authenticated modes such as GCM and EAX modes of operation.


Understanding one-way hash functions construction I understand the needs that lead to the development of cryptography and I am quite familiar with the uses we make of the cryptographic tools.

But, as a programmer, I am conditioned to see them as "black boxes" with specific properties. To me, SHA-X (with X being 1, 2 or 3) is some dark magic, even though I understand why I need it and use it.

That said, I am eager to find some literature to light this up.
From what I have read so far, I have seen that the common mathematical demonstrations consist of games and the evaluation of the winning advantage of an enlightened attacker over a player that would just randomly take decisions. This is exactly the kind of things I am looking for : what mathematical background lead to this construction for this hash function. Learning through an example can be worthy, but the more global this maths background is, the better.

To say it in other words, how does a cryptographer prove the essential properties of his design ? In the case of cryptographic hash functions, these properties are one-wayness, collision resistance and preimage resistances.

What are the logical steps, starting from the required properties, that lead to the specification of a hash function ? How are these properties translated into mathematical definitions ?

Note : I think I needed to ask that last question because for a cryptographic hash function, I feel there is the need to define some thresholds somewhere.

First, it's important to understand that no one knows how to build a practical hash function that is provably secure.

The stuff you've read about games and advantage are part of a theory for proving schemes secure, but that theory doesn't help you build a provably secure hash function all that much.  Rather, it starts from the assumption that a particular hash function is secure (or a block cipher or stream cipher is secure), and then builds more complicated stuff out of those basic building blocks.  So, that theory doesn't help us design the basic building blocks, like hash functions, in the first place.  (Sometimes the theory is used to help guide the design of the structure of a hash function, where designers build a hash function out of a building block like a compression function.  The designers might use the theoretical analysis to demonstrate that if the compression function is good, then the hash function will be good -- but it doesn't help you with the question of how to design a good compression function.)

For more details on how we know that a hash function is secure, see my answer to a similar question (on the IT Security Stack Exchange site).

Generally speaking, to learn how to build a secure hash function, you start by learning about all of the various attacks on hash functions.  Then, you try to design a hash function that will resist all of those attacks (as well as all others you can imagine).  Therefore, a good starting place for you would be to read about attacks on hash functions.

You could start by reading Chapter 9 of the Handbook of Applied Cryptography.  Also check out Wikipedia's articles on cryptographic hash functions and the Merkle–Damgård construction.
Then, you could read all of the submissions to the NIST hash algorithm competition; most of the submissions should provide a design rationale and security analysis, which should give you a chance to read about some of the attacks on hash functions and design strategies.  They should also cite related papers in the research literature, so next you could read papers in the research literature on hash function cryptanalysis -- you might start by reading the papers cited in the Wikipedia links mentioned above, then proceed to reading papers that are cited in submissions to the NIST competition or that you find through others means.  For instance, it's worth reading about parallel collision search, multicollision attacks, indifferentiability, and the sponge construction.

After several years of study, you'll be well on your way to becoming an expert in hash function cryptanalysis, and then you might be ready to start thinking about designing your own hash function.


Can root and intermediate CAs use different asymmetric ciphers and key sizes? For example, could a root CA use RSA-4096, one intermediate CA use RSA-2048, and another use ECDSA-256 (DH19)?

For example, could a root CA use RSA-4096, one intermediate CA use
  RSA-2048, and another use ECDSA-256 (DH19)?

If you use the standard certificate verification algorithm described in RFC 5280 (section 6) that is no problem. Using that algorithm you have a working_public_key_algorithm, working_public_key and working_public_key_parameters which get updated as the as the certificate path is being processed (always after the current certificate was processed) and they're initialized with the root algorithm / public key / parameters.

However, practically you will rarely find ECDSA certificates issued below RSA roots and RSA certificates issued below ECDSA roots. Apparently this is mostly for historical reasons as clients used to indicate what they support (RSA vs ECDSA) using their TLS cipher suite, ie when it contains *RSA_* they only support RSA-based certificates (which needs pure chains obviously) and analogously for ECDSA.


Prove that you have the data when hash is public I am designing an online service where users can upload files (3d models) for processing. I want to speed up things when the same file is uploaded by many different users by allowing them to post a hash (SHA256) of the file before sending the file. If the hash exists they immediately get the processed file otherwise they upload a file.
I worry about this approach that a user can find SHA256 of a file somewhere he may be able to download the processed file without actually owning the file. E.g. SHA256 is somewhere public, but the file is private (e.g. a marketplace made SHA256 for paid 3d models public and someone paid for them and processed them using my service) ... or the metadata is hacked
The questions are:

Is this a genuine concern? Should I be worried about people getting SHA256 and abusing it to get other user's files?
How do I fight this? I was thinking of using HMAC: the server would send a key to the user and ask him to generate HMAC for the file and send it back?
Would it be safe to make HMAC key public so I don't store it for each upload request but the user can just generate HMAC based on this public key?

It's indeed a genuine concern.

How to fight this?

Well, once client had provided the SHA256 hash of the file (to quickly index the file on the server), your server then provide a random one-time key and ask the client to hash the file again with HMAC and the key. Since the key is one-time and random, adversaries have little chance at guessing the key and forging a MAC tag of a file that they only knows the hash of.

It wouldn't be safer to make HMAC key public, as it's equivalent to regular hashing with custom initialization vector.

== Some side notes ==
Browsers nowadays have WebCrypto APIs, which provide the functionalities of hashing and HMAC, but using them in a web page requires the secure HTTPS connection. Also, these APIs don't work on File/Blobs, they work on ArrayBuffers, which for large files could be memory intensive.


Why does CTR mode become insecure after $2^{0.5 \times n}$ blocks? The question is exactly what it says on the tin. If $n$ is the block size in bits of a block cipher, then why does outputting $2^{0.5 \times n}$ block in counter mode become a problem when there is no repetition of the keystream until after $2^{n}$ blocks have been output?

The security proof and bounds, such as those on page 18 of BDJR's 97 paper, can be read to derive some understanding of what going beyond the bound means.

At a high level, the notion is that you model the adversary as querying an oracle who either performs encryption of the provided data with CTR or returns random values.  If the adversary can not distinguish between the two then the scheme is argued to be secure.

Now with respect to the bound you mention, if you give me $2^n$ blocks of zeros to encrypt and I give you back $2^n$ distinct blocks then you should feel confident I used CTR mode. After $2^{n/2}$ blocks of random values you have a good probability of having observed a duplicate if I am giving you random values.


Are EC public/private keys significantly weakened by having a known byte? I would like to use different EC keys for different purposes in an app, and I would like to easily see the purpose for which particular key (pair) was generated.

With ~65K attempts, I can generate a key-pair where the first byte of both the public and private key are equal to a particular "purpose code" byte value.

(e.g. 0x01 is for signing Xs, 0x02 is for signing Ys, 0x03 is for encrypting Zs, etc.)

Does this significantly weaken the keys, in ways other than lowering the brute-force workload from 2^256 to 2^248?

(The obvious approach is to keep the full 256 bits and use an extra byte for the "purpose" information.  Generating a key, chosen to store a little data, has the advantage that this extra data can be encoded in all common key serialization formats, whereas a new "purpose" byte would need all new tools.)

By fixing the first byte of both the private and the public key you actually reduce the key space by about 16 bits, because only about one in $2^{16}$ key-pairs has that property – as you notice. (If there is no way to exploit the restriction on both keys at the same time, you may lose less security but I would assume the worst.)

Doing this is fine, unless the elliptic curve system is almost too small anyway. If it was insecure, then one in e.g. $2^{16}$ randomly generated keys would be similarly weak.

So worst case you should have ~112 bits of security since a 256-bit elliptic curve usually has about 128 bits of security, but that should be enough.


Is Schannel supposed to use SHA1 for (EC)DHE params? I captured a TLS 1.2 handshake on my server (WIN2012.R2/IIS 8.5) and noticed that SHA1 is being used to hash ECDHE parameters despite both the server and client(s) supporting SHA2 signatures.

Cipher Suite: TLS_ECDHE_RSA_WITH_AES_256_CBC_SHA384 (0xc028)

TLSv1.2 Record Layer: Handshake Protocol: Multiple Handshake Messages
         Content Type: Handshake (22)
         Version: TLS 1.2 (0x0303)
         Length: 1980
    Handshake Protocol: Server Key Exchange
            Handshake Type: Server Key Exchange (12)
            Length: 361
            EC Diffie-Hellman Server Params
                Curve Type: named_curve (0x03)
                Named Curve: secp384r1 (0x0018)
                Pubkey Length: 97
                Pubkey:
                Signature Hash Algorithm: 0x0201
                    Signature Hash Algorithm Hash: SHA1 (2)
                    Signature Hash Algorithm Signature: RSA (1)
                Signature Length: 256
                Signature:

I've tested the clients with other servers and found SHA2 was chosen
in many cases so it seems to be my server (not clients) forcing the use of SHA1 for
some reason.
I've also tested another 2012 R2 VM I have as well as 2016 TP5 and
again with both, SHA1 is chosen for ECDHE.
The certificate chain is signed using SHA2 and the HMAC chosen in
this case was SHA384 so the server doesn't seem to have any problem
using SHA2 signatures in other cases.

Could this be misconfiguration on my part? I haven't found any way to effect the (EC)DHE signature algorithm in Windows either accidently or intentionally.

Could this just be a known trait of Schannel in server 2012? (If someone has a similar setup and could confirm by capturing a handshake, I'd appreciate it.)

In any case, is there any risk in SHA1 being used here?

Thanks!

I'm led to believe the use of SHA-1 for the ECDHE parameters is not due to misconfiguration, but is rather the intended (albeit not ideal) behaviour of server-side Schannel. This behavior seems to be present in versions up to Windows Server 2012 R2 and even continues with Windows Server 2016 Technical Preview 5.

I've captured handshakes with many, many random servers that advertise they're using some version of IIS and the negotiated cipher suite uses ECDHE. In all cases, the signature algorithm chosen for ECDHE params is SHA-1. I couldn't find a single IIS server that used SHA-2.

If anyone has any evidence that IIS/Schannel is capable of using SHA-2 in this scenario, please post, otherwise for now I'm going to consider this answered as "by design".


When is a cipher considered broken? We've all read how some people claim AES is broken because there was supposedly a way to get the plain text from a cipher text faster than brute-force. But is this the definition?

Is a cipher broken if you can get the key faster than brute-force? Or is there another definition for "broken"? Because if you have a 128-bit key and it takes $2^{126.5}$ operations to break it, I wouldn't call that broken, for that I find broken a bit of a strong word.

I did find this for an asymmetric key and the quote:

  An asymmetric authentication scheme is considered to be broken if an attacker with access to the verification key can generate any valid cipher text, even if he can convince you to sign arbitrary other plain texts.

...which isn't really applicable to symmetric keys. It is a perfect answer for asymmetric encryption but I'm looking for something more general or I could make a distinction between symmetric and asymmetric but then I would still like to know, when is a symmetric encryption scheme deemed broken?

Your explanation is "broken in the academically sense" - there is a theoretical way to break the algorithm better than brute force. AES is broken in this way. There's also "broken in the practical sense", which means you can break an cipher in real applications or protocols. AES is still safe in this sense, because you still need too much computation power and even related keys to get the original key.

There are also different attack scenarios. You can have ciphertext-only attacks - the attacker only knows the ciphertext. That's a pretty weak attack scenario and not realistic. What if the attacker knows some of the encrypted plaintext because it has a pattern? That's the known-plaintext attack. There are some more kinds of attacks with even more help for the attacker, but they are harder to do in the real world, but even if an algorithm is broken with one of this harder threats, that doesn't mean that the algorithm can't be used anymore. AES is secure because the attacks still need too much work to get the key.


Discovering private exponent from public key I'm going to assume this isn't possible, but I have to ask because I'm trying to fundamentally understand what I've thus far been trying to implement by following an RFC.

SRP-6a starts off with declaring that I should choose $N$, a sufficiently large prime, and $g$, a generator.  Let's say $N$ is 1024-bits and $g$ is 2.  A sufficiently random number $a$ is generated.  For arguments sake I chose the length of $a$ to be 128 bits.  My public key $A$ is then given as $g^a \bmod N$.

Now, assume that I'm the server (or in this case I'm just trying to debug an SRP-6a protocol), and I receive $A$.  Since I know both $g$ and $N$, can I determine $a$ (in a reasonable amount of time). I'm guessing absolutely not, but it would be nice to know precisely why.

When using a Discrete Logarithm based scheme, such as SRP, the rule of thumb is to always use private exponents with a bit length twice the desired security strength. Hence, a 128 bit exponent $a$ will at most give you 64 bits of security. If you want 128 bit security, you need (at least) a 256 bit exponent. This is because the algebraic structure of the groups used for such schemes, make it possible to calculate discrete algorithms using a meet-in-the-middle approach that effectively halves the necessary effort, compared to a naive brute force approach.

In this case, for instance, let $q$ be the order of $g$ in $\mathbb Z_N$. Calculate $y = A(g^{q-x2^n}) \bmod N$ for all $0 \le x \lt 2^{128-n}$ and put the pairs $y,x$ in a table for fast access, indexed by the $y$ component. Next calculate $y' = g^z \bmod N$ for all $0 \le z \lt 2^n$. If you find a $y$ in the table such that $y = y'$, then you know that $z = a - x2^n \bmod q$, and hence that $a = z + x2^n$.

The latter calculations might be carried out in parallel and might be more effectively optimized than the former, so the optimal trade-off might e.g. be to set $n = 80$, meaning you put $2^{48}$ pairs $y,x$ in your table and perform a total of $2^{80}$ parallel calculations $y' = g^z \mod N$. This is feasible using modern hardware.


Cryptosystems used to generate public key certificate Where can we find the cryptosystems used to generate public key certificate? Are the cryptosystems under the signature algorithm and signature hash algorithm? Do I need to analyze the packets trasmitted between my computer and the server? For example, ciphersuite.

Suppose the following ciphersuites are transmitted from ClientHello to the server.

- TLS_RSA_WITH_AES_128_CBC_SHA256           (0x003c)
- TLS_ECDHE_RSA_WITH_AES_128_CBC_SHA256     (0xc027)
- TLS_ECDHE_ECDSA _WITH_AES_128_GCM_SHA256  (0xc02b)
- TLS_DHE_DSS_WITH_AES_128_CBC_SHA256       (0xc040)
- TLS_RSA_ WITH_RC4_128_MD5                 (0xc004)

Can I say that the cryptosystems used to protect the communication between my computer and the server are RSA, ECDHE_RSA, ECDHE_ECDSA and DHE_DSS?

The ciphersuites only define the properties of the SSL channel that is to be created. The certificate - including the private key usage indicated in the certificate - should be consistent with the ciphersuite.

For instance if you have a ciphersuite starting with TLS_RSA then the certificate should allow encryption, and the public/private key should be RSA of course. If you have a TLS_DHE or TLS_ECDHE ciphersuite then the certificate should allow authentication with any supported authentication algorithm. Authentication is generally supported by the certificate of course, as that is the main use case for TLS certificates in the first place.

How the certificate was generated is outside the realm of TLS. Basically it doesn't care, as long as you can create a trust chain to a trusted certificate in the certificate store. For this it does need to be able to verify signatures though, so the algorithms used to sign certificates need to be supported.


What does a "real" quantum computer need for cryptanalysis and/or cryptographic attack purposes? The cryptographic world has been buzzing the word "quantum" for a while now (even the NSA is currently preparing itself for a post-quantum crypto world) and quantum-related hardware engineering is evolving constantly. For example: the 5-qubit quantum computer created at MIT by using the technique of ion traps succeeded in prime-factorizing 15. Does that mean that since it succesfully managed that, that it is a all-purpose quantum computer which could be used for cryptanalysis and/or cryptographic attacks?

If that's not the case, what exactly would a "real" quantum computer need (think: rough description of expected technical abilities, aka specs) to enable its users to use it for cryptanalysis and/or cryptographic attack purposes? And - ignoring rumours about potentially existing but confidential governmental projects - does any such system already exist today?

For example: the 5-qubit quantum computer created at MIT by using the technique of ion traps succeeded in prime-factorizing 15. Does that mean that since it succesfully managed that, that it is a all-purpose quantum computer which could be used for cryptanalysis and/or cryptographic attacks?

No, not even close.
Attacking e.g. RSA requires a lot more than five qubits.
Going from five qubits to, say, a million, is not a simple matter of just making more of the same thing; the physics and engineering needed to scale a quantum computer to a large system is it's own particular challenge.

Qubits experience errors

The simplest and perhaps biggest problem is that the more qubits your algorithm needs, the lower the chance that the algorithm completes without any qubits undergoing an error.
Suppose we need $n_\text{qubits}=100$ qubits to do a useful computation $[a]$ and suppose the number of logic operations we need for the computation is $n_\text{ops} = n_\text{qubits}^3 = 10^6$.
Qubits typically have a certain probability per time of experiencing an error, which leads to the fact that the probability $P$ that a given qubit has not undergone an error is an exponential function of time,
$$P = e^{-t / T_\text{coh}}$$
where $T_\text{coh}$ is the qubit's "coherence time".
Denoting the time of a single logic operation as $T_\text{op}$, we have
$$\ln P = -n_\text{ops}\frac{T_\text{op}}{T_\text{coh}} \, .$$
Supposing we want the qubit to have a reasonable probability to not have an error, say $P=1/2$, we get
$$\frac{T_\text{coh}}{T_\text{op}} = \frac{- \ln (1/2)}{n_\text{ops}} \approx 1.4 \times 10^6 \, .$$
In other words, the qubit lifetime $T_\text{coh}$ has to be a million times longer than the time of a logic operation.
As far as I know, current state of the art is $T_\text{coh}/T_\text{op} \approx 300$ $[b]$, which is a far cry away from $10^6$.

Now, so far we only talked about single qubits, but in order for the algorithm to succeed, we need all of the qubits to go without errors.
With 100 qubits, that puts the target $T_\text{coh}/T_\text{op}$ at $10^{8}$, which, if you ask me, is hopelessly high.

Error correction

  If that's not the case, what exactly would a "real" quantum computer need [...]?

Note that the arguments given above could be used to say that a normal computer shouldn't work!
Of course, we know that normal computers do work, so what's going on?
Regular computer bits (i.e. transistors) have extremely low error rates because they are self-correcting: if the current through a flip-flop fluctuates a bit, the bias circuitry and feedback keep it stable.
This is not possible with individual qubits essentially because you can't monitor a quantum state without affecting it, so there's no way to feed back on fluctuations.

On the other hand, with groups of qubits we can correct errors.
I'm not going to explain the details here, but it turns out that we can use a group of physical qubits to represent a single error-protected logical qubit.
In other words, by encoding the information of a single qubit into a large group of actual physical qubits, we're able to keep the information stable in the presence of errors on the individual physical qubits.
This is called "quantum fault tolerance" or "quantum error correction".
Fault tolerance requires a large set of qubits, probably arranged in a 2D grid, with fast, accurate measurement and logic gates, and the ability to use the results of various measurements to feed back on the qubits with control signals.$^{[c]}$

  ...think: rough description of expected abilities/specs) to enable its user(s) to use it for cryptanalysis and/or cryptographic attack purposes?

A technical, but somewhat comprehensive discussion is given in a review of the surface code by Austin Fowler.

Summary

The experiment with five qubits factoring 15 was far too small to tackle a cryptographically useful problem.
But even that aside, the underlying system is not fault tolerant, so even scaling that system up to lots of qubits wouldn't make it able to solve crytographically useful problems.
To do that, we need a large system with fast and accurate enough logic gates and measurement that it can do error correction.

  And - ignoring rumours about potentially existing but confidential governmental projects - does any such system already exist today?

No, there are no publicly known quantum computers capable of cracking RSA as of 07 March 2017.

As you've alluded, a lot of work in quantum computing has gone secret (e.g. all but one of the jobs I interviewed for after getting my PhD in experimental quantum computing would have required a security clearance) so we don't really know the full story.
That said, based on my and other people's experience in the field, it seems pretty doubtful that any of the secret projects have built a quantum computer capable of e.g. cracking RSA.

$[a]$: I'm not talking about RSA here, I'm talking about the most basic but useful algorithm you might be able to do on a quantum computer.

$[b]$: That's in superconducting qubits but that was a few years ago and there may be better results in other systems now that I don't know about.

$[c]$: I'm being a little loosey-goosey here; not all fault tolerant protocols have the same requirements.
I'm commenting on the ones that I think are most likely to be implemented due to the fact that they have the most forgiving requirements.


If I am about to generate one-time pad, where should I generate my pads from? If I want to generate a few one-time pads, is it OK to just read required number of bytes from /dev/urandom without weakening information-theoretical security?

/dev/urandom is only computationally secure, so you won't get information-theoretical security for your OTP if you draw it from /dev/urandom. If you're happy with computational security, you might as well use a stream cipher instead of a OTP. Stream ciphers are much easier to use securely than OTPs.

On Linux /dev/random aims for information-theoretical security, but in exchange you typically get pretty bad performance. How well it achieves that goal is practice is unclear, since it relies on entropy estimators for its entropy sources, and that's error prone. (I think on BSD /dev/random is equivalent to /dev/urandom because they don't care about information-theoretical security)


Access control problem in oblivious transfer I am not sure whether the title is proper or not, but this question comes to my mind when I was reading $k-n$ oblivious transfers.

In a $k-n$ oblivious transfer (OT) protocol, a party A has $n$ messages and another party B wants to retrieve $k$ of them. There are two basic requirements for OT:

A should not know which $k$ messages are retrieved by B.
B should not know other messages besides the $k$ messages.

Then, does B have access right to all the $n$ messages?

If B does not have the access right, B can retrieve any $k$ messages. In this case, B can actually retrieve all the $n$ messages.

If B does have the access right, why do we need OT. B can simply retrieve all the $n$ messages, since existing OT schemes require $O(n)$ communication overhead.

With this question in mind, it is hard for me to think of any practical scenarios where OT can be utilized. Can anyone give some application examples of OT?

EDIT: I found that there are some research papers about access control in OT. Still, the problem I asked above is mainly in the scenario of information retrieve where access control seems very important. I am interested in other possible applications where OT without access control can be utilized.

OT is typically not used as an application in its own right. In the context of access control, OT limits the number of messages received by B but not which messages. I don't know of any real applications for this (you could talk about a subscription where B has purchased the right to read any $k$ articles, but this is pretty artificial in my opinion).

However, OT is a very important and basic building block used in constructing secure computation protocols. It is used in generic protocols like Yao and GMW, and is often used in specific protocols for things like secure set intersection and others.


Privacy and Integrity in Public Cryptography I'm trying to figure out which is the best way to get privacy and integrity together in public cryptography.

Alice needs to send multiple files $f$ (may be big) to Bob.

I've thought:

Alice computes the hash of the file $h(f)$.

Alice signs $h(f)$ with her private key.

Alice encrypts with Bob's public key $f$ and $Sig_a(h(f))$ resulting in the ciphertext $Enc_b(f, Sig_a(h(f)))$.

Only Bob can decrypt with his private key: privacy guaranteed.
Once Bob decrypted, can verify Alice's signature.

In my opinion this protocol provides privacy and integrity together, right?

Update

So, according to your answers, here's what i've understood:

The protocol is terribly inefficient because it encrypts a large file using public cryptography. This would require to split the file in n chunks ($f_1,f_2,...f_n$) and to send to Bob $Enc_b(f_i, Sig_a(h(f_i)))$ for i = 1 to n. This may require a padding.
A bad guy (Charles) that receives $Enc_c(f, Sig_a(h(f)))$ could decrypt it and re-encrypt it with Bob's public key and send it to Bob. No confidentiality.
In order to fix this, Alice should perform $Enc_b(f,A,Sig_a(h(f),B))$

At this point we can say that:

This protocol (as it is) MAY (depends on how it is implemented in practice) guarantee integrity.
I would use Diffie-Hellman key-exchange protocol (the ephemeral version) to estabilish a secure channel and use symmetric cryptography.

Update 2

Not even integrity is guaranteed. I've seen the so called "message malleability".

Signing and encrypting together is not secure in this method, at least in the way most would perceive security. For example, Bob would likely interpret this message as being sent from Alice to Bob. However, Alice may have sent it to Charles who decrypted and re-encrypted the signed message under Bob's public-key. In order to do this securely, you need to add the sender's and receiver's identities inside (the signature with Alice's key should contain Bob's identity, and the encryption with Bob's key should contain Alice's identity). In addition, you need to use CCA-secure encryption. In short, this isn't so simple and you need to check the details in order to determine if it's secure. This topic is called "SignCryption" and you can look it up for more information.


OTP Scheme where only one party can generate the OTP, but both parties can verify it's validity As far as I understand, OTP usually works on a superficial layer by having two parties both know of a key and then authenticate each other by sharing a hash of the key and some sort of counter (e.g. currentTime mod someNumber) with each other. In theory, this means both parties can verify each other, as both have the capabilty to generate a OTP and both have the the capability to verify the integrity OTP given to them.

I'm looking for an OTP scheme between two parties where both parties can verify the validity of an OTP, but only one party can generate it. To my understanding, this would not work with the logic described above. Does such a protocol already exist? If not, is such a system even mathematically realizable?

I'm looking for an OTP scheme between two parties where both parties can verify the validity of an OTP, but only one party can generate it.

The obvious way to do this is for one party (Alice) to select the one-time password and send the hash of that password to the other party (Bob).  Then, Bob can verify that Alice has the correct password (as Alice actually sends it), but Bob himself cannot generate it.

If Alice and Bob need to do this $n$ times based on the same exchanged key, then what Alice can do is select the base key, and hash that $n$ times, that is, compute $H^n(\text{base key}) = \underbrace {H(H(H(…H(\text{base key})))))}_{n \text{ times}}$, and send that to Bob.  Then, to authenticate the first time, she would send $H^{n-1}(\text{base key})$, which Bob can verify with his copy of the base key (but could not compute beforehand).  To authenticate the second time, she would send $H^{n-2}(\text{base key})$, and keep on doing this up to $n$ times.


Can iterated hashing be used to mitigate collision and preimage weaknesses? How much security does double hashing add regarding collisions and preimages? Is it helpful to iterate a hash function even more times than two?

For example, can MD5 be fixed (in practice) by applying the hash function twice (MD5(MD5(x)))? Also, Bitcoin uses SHA256(SHA256(x)). Does this add security in practice?

I understand that iterating a function many times can reduce the number of possible outputs. Also, the function might enter a cycle. Is that a problem with just a few iterations (such as two)?

(This question is not about storing passwords securely.)

With respect to collisions, hashing twice can not increase security, because if $x$ and $x'\ne x$ collide for $H$, that is $H(x)=H(x')$, then  $H(H(x))=H(H(x'))$. Otherwise said, any collision for $H$ is a collision for the double hash $H\circ H$. It is therefore trivial to exhibit collisions for $\operatorname{MD5}\circ\operatorname{MD5}$. Hence the answer to the question as worded in its title is NO.

With respect to preimage, hashing twice demonstrably does not harm security (from a preimage for $H\circ H$ one can make a preimage for $H$, simply by applying $H$), and tends to improve it for practical functions. In particular, one hypothetically able to build preimages for $\operatorname{MD5}$ only for 512-bit messages would likely have a hard time extending that to $\operatorname{MD5}\circ\operatorname{MD5}$.
Handwaving argument: if for some 128-bit $v$ one could find a 512-bit $\operatorname{MD5}\circ\operatorname{MD5}$ premiage $m$, then the easilly computed $m'=\operatorname{MD5}(m)$ would be a 128-bit $\operatorname{MD5}$ preimage of $v$, which arguably is harder to find than a 512-bit $\operatorname{MD5}$ preimage of $v$, since for a given $v$ it is expected that there are about $1$ premimage of the former kind, and about $2^{384}$ of the later.

One area where double-hashing increases security is length extension attack. $\operatorname{SHA-256}$ is trivially vulnerable to that, $\operatorname{SHA-256}\circ\operatorname{SHA-256}$ is not.

In some use cases, hashing twice can destroy security, including for common hashes; an example is given here; in summary: some proof-of-work protocol safe when using $H$ is entirely unsafe using $H\circ H$.

With usual hash functions (or ideal ones), hashing twice does not dramatically reduce the output space (it is reduced by a factor about $1-1/e\approx0.63212$); that makes accidental collision slightly less unlikely, and it is mostly immaterial in practice. It does not make collisions easier to exhibit, since the amount of invocations of $H$ expected necessary to exhibit a collision by whatever brute force method can not decrease (if it did, that would be trivially usable to exhibit collisions for $H$ at reduced cost).


Actual RSA encryption & decryption of strings? $K_{pub} = (n, e)$
$K_{pvt} = d$
Then
$E_{K_{pub}}(x) \equiv x^e \mod n$
Practically, when RSA is used to encrypt strings, what is the $x$ here? You cannot take it byte by byte because $\mod n$ will result in values larger than a byte. So what is done?

Practically, when RSA is used to encrypt strings, what is the $x$ in $x^e\bmod n$?

That depends on the variant of RSA. Among the most common:

Toy-sized textbook RSA, where the public modulus $n$ is small: it is customary to encrypt letter by letter (or pair of letters, as in the original RSA article's small example) and concatenate the RSA cryptograms. Thus $x$ is the rank of the letters in the encoding used (or $x=x_0\,b+x_1$ where $x_0$ and $x_1$ are the ranks of two letters, with $b$ a public constant greater than the maximum value of $x_i$, e.g. $b=100$ in said article). There is no security for small $n$: a toy hammer won't actually nail. Small $n$ is anything up to like a hundred decimal digits. That can be factored quickly, which allows decryption. See this for records.

Textbook RSA with large $n$: it is customary to transform the string into bytes (e.g. per UTF-8, the modern compatible superset of ASCII), then from bytestring to integer $x$ (usually per OS2IP). In Python
int.from_bytes(bytes('François wears a !', 'UTF-8'), byteorder='big', signed=False)

There is a size limitation to $k-1$ bytes, where $2^{8(k-1)}<n<2^{8k}$, which insures $0\le x<n$. On decryption, leading zero bytes are ignored/removed (due to the simplistic conversion from string to bytestring). Variations abound (some encoding of size to allow any bytestring, padding on the right so that $x$ is large even for small strings, endianness…).
Caution: Textbook RSA in not secure under Choosen Plaintext Attack:

An attacker can trivially verify a guess of the plaintext: just encrypt the guess and check against the cryptogram. That attack is devastating for names on the class roll, credit card number…
When short strings encode to small integers $x$, several other attacks apply, including

when $x$ happens to we writable as $x=x_a\cdot x_b$ for integers $x_a$ and $x_b$ small enough to be found by enumeration, there's a meet-in-the-middle attack
when $e<\log_2(N)/\log_2(x)$, it stands $x^e\bmod N\,=\,x^e$, and thus it's trivial to find $x$ by $e\text{th}$ root extraction.

RSAES-PKCS1-v1_5: similar to 2 plus random padding, and means to remove it on decryption. $x$ is a combination of the string to encode, 3 constant bytes, and at least 8 random (non-zero) bytes. The string is thus limited to $k-11$ bytes (per §7.2.1 step 1). This method is better, but still has serious defects:

Implementations of decryption are difficult to protect against side-channel attacks. The first was Daniel Bleichenbacher's Chosen ciphertext attacks against protocols based on the RSA encryption standard PKCS #1, in proceedings of Crypto 1998, and there are many variations.
Unless we lower the $k-11$ limit, encryption is inherently vulnerable to an attack under CPA costing $2^{63}$ encryptions.

For these reasons, RSAES-PKCS1-v1_5 should not be used in any new design.

RSAES-OAEP: this is a major improvement of the above, using a hash. The string is transformed by the padding process into integer $x$ that is sort of random with $0\le x<2^{8(k-1)}$, and that's undone in decryption. Secure implementations of decryption are easier than for RSAES-PKCS1-v1_5. Security is theoretically reducible to that of the hash and of the RSA problem (finding a random $x$ given $x^e\bmod n$). The size limitation becomes $k-2h-2$ bytes (per §7.1.1 step 1.b) where $h$ is the size of the hash (e.g. $h=32$ bytes for SHA-256).

Hybrid encryption, e.g. RSA-KEM. A random value $x$ with $0\le x<N$ is RSA-encrypted with no padding, a symmetric encryption key is derived from that, and that key is used to encrypt(-and-MAC) the string to encrypt. Some avenues of implementation mistakes on decryption that still exist in RSAES-OAEP are gone. Security is theoretically reducible to that of the encryption and the RSA problem, with a simpler proof and/or quantitatively better assurance than for RSAES-OAEP. There is no size limitation. However the size of the cryptogram is slightly increased, and we need a Key Derivation Function and an authenticated cipher, when that's built into RSAES-OAEP.


"Dave Check" for a tweakable P-256 ECDH KDF I have two devices with hardware tokens that contain P-256 private keys, and which allow me to compute ECDH shared secrets with arbitrary public keys. I need to build a tweakable key derivation function, which deterministically allows both sides to generate the same key given their partner's P-256 public key and a tweak value. The construction must have the property that computing the key for a new tweak value requires an operation on the hardware token, even if token outputs for many other tweak values are known.

I've come up with the following pseudocode:

// NIST recommended way to generate a private key
l = 2^256 − 432420386565659656852420866394968145599
P256Priv(ikm): (HKDF_expand(40, ikm) % (l - 1)) + 1

// point multiplication with g as the P-256 generator
P256Pub(p): g * p

// different function instances for different tokens
tokenECDH(inPub): ECDH(tokenPriv, inPub)

// Using XOR because it makes both sides symmetrical
TweakableKDF(tokenECDH, peerPub, tweak, numBytes):
    Epriv = P256Priv(tweak)
    Epub = P256Pub(Epriv)
    HKDF_expand(numBytes, tokenECDH(Epub) ^ ECDH(Epriv, peerPub))

It looks to me like this would be secure, but I don't want to be a Dave. (Also, I can't help but wonder if there's something standard out there that does this already; I looked briefly and was surprised I didn't find much.)

Any Questions? Comments? Snide remarks?

This is broken, because possession of Epriv (a function of the public tweak value) allows calculation of the output of tokenECDH(Epub) given knowledge of tokenPub (another public value).

This is stupid obvious now, but it took several days to figure it out.


Can cryptocurrency mining devices be used for cryptanalysis? In the past year or so we have seen production of ASIC devices designed for mining of cryptocurrencies.  These devices can perform SHA256 hashing at rates much higher than was seen in the past and are continually advancing in power.  Can such devices be used to perform cryptanalysis instead of mining? Does this development pose a threat to our current security assumptions?

Practicality: Using a bitcoin miner for cryptanalysis would at the very least require you to write very low-level custom code. Indeed, depending on the precise hardware/software split used by the miner, it might well require modifying the actual hardware to facilitate your cryptanalytic attack. Anyway, let's suppose someone could 'convert' one. What would this mean?
 Well, if someone could convert a bitcoin ASIC into a viable cryptanalysis box, then you can bet the ASIC companies would just go ahead and produce them directly.

It is probably reasonable to assume that 'groups actively involved in cryptanalytic attacks already use some of the best hardware available, so in practice a converted miner would still probably leave you behind the curve. Anyway, supposing it did, your question would boil down to:

What would happen if the 'effectiveness'$^{[1]}$ of cryptanalytic equipment suddenly advanced by an order of magnitude?

Most good crypto is either believed to be well outside the bounds of brute force (eg see these answers about AES, RSA), even when we make very generous assumptions about an adversaries computational power. As such, even relatively significant improvement in cryptanalytic equipment (which is what your question suggests) will make a negligible difference in these problems.

Notes:

We assume 'effectiveness' has some appropriate meaning for the problem in hand, eg cost/size/speed etc


Ciphertext-only attack on Simplified DES Is it possible to deduce the plaintext block or the key, given only a Simplified-DES ciphertext block (e.g. c=01110110)? I'm reading Cryptography And Network Security, by William Stallings and I'm bit confused.

Simplified DES is a toy Feistel cipher with 16-bit 8-bit block and 10-bit key, and only two rounds, intended for educational purposes. Here is a preview of the original paper, and an implementation; another; yet another.

If one knows one block of ciphertext, but nothing about the plaintext and key, the plaintext can not be guessed entirely: each of the $2^{10}$ key will lead to a plaintext. Most plaintext will be reached several times, but a few plaintext might be excluded. If S-DES was a perfect toy cipher, it seems that any particular plaintext would have odds about $(1-2^{-8})^{10}\approx1.8\%$ to be impossible (it turns out odds are much higher for S-DES with two rounds, which is far from a good cipher); this in itself would constitutes a practical attack in some contexts (e.g. when one is content to exclude that the plaintext is "OK" or "NO", with some sizable odds). An adversary can also assign odds to each possible plaintext, and is at a sizable advantage over a random guess of the plaintext.

If one knows enough blocks of ciphertext, and something about the plaintext, even so vague as "it is mostly text", then an attack is easy: decipher with all the possible keys, and have a human look at the $1024=2^{10}$ resulting plaintexts, formatted with one line per candidate key. Most likely the right plaintext will be spotted by naked eye+brain within seconds. This can be helped by ordering the candidates according to how well they compress with LZW or similar. Success depends on the length of the known ciphertext, and redundancy in the plaintext. If some bits of the plaintext are known, then very little ciphertext is enough (e.g. about 5 blocks if 2 bits per plaintext blocks are known to be 0, which is the case for ASCII).


Maximum security strength in bits of ISAAC cipher? Wikipedia claims key length can be very big in this cipher, so I assume it can offer a million bits of security provided entropy of key is the same?

Of course I can SHA-256 hash the key to allow any key sizes for AES... but it defeats the whole purpose of having such large entropy when the security is less.

So what is the maximum level? For instance, AES-256 provides a 256 bit security level.
I don't want it to wrap the keys or diminish its security/entropy.

Wikipedia and most sources are not clear about it.

ISAAC's internal state is a 256-element array of 32-bit words, so the maximum key size is 8192 bits. In theory, this means ISAAC has a maximum keyspace of 28192. It's important to remember, though, that attacks are known that can result from weak states, meaning not all keys are created equal. While this may not be an issue in practice, there are two primary reasons why you shouldn't use it:

It's not particularly well-researched, so more serious attacks may be lurking.

The entire 8192-bit keyspace is utterly unnecessary. 256 is more than enough.

Just stick with 256-bit AES if you need a block cipher, and ChaCha20 if you need a stream cipher.


Mapping points between elliptic curves and the integers My primary question is:

Is there an easy way to create a bijective mapping from points on an elliptic curve E (over a finite field) to the integers (desirably to $\mathbb{Z}^*_q$ where $q$ is the order of E)?

To phrase it a second way, given a point on the curve that is chosen with uniform randomness, can you translate it into a uniformly random integer in some interval (or group)? I'm also interested in mappings that are statistically close to uniform.

(I thought of using a random extractor, but this generally requires 2m bits of min-entropy in the input to produce m bits of near-uniform randomness)

I was reminded of this question when reading the Telex paper, where they encounter this issue. Their solution is to use two specially selected curves, a curve and its twist, and only map the x-coordinate.

Secondary questions:

Using a curve and twist, is there a way to use the y-coordinate to select which curve so that the mapping is one-to-one?
If there is an approach, does it also work with pairing-friendly curves?

I do not know of any general way to create the mapping you want (and if there was, it might turn into an efficient point-counting algorithm, which would be great), but you can do this on some curves.

Consider a prime $p$ equal to $2$ modulo $3$. In $\mathbb{Z}_p$, every value has a single cube root (because $3$ is then invertible modulo $p-1$). Then, look at the curve $y^2 = x^3+1$. For any value of $y$, $y^2-1$ has a unique cube root $x$, so there is a one-to-one mapping between non-infinity points on that curve and their $y$ coordinate in $\mathbb{Z}_p$. For completeness, map the "point at infinity" to the integer $p$, and you are all set: an easy bijective mapping between the $p+1$ curve elements, and the integers modulo $p+1$.

Moreover, this curve is pairing-friendly, with an embedding degree of only $2$ (because $p+1$ divides $p^2-1$). It also allows a distortion map so that you can have a symmetric pairing: if $\mu$ is a cubic root of $1$ distinct from $1$ (so an element of $GF(p^2)$, the field extension), then the mapping $m$ from $(x,y)$ to $(\mu x,y)$ is a morphism over the curve. Then you can define a pairing $e(P, Q)$, where $P$ and $Q$ are both points on the original curve (in $\mathbb{Z}_p$) as the Tate (or Weil) pairing computed over $P$ and $m(Q)$. This allows you to stay on the base curve as much as possible; only the pairing output will need the field extension.

Ben Lynn shows some details in his PhD dissertation (he calls that curve a "type B"). Note that since there is a pairing of embedded degree $2$, then discrete logarithm on the curve is "reduced" to discrete logarithm in the $GF(p^2)$ field; so, for proper security, $p$ must be at least 512-bit long.

Edit: A similar trick works for "type A" curves with equation $y^2 = x^3 + ax$ in $\mathbb{Z}_p$ for $p = 3 \mod 4$ and a constant $a$. For a given $x$, then exactly one of the three following situations occurs:

There are two distinct values $y$ such that $(x, y)$ is a valid point, and they are opposite of each other, so one is lower than $p/2$ and one is greater.
There is no valid $(x, y)$ point, but there are two valid $(-x, y)$ points for two distinct values of $y$.
$(x, 0)$ is a valid point, and so is $(-x, 0)$ (this one can happen only if $-a$ is a square modulo $p$).

So you can map the point $(x, y)$ to:

$x$ if $1\leq y \lt p/2$
$-x$ if $p/2 \lt y \lt p$
$x$ if $y = 0$

Then map the point of infinity to $p$, and you're done.


Where should I start to learn cryptography? I want to learn cryptography. I just wanted to ask people who are experienced about the field where I should start. Any recommendation would be something for me.

Thank you in advance.

https://gnupg.org/documentation/index.html

Not experienced, just sharing one of the ways, which working for me (Online identity verification issues -> Web of trust -> PGP -> Cryptography).


Message authentication vs entity authentication Does message authentication authenticate the entity?

If the answer is "No", because message authentications like MAC work with the shared symmetric key, then my second question is:

  Does a message authentication using an asymmetric key like the digital
  signature enable both entity and message authentication?

If the answer is yes:

  Is it arguable to say that message authentication using asymmetric key
  provides both entity and message authentication?

Message authentication (sometimes called data origin authentication) is the assurance that a given entity was the original
  source of the received data.

  Entity authentication (or user authentication) is the assurance that a given entity is involved and currently active in a
  communication session. [1]

A MAC provides data origin authentication as the receiver knows that the message and corresponding MAC could have only come from the one person with the shared key. Used on its own, a MAC will not give you entity authentication.

A digital signature also provides data origin authentication as the verifier knows that only the owner of the private key could have produced a valid signature. Used on its own, a digital signature will not give you entity authentication.

You mention a shared symmetric key and whether or not a security service is provided. You are likely confused with non-repudiation.

  Non-repudiation is the assurance that an entity cannot deny a previous
  commitment or action.[1]

If there is a shared key (such as in the MAC setting) one user could deny having produced a MAC tag on the message as the key is shared- external parties are not sure which owner of the MAC key could have produced the tag. Whereas with digital signatures, each key is unique to each user, so there is non-repudiation as only one user could produce a valid signature.

Used naively, neither MACs nor signature provide entity authentication as signatures/MAC tags could be forwarded or replayed. Recall: message authentication provides assurance on the original source and does not tell us anything about when the message was sent or who is sending it now.

Consider the following scenario with data origin authentication but no entity authentication: Alice could sign a message and send the message and signature to Bob. Bob could then forward the message and signature to Charlie, who can verify that the original source of the signature was Alice (as there is message authentication) but not that they are communicating with Alice now. Hence there is no entity authentication.

To get entity authentication, we need some kind of freshness. For example, for Charlie to be assured about Bob's identity and current activity, Charlie could request Bob produce a valid signature on a fresh nonce, generated by Charlie. This ensures that Bob is currently active and that the signature came from him. Obviously, this may be vulnerable to man in the middle attacks (Bob could forward the none to Alice to sign, and return the signature to Charlie), but there are things that can be done about this (for example, by asking Bob to sign the challenge along with a session ID: the session ID is unlikely to be the same as the session between Bob and Alice, so Alice would not sign).

In general, think of entity authentication as data origin authentication + freshness.

[1] Reference: Everyday Cryptography, 2nd Edition by Keith Martin (2018).


questions about sensitivity in differential privacy Ted here (What does the term "differential" in "differential privacy" mean?) describes the difference between local and global sensitivity as

"By contrast, local and global sensitivity are only tools to build differentially private mechanisms: they measure how much changing the data of one user will change the output of the statistic you're trying to compute. Global sensitivity measures how big that change can get for every possible database, while local sensitivity measures it for a single database. Local sensitivity is mostly used to define another concept, smooth sensitivity, which in turn is used to design DP mechanisms."

for every possible database, we mean that ones record is to more than one database?

what is more, I see in the definition that local sensitivity takes account only for D'. why not the D as well?

$D$ is the database at hand. Differential Privacy is a property of a randomized algorithm, which is associated with a domain. So, DP holds for any neighboring databases in the domain. However, when you have a true database $D$, in some cases you don't need to add a noise whose distribution is associated with the global sensitivity to ensure privacy. You can add a smoothened version of the  local sensitivity to add a smaller noise, where local sensitivity is roughly the sensitivity of the function restricted to the neighbors of $D$.


Embedding SHA256 inside SHA1 for BitTorrent BitTorrent uses SHA1 for its hashes, but SHA1 is unsafe and people can tamper the preimage and still obtain the same hash, right?
So imagine I want to be very sure the file I'm sharing on BitTorrent will be correctly downloaded by who is downloading it. Does it work to include 2 files, being:

The file I'm actually sharing;
A file containing the SHA256 of the file I'm sharing.

Then the receiver must just check if the SHA256 matches (plus check if the SHA1 matches, which will be done automatically by the BitTorrent client).

The problem with SHA-1 is the collision attack that way before the actual attack shattered.io NIST dropped it in 2011 from digital signatures since finding collision has catastrophic result in Digital Signatures. The generic collision of SHA-1 requires $2^{80}$-time and that was considered low for 2011 and beyond. The Rabin was the one first to use the hash ( it was then called compression) to prove the security of their signature scheme that we call now the Rabin Signature Scheme. SHA-1 is still allowed by NIST for for
using non-digital-signature applications as Acceptable status in 2019, NIST.SP.800-131Ar2

BitTorrent uses SHA1 for its hashes, but SHA1 is unsafe and people can tamper the preimage and still obtain the same hash, right?

That is not the pre-image attack that is given a hash value $h = H(m)$ for some message $m$ find a pre-image $x$ of the hash function $H$ so that $h = H(x)$. We can have $m=x$ or not. Equality is not required from the pre-image attack by definition. As one can see, this is very helpful for password cracking, it doesn't matter you have found the same password or not since both are working. There is no pre-image attack on SHA-1 better than the generic pre-image attack and that still requires $2^{180}$-time.
What you have tried is the second-preimage attack that is given a message $m$ and its hash values $h = H(m)$ find another $m'$ such that $h = H(m')$. SHA-1 has no second-preimage attack that faster than the generic pre-image attack and the cost of the generic second-preimage attack is $2^{160}$-time for SHA-1.
Tampering one-bit arbitrary you will get $1/2^{180}$ probability that has the tampered files same hash if we consider the output of the SHA-1 as uniform random.
Finding second pre-images is very dangerous. For example; one can design a new malicious IOS for the existing ISO and replace it. There is a problem here on the BitTorrent network that is many people share the same file and this will create conflict on the IOS that people downloaded. Therefore for an active download, it may not possible. For a new download, if the attackers are fast on finding the second-preimage attack, then they may replace the original copy before distribution, too IFs, right?

So imagine I want to be very sure the file I'm sharing on BitTorrent will be correctly downloaded by who is downloading it. Does it work to include 2 files, being:

The file I'm actually sharing;
A file containing the SHA256 of the file I'm sharing.
Then the receiver must just check if the SHA256 matches (plus check if the SHA1 matches, which will be done automatically by the BitTorrent client).

SHA256 calculation is free since it has no key. The IF attacker can still calculate the malicious ISO and their SHA256 hash and store as you did.
Risk Management
The usage of the SHA-1 really depends on risk management. For example, Git still uses SHA-1 and Linus has a clear reason for this;

Git does not require the second preimage resistance of SHA-1 as a security feature, since it will always prefer to keep the earliest version of an object in case of collision, preventing an attacker from surreptitiously overwriting files.

Now what about BitTorrent
BitTorrent divided files into 64 KB – 2 MB chunks. The torrent's metadata file (.torrent file) stores each piece's size and hash value. Together with the info_hash that store makes BitTorrent quite resistant to intentional tampering (poisoning). To verify the chunks SHA-1 is used the value in the info_hash.
There is research on this;
Adaptive Content Poisoning To Prevent Illegal File Distribution in P2P Networks*

We discover that BitTorrent is most resistant to content poisoning.
....
Because the index file is distributed outside of the P2P file-sharing system, each chunk can be verified with a reliable hash contained in the metadata. This verification provides BitTorrent protocol with high resistance to content poisoning.

There is also a long talk about this problem on the GitHub of the Bittorent; In short, if you trust the host that shares the .torrent file, you are safe.


Secure content-defined chunking Intro

For deduplication purposes, I need to split a stream of plaintext bytes into variable-sized chunks. The way this is traditionally done is using a rolling hash function defined over some window $w$ (e.g. 48 bytes). This window "slides" along the byte stream and is evaluated at each byte position, and when the value of the function is let's say $f(w) \equiv 0\ (\textrm{mod}\ 1024)$ a cutpoint is made, marking the end of the current chunk and beginning of the next one. The hash function is extremely fast to evaluate when the following is known:

The value of the rolling hash function at some window position
The byte entering the window
The byte leaving the window

The issue

Now if I encrypt each chunk and upload it to the server, I already leak some information about the plaintext:

The adversary knows that the hash value (a simple CRC32-like checksum) of the last $w$ bytes of each plaintext chunk $\equiv 0\ (\textrm{mod}\ 1024)$
All the other windows are hashed to a value $\not\equiv 0\ (\textrm{mod}\ 1024)$.

Related

Here is a similar question, but it seems people there did not realize that the hash value (output of the rolling hash function) is never published or known to the attacker. The only information disclosed is whether the hash value $\equiv 0\ (\textrm{mod}\ 1024)$ (true or false) for every window position in the input plaintext stream. So they recommend to use SipHash or $AES(f(w)) \equiv 0\ (\textrm{mod}\ 1024)$, but both solutions are just too slow compared to using the plain rolling hash.

There seem to be similarities with the hash-table flooding attacks, as the hash value is also never directly published. Besides the already-mentioned SipHash, Microsoft has proposed Marvin32 for this particular issue.

Questions

Besides the already mentioned solutions, what is the proper way to perform chunking without leaking information about the plaintext? Performance is very critical here though.
Would UMAC or Universal hashing have any application here?
Would this rolling hash function solve the information leakage on its own without encrypting the hash value with AES/SipHash? If not, what can be done to fix the information leakage? Pseudo-code for this hash function:

// My secret key, never shared or disclosed to anyone
var key = ....;

// Generate substitution table
var substitution = new uint32[256];
var substitutionKey = HMAC(key, SUBSTITUTION_SALT);
for (uint32 i = 0; i <= 255; i++)
{
    var randomBytes = HMAC(substitutionKey, UInt32ToBytes(i));
    substitution[i] = BytesToUInt32(randomBytes);
}

// Generate random irreducible polynomial of degree 33 (GF 2) and store it
// in a 32-bit register (33 coefficients, but the 33rd is implied because
// it's always 1)
// The algorithm is not shown here due to its complexity, but let's assume
// the polynomial is derived from the key
var polynomialKey = HMAC(key, POLYNOMIAL_SALT);
uint32 polynomial = RandomIrreduciblePolynomial33(polynomialKey);

// Hash an input window
uint8[] window = new uint8[48];
LoadPlaintext(ref window);
uint32 hash = 0;
for (uint32 i = 0; i < 48; i++)
{
    // Galois multiplication by x and subsequent reduction
    hash = (hash << 1) ^ ((hash >> 31) * polynomial);
    // Add the substitution polynomial
    hash = hash ^ substitution[window[i]];
}

...

// Now if we want to move the window forward by a single byte, there
// exist a very efficient algorithm that does that, but it's not
// relevant to the issue at hand

UMAC uses AES, so it will not lead to a faster algorithm than the rolling hash + AES solution suggested in the previous question. Universal hashing based MACs like UMAC and Poly1305 usually use a PRF (which you could just use directly) to hide the hash. There are universal hashing MACs that do not, but as far as I know they are even slower. (Further, I am not sure if a secure MAC would even be enough, or if you actually need a PRF.)

Without leaking any more information, there are not many options. Rolling hash + SipHash is probably faster anywhere that you lack AES hardware, but that may be the best you can do.

If you find the performance cost to be unacceptable, you might want to allow some information to leak. For example, if you define chunking using parity(w) = 0 and then PRF(k, f(w)) mod (n / 2) = 0, you halve the number of PRF calls while only leaking one extra bit of information on the window (and even less for those positions where you did not end a chunk).

You can of course reveal even more information to reduce the number of calls further, but in the end you back at something leaks as much as just using f(w) mod n = 0.


What happens to NORX if the same (key, nonce, header data) triple is reused As I understand it, reusing a (key, nonce, header data) triple in NORX leaks

the XOR of the initial common prefix (but this is zero, so only its length is leaked)
the XOR of the first distinct blocks (which is usable by an attacker)

Is this all NORX leaks if misused?

It depends on the attack model. In certain (realistic!) attack models, such as the one used for the BEAST and related attacks on TLS, security breaks down further—it becomes possible to decrypt messages in a byte-by-byte fashion!

This is not specific to NORX; any online authenticated encryption scheme will be vulnerable to the CPSS attack if misused repeatedly, though supposedly "misuse-resistant" modes do not lose security instantly (unlike e.g. AES-GCM). Modes that resist this kind of misuse necessarily need to perform two passes over the message, rendering them offline (i.e., the entire message must be accessible during encryption).


Why is a common reference string needed in zero knowledge proofs? Can we have a non-trivial language without a CRS? Why?

To complement a bit the answer of Occams_Trimmer: a CRS matters strongly for obtaining zero-knowledge proofs with a small number of rounds and for a large class of languages.

Without a CRS and without restriction on the number of rounds, as Occams_Trigger mentioned, we get the class CZK. This is a very large class: under the minimal assumption that one-way functions exist, it is actually equal to the huge class PSPACE. If we limit our attentions to zero-knowledge proofs with an efficient (polynomial time) prover, then it becomes equivalent to NP (i.e., essentially the class of all languages we care about).

However, without a CRS, it is much harder to get a small number of rounds: assuming only one-way functions, we need a superconstant number of rounds to get zero-knowledge proofs for NP. Assuming further the existence of collision-resistant hash functions, we can build five rounds zero-knowledge proofs for NP. This is essentially the best we can hope for: under black-box simulation, a 4-round zero-knowledge proof for NP would collapse the polynomial hierarchy (but there exists some candidate constructions based on exotic assumptions, such as knowledge-of-exponent assumptions or keyless multi-collision resistant hash functions, with non-black-box simulation). Even with non-black-box simulation, a 3-round ZK proof for NP would break indistinguishability obfuscation. Furthermore, 2-round ZK proofs can simply not exist for languages outside BPP.

In contrast, with a CRS, every language in NP has a non-interactive (1-round) zero-knowledge proof, under standard assumptions (e.g. factorization).


Computational feasible to reverse MD5SUM? This might be out of ignorance, I apologize, but how complex of a problem might it be to generate a file of size $N$ whose MD5SUM is $X$?

For example,

ls -l wczasp.rb
-rwxrwxrwx  1 master master     7273877 2011-01-30 17:13 wczasp.rb

md5sum wczasp.rb
acf3602b5eb9a2db3e365d3043682faf  wczasp.rb

So, how computationally hard might be to generate any 7273877-byte file whose 128-bit checksum is also acf3602b5eb9a2db3e365d3043682faf? In a sense, I am asking for a hash collision. My intuition says next to trivial, and nearly as useless too, but I would like to know for sure.

Actually, to the best of our knowledge, it's computationally infeasible.

By the terminology what we use when we discuss cryptographical hash functions, you're not asking for a hash collision (which is "find two different messages that hash to the same value"), but instead you're asking for a hash preimage (which is "for this hash value, find a message that hashes to it").

While MD5 is known to be woefully inadequate when it comes to resistance to hash collisions, there is no known way to find hash preimages that is faster than brute force (that is, hash different message until you stumble across one that happens to hash to the target value).  This brute force approach with MD5 will take $O(2^{128})$ expected operations, and so it is computationally impractical.


Combining AEAD with RSA 'Hybrid' encryption, where we combine symmetric encryption with public-key cryptography, is pretty 'tried and tested'.

To summarise, we generate a symmetric key and encrypt it using RSA. We would encrypt our data using the symmetric, and prefix it with the IV and encrypted key. You therefore need the private key from the RSA keypair to be able to decrypt the symmetric key and then decrypt the data using the symmetric key.

My question is about combining RSA with autheticated encryption, specifically AES in GCM mode. Are there any pitfalls, or any reasons this might be a bad idea?

Is it a good idea to include the IV and RSA-encrypted symmetric key in the additional data (to provide integrity for them), or should they simply be prefixed to the encrypted data?

The main pitfall is possibly thinking that it provides authentication.

The result is still a public key scheme.

It won't help to include the IV in the associated data, since

that is already covered by the authenticated part of AEAD.

Including the RSA-encrypted symmetric key in the associated data would help by making the

resulting hybrid encryption CCA2 secure even if the core public key scheme is only RCCA secure.

RCCA: Relaxing Chosen-Ciphertext Security


Does Salsa20 protect integrity? I was reading about the differences between block ciphers and stream ciphers. One thing that hit me was that stream ciphers like RC4 tend to be susceptible to bit-flipping attacks, in which flipping a bit in the ciphertext can predictably change the plaintext, allowing an attacker who knows the plaintext to change it in any way he/she wants, while in secure block ciphers, an attacker cannot flip a bit in the ciphertext and predictably change the block of plaintext.

How does Salsa20, being a widely used and secure stream cipher, protect against these attacks, if it does at all? If it doesn't, how does Salsa20-Poly1305 protect integrity of known plaintext?

Salsa20 alone does not protect integrity.

Poly1305 protects integrity, as it is a Message Authentication Code (MAC). A MAC takes a secret key and a message, and outputs an authentication tag. Any change to the message will cause the resulting tag to not match. Only someone with the key can generate the tag, which means that an attacker shouldn't be able to flip bits undetected.

At a very high level, Poly1305 takes a message and a two-part key and turns it into a very big polynomial (modulo a large prime).

$MAC=(m_{1}r^{n}+m_{2}r^{n-1}\ldots+m_{n}r^{1}+k)\mod p$, where $m_1$, $m_2$, etc, are blocks of the message and r & k are the key.

In the case of Poly1305 the prime p is $2^{130}-5$.

To encode a message $M$ into blocks you take 16 bytes from the message, append a 1 byte to the end, then treat the 17 bytes as a little-endian number (this process ensures that trailing zeroes are detected).

There are also some restrictions on how $r$ is chosen.

The end result is very difficult to compute by an attacker not knowing r and k, even if they know the plaintext of the message.

Loup Valliant has a good explanation with a bit more detail on how Poly1305 actually works.1 And of course DJB's paper provides even more detail, though it's harder to understand.2


Do identical strings always have the same SHA-256 value? If you hash a string using SHA-256 on your computer, and I hash the same string using SHA-256 on my computer, will we generate the same value? Does the algorithm depend on a seed (so we'd both need the same seed) or some other such parameter?

edit:
To clarify, by 'string' I meant 'the same byte input', which as the comments and @ispiro's answer point out, may be different for the same character string depending on the encoding.

Yes, if you hash the same input with the same function, you will always get the same result.

This follows from the fact that it is a hash-function. By definition a function is a relation between a set of inputs and a set of permissible outputs with the property that each input is related to exactly one output.

In practice there is no seed involved in evaluating a hash-function.

Now, this is how things work in practice.
On the theoretical side of things, we often talk about families of hash-functions. In that case there does exist a key that selects which member of the family we are using. The reason for this is a technical problem with the definition of collision resistance.

The naive definition of collision resistance for a single hash function $H : \{0,1\}^* \to \{0,1\}^n$ would be that for all efficient algorithms $\mathcal{A}$ the following probability is negligible $$\Pr[(x_1,x_2)\gets\mathcal{A}(1^n): H(x_1)=H(x_2)]$$

The problem with that is, that it is impossible to achieve. Given that $H$ is compressing, collisions necessarily exist. So an algorithm $\mathcal{A}$ that simply has one of those collision hardcoded and outputs it, has
$$\Pr[(x_1,x_2)\gets\mathcal{A}(1^n): H(x_1)=H(x_2)] = 1.$$
So the definition is not achievable, since this $\mathcal{A}$ by definition exists even though nobody might know what it is.

To solve this problem, we define collision resistance for a family of hash-functions $\{H_k : \{0,1\}^* \to \{0,1\}^n\}_k$.
We then define that such a family is collision resistant if it holds that the following probability is negligible
$$\Pr_{k\gets\{0,1\}^n}[(x_1,x_2)\gets\mathcal{A}(k): H_k(x_1)=H_k(x_2)].$$

Here we do not run into the same problem, because the exact function $\mathcal{A}$ needs to find a collision for is chosen uniformly at random from an exponentially large family. Since $\mathcal{A}$ could have hardcoded collisions for at most a polynomial number of functions in the family, such hash-function families are not trivially impossible.

Note that this means that there somewhat of a disconnect between the theoretical treatment of hash-functions and their practical use.


RSA and ECDSA Certificate Sizes Is there a table (or a whitepaper from official sources) that compares the size of X509 certificates generated with RSA (starting from 1024 bits) and ECDSA (starting from 160 bits) ? Thanks for the support.

Building such a table would be very difficult, because certificate-sizes depend on a lot of (variable-sized) things, including but not limited to:

usage constraints
signatures
public keys
URLs to CRLs and OCSP-servers
Name, location and other identifiers of the key-holder
Name, location and other identifiers of the issuing CA

However, you can estimate the difference between a pure ECC certificate and a pure RSA certificate yourself using simple math.

The relevant properties here are the public keys, the signatures and the signature algorithms. Let's assume that the signature algorithm identifiers are equally large in both cases (e.g. it's a simple OID or an integer).

Now we need to figure out the public key sizes. But this is easy as a public RSA key usually consists of the pair $(n,e)$ of which the lengths are known. Usually $e$ is 2-3 bytes long and $n$ is roughly 2048/8=256 bytes long. Now add these sizes together and ignore the structural ASN.1 encoding overhead and we get roughly 260 bytes of public key of the key-holder for RSA. RSA signatures are as long as the modulus so that's another 256 bytes coming from the CA. So in sum we're at about 520 bytes for RSA.

For ECC, the public key consists of one point, of which we only need the x-coordinate and an additional byte and an identifier identifying the used (standardized) curve. The curve point usually is as large as the curve modulus, e.g. 256/8=32 byte with one extra byte to encode the compression type. The OID is about 9 bytes long. An ECDSA signature by itself consists of two points, so that's another 66 bytes. Summing up you end up at about 110 bytes with ECDSA.

Similar calculations can be done for the security parameters of your choice.


What is a (smooth) projective hash function? I recently came across the term "smooth projective hash function", and I see that there are many constructions nowadays that rely on them, especially some PAKE constructions. But, I didn't exactly understand them. What are they? And why are they so useful?

Smooth projective hash functions have been introduced by Cramer and Shoup under the name hash proof systems. An SPHF for a language $L$ allows to hash a word $x$, in two different ways: either with some secret key (the hashing key, usually denoted $\mathsf{hk}$) or with the associated public key (the projection key, usually denoted $\mathsf{hp}$). It must satisfies two properties:

If the word $x$ is in the language, both ways of hashing will return the same hash value
If the word $x$ is outside the language, the hash obtained with the secret key is statistically indistinguishable from random, even given the public key

Intuitively, this can be used as a kind of designated-verifier zero-knowledge proof (although it does not satisfy the classical zero-knowledge property): to prove the $x \in L$, the prover receives the projection key $\mathsf{hp}$ from the verifier, and hashes the word with respect to $L$, using $\mathsf{hp}$, and sends back the result. The verifier compares it to the hash obtained with the secret key and accepts the proof if both hashes are the same.


Is it possible to perform CPA(Correlation Power Analysis) when attacker has only specific round's waveform? I read Quite a lot document about breaking AES using CPA.

But most of them, assuming that attacker has the first or last round of the waveform(trace) and exploit SubBytes.

My question is if the AES-128 (or AES-256) can be attacked even if attacker has only a certain round of waveform, not the first and last.

Even if attacker has the multiple pairs of plaintext and ciphertext, Is it impossible to figure out the encryption key using only a specific round's waveform?

Yes, in general you can perform a key-recovery DPA attack on certain inner rounds of AES. Most of the attacks in public literature target leakage from first or last rounds (the outer rounds) after a highly non-linear operation (such as SubBytes) just for convenience. This attack is very easy to implement. Exploiting leakage from inner rounds becomes a bit trickier and slightly more cumbersome to implement, but it's certainly possible for the second round of AES (or second to last) and further in DES.

Let's recap a bit. One main ingredient of DPA attacks is divide and conquer. Say we are targeting AES-128. We essentially chop one intractable problem (performing key recovery on 128 bits) into 16 much smaller and attainable problems (16x 8-bit DPAs that recover each byte of the first or last round subkey). The DPA attack itself is basically comparing predictions for leakage when handling an intermediate $V$ against actual measurements. A vanilla DPA targets leakage from an intermediate $V_i=F(X_i, K_i)$ that is a function of:

data $X_i$ that the DPA practitioner knows (such as a portion of the plaintext or ciphertext), and
a portion $K_i$ of the (unknown) subkey. The main condition on $K_i$ is that the DPA practitioner can efficiently go over every possible value of $K_i$. This ensures the running time of the DPA attack stays manageable and the whole attack is practical.

Now we can see the reason we find DPA attacks on outer rounds easier: there are plenty of intermediates $V$ that satisfy these two conditions. In your example, the output of SubBytes makes an excellent choice: the practitioner needs to enumerate just $2^8$ subkeys. (There are other additional, unrelated reasons that make this a good choice; namely, it's the output of a highly non-linear operation, which helps in the process of weeding out wrong subkey hypothesis, but this is not important now.)

Note if we chose an intermediate $V$ that depends on too many key bits (in a way that the condition on $K_i$ above does not hold), then the DPA attack would just take too much time and not be practical, or even pose an advantage over plain cryptanalysis (including brute force).

Back to the original question, you can find intermediates in the second round in AES that satisfy these two properties. For example, a very, very naive attack could target the SubBytes output of the second round. The attack needs to enumerate $2^{40}$ keys. This is certainly a much heavier computation than $2^8$, but not the end of the world.

This hassle can be circumvented if the practitioner can deactivate portions of input texts by fixing them to a constant value. Say we're targeting an intermediate $V$ that is the xor of four S-box outputs: $V=S(P_1 + K_1) + S(P_2 + K_2) + S(P_3 + K_3) + S(P_4 + K_4)$. Naively, this would mean that we've to enumerate $2^{4w}$ $w$-bit subkeys to jointly recover $(K_1,K_2,K_3,K_4)$. If we fix $P_2$, $P_3$ and $P_4$ to constant values, the intermediate $V$ can be rewritten as $V=S(P_1 + K_1) + c$ for some unknown constant $c$. We can perform the DPA on the "key hypothesis" $(K_1, c)$ taking $2^{2w}$ effort (and then repeat to recover $K_2$, and so on). Overall this takes roughly $2^{2w+2}$ time, less than jointly recovering all subkeys. (I've oversimplified a bit for the sake of the explanation, but you can find intermediates in AES where this technique applies.)

From here, there are other tricks you can use to target inner rounds. They are slightly more complicated and combine DPA with more traditional symmetric cryptanalysis. Although they are described in a very narrow and specific setting, usually they can be ported to different algorithms or scenarios. Here are some examples:

Handschuh and Preneel give in Blind Differential Cryptanalysis for Enhanced Power Attacks a differential attack assisted by side-channel information to exploit the third or fourth round of DES under a certain leakage model.
Collision attacks can also exploit leakage from inner rounds. An example is Enhancing Collision Attacks by Ledig, Muller and Vallete or Two New Techniques of Side-Channel Cryptanalysis by Biryukov and Khovratovich.
Here is a DPA attack that targets the third round of DES without requiring collisions by Gierlichs and yours truly. This attack uses DPA with a regular model and a cheap regular differential cryptanalysis step. This one is probably easier to follow than the others in this list.


Decrypt AES-128 with key file but missing IV? I want to decrypt a file that has been encrypted using AES-128 in CBC mode using OpenSSL. I got the “.key” file – which is 32 digits – but when I try to decrypt with OpenSSL, the program asks me for “-iv” and I don't know the IV of that file so it won't decrypt. Is there is any other way to decrypt the file without knowing the IV?

I tried with another file of which I have the correspondent IV and it works, and when I don't supply that IV, the decryption fails too.

By the way: is there anyway to know what type of encryption was used to encrypt a file?

First of all, I suggest you to try use as IV first 16 bytes of encrypted file.
Because in general IV is the first block of ciphertext.

But if that doesn't work, then – of course – you can decrypt all message except first block.
Just use first block as IV, and start to decrypt from second block. That will work because CBC does not provide integrity, and you can decrypt parts of the message picking any part of the ciphertext.

To better understand how this works, I also suggest you to read about CBC.


Real world use cases of Multi-Party Computation Most of the research papers give imaginary applications of multi-party computation.

Either they talk about Yao's millionares' problem or two or more corporates willing to compute some intrustion detection stuff collectively on their private data without revealing their network logs or similar.

In reality, what are the practical use cases for multi-party computation?

Sharemind is trying to achieve cloud privacy of data computations (of single party) by distributing to multiple cloud servers but here there are no multiple parties as such.

While Homomorphic encryption is touted as special case of SMC, but its still single party outsourcing computations.

As I mentioned in a comment, a relatively new application of multi-party computation is its use as a countermeasure against (mainly hardware) side-channel attacks. In particular, there is a method called "threshold implementations" which is based on a form of secret sharing.

A relevant reference would be the paper Secure Hardware Implementations of Nonlinear Functions in the Presence of Glitches by S. Nikova, V. Rijmen and M. Schläffer.
Extensions to higher-order DPA attacks have also been proposed.

Let's say you wish to securely implement a Boolean function $f$ with $n$ input bits. The (secret) input $x = (x_1, \ldots, x_n)$ is then "shared" by (randomly) choosing additive shares $x_{i, j}$ such that

$$x_i = \bigoplus_{j = 1}^{s_{in}}x_{i, j}.$$

I'll write $\mathbf{x} = (x_{1, 1}, x_{1, 2}, \ldots, x_{1, s_{in}}, x_{2, 1}, \ldots, x_{n, s_{in}})$ for convenience below.

The idea is then to share $f$ too, in such a way that for all inputs $x$ and correct sharings $\mathbf{x}$

$$f(x) = \bigoplus_{i = 1}^{s_{out}} f_i (\mathbf{x}).$$

This is called the correctness property.
We now also require that $f_i$ is independent of every $i$th share of $x$. So each $f_i$ actually operates on $n(s_{in} - 1)$ rather than $ns_{in}$ inputs. This is called the non-completeness property.

Under the non-completeness assumption, the paper shows that if $x$ is shared with independent uniformly chosen shares, then $f_i$ (as well as any intermediate result) is independent of the input shares $x_{k, i}$ with $k = 1, \ldots, n$.
This then leads to pipelined implementations which are secure against first-order (i.e. using first-order statistical moments) side-channel attacks. For more details, take a look at the paper (or other papers on the same subject).