How is the Lai-Massey scheme invertible? The Wikipedia page on the subject and other descriptions that I can find of it are as clear as mud. $L$ and $R$ are combined to make a number that is then added to both. That seems like a loss of information to me.

One Lai-Massey round can be described as
$$
\begin{align}
L' &= \sigma(L \oplus F_k(L \oplus R)) \\
R' &= R \oplus F_k(L \oplus R)\,,
\end{align}
$$
where $F_k$ is some round function—not necessarily invertible—and $\sigma(\cdot)$ is an orthomorphism, an arbitrary function such that both $\sigma(x)$ and $\sigma'(x) = \sigma(x) \oplus x$ are invertible.

To invert this,
$$
\begin{align}
L &= \sigma^{-1}(L') \oplus F_k(\sigma^{-1}(L') \oplus R') \\
R &= R' \oplus F_k(\sigma^{-1}(L') \oplus R')\,.
\end{align}
$$
We can see this works because
$$
\begin{align}
\sigma^{-1}(L') &=
L \oplus F_k(L \oplus R)\,,
\end{align}
$$
and
$$
\begin{align}
\sigma^{-1}(L') \oplus R' &=
L \oplus F_k(L \oplus R) \oplus R \oplus F_k(L \oplus R) \\
&= L \oplus R\,.
\end{align}
$$


What is the difference between PRF and a Random Oracle? What is the difference between Pseudo Random Functions and Random Oracles?

Is the difference only about the domain of PRFs and Random Oracles, former having a fixed domain and latter can act on any input as long as it is well formatted?
Having a Random Oracle is a stronger assumption, why is that?

$\newcommand{\str}[1]{\{0,1\}^{#1}}$

Roughly speaking, a pseudo-random function is to a random oracle what computational encryption scheme is to one-time pad -- the former is a computational analogue of the information theoretic latter.

For simplicity, let's fix the domain and co-domain to be the set of all $n$-bit strings. Let's consider the set $\mathcal{F}_n$ of all functions that map $n$ bits to $n$ bits, i.e.,
  $$\mathcal{F}_n=\left\{f:\str{n}\rightarrow\str{n}\right\}.$$
A random oracle on $n$ bits is a function sampled uniformly at random from $\mathcal{F}_n$ that is presented as an oracle. That is, any machine that has access to the random oracle can (by writing on its oracle tape) query it on inputs and will receive the value of the function in return (written back on the oracle tape).
Note that since there are $|\mathcal{F}_n|=(2^n)^{2^n}$ such functions, the probability that a particular $f\in\mathcal{F}$ is chosen is $1/|\mathcal{F}_n|$. Moreover, as it is picked uniformly at random, a random oracle is incompressible and the only way to explicitly represent it is via its function table (which has a size of $n2^n$ bits). (This is why it is presented as an oracle.)

A pseudorandom function, on the other hand, is a family of functions that "appear" random to a computationally bounded machine. More formally, it is a family of explicit, efficiently-computable keyed functions on $n$-bit strings
  $$\mathcal{G}_n=\{g_k:\str{n}\rightarrow\str{n}\}_{k\in\str{n}}$$
that is pseudo-random: for any computationally bounded machine the worlds with  oracles
$$f(\cdot):f\leftarrow\mathcal{F}_n ~~(\text{random})$$
and
$$g_k(\cdot):g_k\leftarrow\mathcal{G}_n\stackrel{\Delta}{=}k\leftarrow\str{n}~~(\text{real})$$
appear indistinguishable. In other words, it is indistinguishable from a random oracle for computationally-bounded machines. Note that $\mathcal{G}_n\subset\mathcal{F}_n$ and, more importantly, the number of functions in $\mathcal{G}_n$ is much smaller than that in $\mathcal{F}_n$: $$|\mathcal{G}_n|=2^n\ll|\mathcal{F}_n|=(2^n)^{2^n}$$
However, by pseudo-randomness, a computationally-bounded machine should not be able to tell this.

The advantage of using pseudo-random functions instead of random functions is that they have a succinct representation: once the family $\mathcal{G}_n$ (which we require to be explicit and efficiently-computable) is fixed the function is represented by the key $k$ and therefore its explicit representation is simply $n$ bits long.

Now, to answer the questions

  Is the difference only about the domain of PRFs and Random Oracles,
  former having a fixed domain and latter can act on any input as long
  as it is well formatted?

Not necessarily, one usually talks about an ensemble of PRFs, that is one for every bit length: $\{\mathcal{G}_n\}_{n\in\mathbb{N}}$.

  Having a Random Oracle is a stronger assumption, why is that?

That question can be interpreted in different ways. Assuming an object $B$ is said to be stronger than assuming another object $A$ if $B$ implies $A$ (but the other direction does not hold or is unknown). For example, DDH is a stronger assumption than CDH, or IND-CCA is a stronger assumption than IND-CPA. In this sense, it is not possible to directly compare a random oracle to a PRF since the former lives in a relativised world (i.e., a world with oracles), whereas the latter need not. It unlikely that a construction of PRF from random oracle could be explicitly and succinctly described (as @Ievgeni points out) because of the incompressibility of the random oracle. On the other hand, one could talk about simulating a random oracle using a PRF -- however, to an unbounded adversary this would appear distinguishable.

That said, a protocol that is based on a PRF is preferred to one that is based on random oracles since in practice we do not know how to instantiate random oracles. One could replace it with a concrete hash function like SHA3 (i.e., the random-oracle methodology), but this protocol only has heuristic guarantees (discussions here and here) and in some cases known to be insecure (discussion here). However we do know how to (explicitly) construct pseudo-random functions from the mild assumption that one-way functions exist (discussion here).


How is public-key cryptography secure? Quite strange question, but here goes:

I don't quite understand how asymmetric encryption works. Take SSH for an example: The server will always be listening for commands, so anyone who has the public key (easily obtained as I understand (I might be wrong)) can send commands to the server and it would appear as if the correct client had sent them? I know there must be a catch but I can't seem to figure it out. Even if SSH used symmetric keys, the exchange of those keys uses asymmetric keys so a man-in-the-middle could tell the server it's password instead of the real one?

Sorry if this is a little rambley, it's quite hard for me to explain.

Thanks in advance.

Take SSH for an example: The server will always be listening for commands, so anyone who has the public key (easily obtained as I understand (I might be wrong)) can send commands to the server and it would appear as if the correct client had sent them?

You are confused indeed, but you are drawing a strictly correct inference here: the server's public key is of no use for the server to tell authorized clients apart from attackers. But it's not meant to do that; the server public key is meant to provide two things:

Allow the client to authenticate the server (so that an attacker can't impersonate the server);
Allow the client to bootstrap an encrypted channel with the server.

So what follows is that, in addition to its public key, the server needs some other mechanism to authenticate the clients.  The most common ones are familiar:

The server asks the client for a username and password
The user has their own public key registered with their account in the server (in most implementations, in their ~/.ssh/authorized_keys), and the client and server execute a challenge-response protocol to allow the client to prove they possess the corresponding private key.


EdDSA Signature Algorithm - hash of secret key Why does EdDSA use the (SHA-512) hash of the secret key as the exponent for the public key rather than using the secret key value directly? This seems inefficient, and I can't see how it adds any extra security.

Ed25519 needs two secret values:

The private scalar (~256 bits)
A hash prefix used derive a secret nonce from the message (256 bits)

Using the same value for these is bad style, as is deriving one of them from the other. You could also use their concatenation as private key, but that'd double its size to 512 bits. So Ed25519 chose the clean solution of deriving both from a 256 bit master secret.


SHA256 output to 1-6 number range? I want to calculate a random number (1 to 6) from the output of sha256. Can I assurance the probability of 6 abilities is the same?

The approximate way

You don't need to be perfectly even if you can make the unevenness small enough to be undetectable. So you can realistically do this: take the first 128 bits (16 bytes) from the SHA-256 output (or more, if you like), read them in as an unsigned bignum (arbitrary precision integer) using your library of choice, take the remainder modulo 6, and add one. The distribution will not be even—1 will be very slightly more likely than 6—but not distinguishable in practice from an even distribution.  The probability of picking 1 is:

$$
{\lfloor 2^{128} \div 6 \rfloor + 1 \over{2^{128}}}
$$

...which Wolfram Alpha tells me is about:

$$
0.166666666666666666666666666666666666667646245292351906256...
$$

And the probability of picking 6 is:

$$
{\lfloor 2^{128} \div 6 \rfloor \over{2^{128}}}
$$

...which is about this much:

$$
0.166666666666666666666666666666666666664707509415296187486...
$$

These values are only $2^{-128}$ apart, as you can tell algebraically from the expressions above. Good enough for cryptographic purposes.

NIST Special Publication 800-185 (SHA-3 Derived Functions) recommends a similar method for hashing with SHAKE or other variable length output functions into an arbitrary integer range. SP 800-90Ar1 (Recommendation for Random Number Generation Using
Deterministic Random Bit Generators), in Section A.5.3, recommends this method as well.

The exact way

Looping over the unsigned bytes in the SHA-256 result byte array, at each step:

If result[i] % 8 is less than six, return (result[i] % 8) + 1;
Otherwise, if (result[i] >> 3) % 8 is less than six, return ((result[i] >> 3) % 8) + 1;
Otherwise, continue on to the next iteration of the loop;
If you looped through the whole thing, be very suspicious you did something wrong, and if you didn't (!) assign result := sha256(result) and try again from the top.

Whatever number is returned, it is equally likely as all the other five.

On any given iteration, the chance that iteration will return is 75%, so with 64 attempts, the probability that none of them will return is $(1 - 0.75)^{64} = (2^{-2})^{64} = 2^{-128}$. And if that happens you hit step #4.


What is an oracle adversary? I'm trying to figure out block ciphers and this is the first time I've encountered the term "oracle adversary". It appears in the context of defining a PRP and a PRF. Can someone please explain what an "oracle adversary" can/cannot do? Or maybe help out with a link or something (I've tried looking it up myself, but I could only find the RSA Laboratories RSAES-OAEP Dictionary, which doesn't really clear things up).

Here's the context:

  (Pseudo-Random Function). A family of functions F : {0, 1}^k × {0, 1}^n → {0, 1}^n is pseudo-random if for all polynomial time oracle adversaries $A$, $$
\left|
\Pr_{K} \left[ A^{F_K(\cdot)} = 1 \right] -
\Pr_{R:\{0,1\}^k \rightarrow \{0,1\}^n} \left[ A^{R(\cdot)} = 1 \right]
\right|
$$ is negligible.

This is a common abstraction throughout theoretical crypto that is borrowed from complexity theory.  It is a formalization of the idea that an adversary is only allowed to attack a primitive (PRF, PRP, etc.) by observing its "input/output behavior."

Formally, adversaries are (often implicitly) thought of as Turing machines, circuit families, or whatever formal model of computation you like.  And when we say that an adversary is given "oracle access" to, say, $F_K(\cdot)$, we mean that it has a special state that it can enter, where it provides some $x$ and then obtains $F_K(x)$.  Note that the adversary is given complete freedom to choose the $x$: It can repeat the same $x$, query at random $x$, or choose the $x$ with some structure.

You can formalize this with Turing machines by having a special oracle tape and state that "magically" overwrites $x$ with $F_K(x)$, or with circuit families you can think of these queries as special $F_K$-gates, or if your adversary is expressed in the C programming language then it could have the ability to call a function from a library that
computes $F_K(\cdot)$.  The details of the formalization are rarely important to crypto.

Beware the subtlety where in definitions like PRF security, the adversary always "knows" the $F$ that it is attacking, due to the order of quantifiers.  In those definitions, the adversary is given input/output access to a function that is either $F_K(\cdot)$ (for a "known" $F$ but "unknown" random key $K$), or to an "unknown" random function with the same
domain and range.


Why does TinyJAMBU-128 claim only 112-bit security? I am trying to understand the security level of TinyJAMBU-128.
As shown in Table 4.1 page 12 of this document, TinyJAMBU-128 claims 112-bit security. However, it has a 128-bit key. How have we lost 16 bits of key? What is the obvious attack that has $2^{112}$ time complexity?

I believe this is simply a statement of the intention to meet the submission requirements set out by NIST for lightweight ciphers.  Note that the paper linked in the question refers to "security goals".
As per section 3.1:

An AEAD algorithm shall not specify key lengths that are smaller than 128 bits. Cryptanalytic attacks on the AEAD algorithm shall require at least ${2}^{112}$ computations on a classical computer in a single-key setting. If a key size larger than 128 bits is supported, it is recommended that at least one recommended parameter set has a key size of 256 bits, and that its resistance against cryptanalytical attacks is at least $2^{224}$ computations on a classical computer in a single-key setting.

Note that these are the final submission requirements from 2018.  It seems the figure for 192-bit is deduced from the requirements for 256 bit, or is perhaps referencing earlier requirements.


What's the difficulty of using elliptic curves to design homomorphic encryption protocols? I have recently been very interested in elliptic curves because they are a powerful tool in crypto, ECC, pairing, etc. However, it seems that elliptic curves are not popular in homomorphic encryption. I understand that lattice-based crypto is currently the only way to construct FHE, like LWE. Elliptic curves can only be used to construct PHE; for example, BGN. After doing some research as a freshman in HE, I found that there is not much effort in trying to use EC to construct FE. So, I'm just wondering why. Is it because elliptic curves have some issues in their structure, making it hard to construct HE? Or is it because lattice-based construction is a hot topic, so researchers prefer it over EC?

From my point of view, Homomorphism is a inherent attribute of certain lattice-based scheme.Researchers try every means of solution to enhance the attribute,but not all primitives have this attribute.


Is openssl rand command cryptographically secure? I'm wondering if the openssl rand command produces cryptographically secure random bytes. For example when in need for a random password or token:

openssl rand -hex 32

The man page unfortunately does neither state it's cryptographically secure, nor that it's not.

On the one hand, I think this is openssl, its sole purpose is to do cryptography. On the other hand, the man page states something about reading and writing seed data instead of directly querying a CSPRNG.

So it is somewhat unclear for the end user. Does someone know?

Yes, it is cryptographically secure, pseudo random output, seeded by retrieving secure random data from the operating system.

If it is random or not depends on the fact if the OS RNG is random. This is usually the case on normal desktops,  but you'd better be sure for e.g. limited embedded systems. If no truly random data can be retrieved  - according to RAND_bytes - then rand will exit with an error.

Added note: Of course you are dependent on the implementation. Famously OpenSSL was broken for Debian because a maintainer ran a program to find memory errors and disabled all entropy sources rather than the one that was (deliberately) failing the property that no uninitialized memory should be used. So it is of importance to review security reports and keep your system up-to-date / on long term support.

Any random source that you add using -rand [file][:file]* is used as additional seed data - in other words, the output will always be random, even if you supply the same seed.

As the pseudo random generator provided by OpenSSL generally runs in the application space on the main thread, it may be faster than asking a lot of data from /dev/urandom. But to be honest, most of the time using /dev/urandom suffices (and current implementations are pretty fast as well).

You can see that it is random when you look at the link to the RAND_bytes manual page which is the function that lies behind command line rand and is linked to from the manual page (in the "see also section, but yeah"):

  RAND_bytes() puts num cryptographically strong pseudo-random bytes into buf. An error occurs if the PRNG has not been seeded with enough randomness to ensure an unpredictable byte sequence.

That RAND_bytes() is used can be found in the source file for the rand command, rand.c, so yes, this is indeed the function that is called.


Meaning of entropy of a bitstring in NIST SP 800 - 90A From NIST SP 800 - 90A from January 2012 (see http://csrc.nist.gov/publications/nistpubs/800-90A/SP800-90A.pdf), page 6:

  For the purposes of this Recommendation, an n-bit string is said to have
  full entropy if that bit string is estimated to contain at least
  $(1-\epsilon) n$ bits of entropy, where $0 <= \epsilon <= 2^{-64}$.

My understanding of entropy is that entropy is a property of the probability distribution of a source of bit strings, and not a property of a single bit string.

So what is NIST specifying here? Is there a way to estimate the entropy of the underlying source, given a bit string produced by that source? Maybe statistical tests, like Maurer's universal test? This could only be probabilistic since in principle, a true source of randomness can create any bit string...

"Entropy" is more accurately defined, in cryptography, as "that which the attacker does not know". For instance, suppose that every day you take all rates at the closure of the New York stock exchange, and hash them with SHA-256. The resulting value is very unpredictable (otherwise you could become very rich), so, from a "physics" point of view, there is a lot of entropy here. However, once the rates are published, everybody knows them: thus, from a cryptographic point of view, the entropy is nil.

To estimate the entropy, you have to analyze the process that generates the purportedly random value, and imagine an attacker trying to guess that value: the attacker has access to a validation box that returns "true" if the attacker found exactly the value, and "false" otherwise. You may say that the process yields "$n$ bits of entropy" if, on average, the attacker must invoke the validation box $2^{n-1}$ times before hitting the right value.

The important point here is that the estimate can come only from an analysis of the generation process. It cannot be tested with statistics, because statistics do not capture the level of knowledge of the attacker.


detecting ROT13/base64 encryption Is there anyway to detect that a cipher is encrypted with ROT13 Or Base64 without decrypting it using the algorithm and check that the result means (works)?
I mean does an algorithm exists that test the cipher and tell YES it is ROT13/Base64 (or NO it isn't)?

Thanks

Without using ROT13 explicitly, it can be done. You can draw up a frequency histogram of the text, and then shift it 13 characters left (or right). If it lines up to give the average English frequency distribution, it's likely this is ROT13 material. This will only work well if you have a large enough sample, obviously.

You should be able to do roughly the same thing with Base64, since it too preserves frequencies to some extent (though in a less obvious way, as the encoding works at the bit level, not on each character)

Though for Base64 a more intelligent approach is to just decode the whole thing and check that it looks like english (or whatever format you expect, really) either by frequency analysis or another method. It would be much faster and easier, but according to your question this is not a valid approach, so...

Nitpick: neither ROT13 nor Base64 use a cryptographic key, so they are not ciphers, but encodings (at least Base64 is - ROT13 tries to be a cipher, and could be called one, I suppose, but it's not technically correct).


Including the next random One Time Pad as part of the encoded message? I've tried to do something very simple here, which is to encrypt a message with a one-time-pad (OTP) and include the next OTP as part of that same encrypted message. i.e. The first message consists of the actual text of the message and then the next OTP added to the end. The length of the OTP should always stay the same, so I did some simple bit manipulation to squeeze more than one character into a byte. So that means that every succesive OTP will be the same length as the original OTP.

My main question: Is the fact that the next OTP is included at a known location in every encoded message a factor that will allow decryption of the messages given a few encrypted messages? Or will it be as secure as a normal OTP?

Is the fact that the next OTP is included at a known location in every encoded message a factor that will allow decryption of the messages given a few encrypted messages? Or will it be as secure as a normal OTP?

Yes, that's a big problem.

You're practically transporting the (next) OTP you're adding at the end of your ciphertext in the open. Differently put: you're sharing the (next) secret unprotected and in plain sight of any potential attacker.

This is especially true when assuming we – as we usually do – respect Kerckhoffs’ principles. The attacker would know that you’re adding the next OTP to the end of the current ciphertext, and can therefore extract the next secret easily.

Even when we wouldn’t respect Kerckhoffs’ principles and keep your construction secret, it wouldn’t be too hard for an attacker who intercepted merely 2 transmissions to grasp what you’re doing… which includes that the attacker also gains the bonus of being able to simply decrypt that 2nd intercepted message, and also gaining knowledge of the next OTP you’re going to use for transmission number 3. That’s definitely not what you want…

OTP security claims

You’re somewhat violating the definition of OTP (points 2, 3, and maybe 4):

  Per definition, OTP requires the “key“ to be…

  a truly random one-time pad value,
  generated and exchanged in a secure way.
  at least as long as the message, and
  only to be used once.

I’ll leave it up to personal opinion if your idea aditionally violates point 4, as that depends a bit on the individual point of view. While others might disagree, I personally see something which might be interpreted as reuse.

In the end, that doesn’t reall matter because violating points 2 and 3 is already more than enough to say that the usual OTP security claims are in no way applicable when looking at your construction.

Other problems related to your construction

Please note we’re not yet talking about potential authentication issues – for example: you need to think about an attacker intercepting your messages, modifying them, and then forwarding them without you being able to detect the modification. In most scenarios, this is disastrous. Fact is, OTP itself doesn’t handle authentication by nature… that’s where MACs come in.

TL;DR:

Never, ever share/transmit a secret (here: next key) in an unprotected manner.
Always think about authentication, because simply encrypting something doesn’t mean it’s safe from being forged. You should – at least – be able to detect message forgery.

EDIT

This edit include the comments posted to this answer, to make the answer more complete and to safeguard the infos contained so they don't vanish when comments get cleaned up (aka deleted).

  OP: Hi e-sushi, thx for your detailed answer. I think perhaps you're misunderstanding. I'm not including the next OTP at the end of the cypher text, but as part of the cypher text. So basically I'm doing what Daniel described: "...  padding the ends of messages with random data, encrypting (message + random), then decrypting and collecting the random data at the end, and using this later as another one time pad ...". The first pad will be exchanged in a secure way of course and all subsequent "compressed" pads will be the same length as the message. Yep, will still get to MAC thx :-)

  ME: Same problem… as you're including the next OTP with the current message. So, xorring the 2nd half of message 1 with the first half of message 2 will reveal the key you included in message 1… which allows decryption of the first half of message 2.

  ME: In the end, you’re having a chicken-and-egg problem (better pidgeon hole problem) there. OTP key should be 100% length of plaintext. So, you can’t add plaintext to your “next OTP“ as that would not be OTP anymore. The only solution is that you do bit fiddling which would overlap and boils down to a double-XOR… $(m \oplus nextOTP)  \oplus currentOTP)$. There’s no way to create an OTP  going $(m | nextOTP) \oplus currentOTP$ because $nextOTP$ and $currentOTP$ MUST have the same length. Otherwise you wouldn’t be able to transmit that next OTP. Even in an optimal case, each transmission would halve the space available to transmit the next key material.

  OP: Aha, okay I see, so it's leads to the same problem as re-use of an OTP. Oh well, I thought maybe it was a nice way to get new pads distributed. Never role one's own encryption, lol. The best is just to include info of where to get the next pad in the message, or use a book, or some stream of random data seeded with a random key perhaps.

  ME: @Sci Yep, which is why I mentioned that “ While others might disagree, I personally see something which might be interpreted as reuse.“ in my answer. ;) Indeed, including a hint (on the location where to find the next OTP) in your plaintext message seems more logic as it voids the issue. Related to adding a MAC to the whole thing just to make it safer and more complete – simplest would probably be a HMAC (hash-based MAC). Please see Should we MAC-then-encrypt or encrypt-then-MAC?. It's not difficult to add but you need to do it correctly.

EDIT 2

Last but not least, @tylo's comment completes it:

  I think this answer has most of the essentials, but there is one misconception, which is not adressed yet: Due to the Kolomogorov complexity a real one-time-pad can not be compressed on average. And using a "compressible OTP" would not be truly random and uniform.


Coefficients of Elliptic Curve over Finite Fields When talking about elliptic curve over finite fields in ECC, we often assume that the elliptic curve can be written in the Weierstrass form

$$y^2=x^3+Ax+B, \quad A,B\in \mathbb{F}_q$$.

where $\mathbb{F}_q$ is a field of characteristic not $2$ and $3$. (For example, Schoof's algorithm to compute $\#E(\mathbb{F}_q)$ assumes this. )

In practice, would $A$ and $B$ ever be non-integer coefficients(suppose we are working over $q=p^n$)? That is to say $A=\underbrace{1+...+1}_{\text{sum of }1}$ or might we pick $A,B$ to be other elements from $\mathbb{F}_q$?
How would these algorithms that assume the Weierstrass model, generalize to say elliptic curves over fields of characteristic $2$ or $3$? For example, Koblitz curves are a class of elliptic curves of the form $y^2+xy=x^3+ax+1$ in $\mathbb{F}_{2^m}$?

$A$ and $B$ can be non-integers if you're working with an extension field. For example, this happens with pairing-friendly curves where you need to work with elliptic curves over e.g. $\mathbb{F}_{p^2}$.
Depends on the algorithm. For counting elliptic curve points, the "hard" part is computing $\#E(\mathbb{F}_p)$. If you compute that, than it's easy to compute $\#E(\mathbb{F}_{p^k})$; see this answer. In the Koblitz curve case it's even easier since computing $\#E(\mathbb{F}_{2})$ is trivial (it's either 2 or 4 depending on the curve).


Using an RSA private key simultanously as an AES encryption key to generate random numbers? Currently I'm implementing a PRNG for an embedded system. Using the RFC 4086 I've decided to use the X9.17 - to be more specific the successor X9.31- standard to implement my PRNG. X9.17 uses DES, but X9.31 uses AES!

Now I need to specify the value of the AES key for X9.31.  I know that at least my AES key must be unpredictable to an adversary. Because of this I want to use the RSA private key of the certificate which belongs to my embedded device. (This value is currently the only one that from my point of view that is unpredictable.)

My idea how to generate the AES key from the RSA private key:

AES_key= SHA1(RSA private key || date)

But is it OK to (ab)use a RSA signing key as a symmetric AES key, to encrypt the seed and finally generate random values? Is there any serious security weakness?

On a general and administrative basis, reusing the same private key for distinct usages is bad.

For this specific case, this should be fine (although you should use SHA-256 instead of SHA-1, if only for reasons of public relations: SHA-1 has bad press and any use of SHA-1 for a new design will be questioned), subject to the important caveat below.

The current date is a monotonous scale. However, your device does not have direct access to that physical value; it only has a clock which provides a discrete (it works by small increments, e.g. 1 second each) approximation of the current date. If you try to generate your AES key twice in the same second, and the "current date" changes only once per second, then you get the same seed, hence the same output, which can be bad. Also, more importantly, if the user (or attacker) can set the clock, then he can potentially enforce a seed reuse, leading to a PRNG sequence repeat. "Setting the clock" must be thought in a wide sense: an attacker who have the device in his hands may try to freeze or cook it, because quartz are sensitive to temperature. He may also play with the power input, e.g. adding a high frequency signal into it, on the hope that it would interact with the quartz and change its oscillating frequency. Possibilities are quite endless; the bottom line is that it is very hard for an embedded device to have an accurate, secure notion of the current time. Even getting a value which an attacker cannot force to repeat can be quite a challenge.

A more robust version would use a counter, which you increase every time you need a new AES key. Make sure that the counter is large enough that it cannot overflow (e.g. use a 64-bit counter). The counter must have permanent storage and never be reset throughout the lifetime of the device; you must also update the counter storage before using the counter value in the PRNG.

By the way, using the RSA private key as PRNG seed will not help you when it comes to actually generating the RSA private key itself. So either you generate the RSA private key externally and import it into the device (e.g. as part of factory initialization), or you have a problem. This might lead to another problem, depending on your exact situation: if a user can force the value of the RSA private key, then he can predict the PRNG output. You do not give information on your security model to know whether this can be an issue for you.


Low exponent attack on RSA public key question is here. determine true or false

I think that in the RSA cryptosystem, one should use large private key because of the low exponent attack.

Also, In RSA cryptosystem, one should use large public key because of the low exponent attack.

Is my thinking right?
How much long or big do these key need to be?

The reason to use a large private key (or rather, not to attempt to use a small private exponent) are given in 5. The reasons to use a large public key are in 1, and have nothing to do with exponent size (private or public). There is no known reason to use a larger public exponent than suggested in 2, and that's uncommon.

In RSA:

One should use a large enough size $n$ for the public modulus $N$; that's important because anything that factors $N$ will break the RSA instance using that $N$, and the resistance of $N$ to factorization tends to grow with $n$ (for constant number of factors of size proportional to $n$). The bit size $n$ of $N$, with $2^{n-1}\le N<2^n$, is known as the key size, public key size, or public modulus size. Official security recommendations start at $n=2048$.
The public exponent $e$ can be fixed to $e=2^{16}+1$, which is most common, compatible, and unobjectionable; or $e=3$ which gives a significantly faster public-key operation (see cautionary note). In modern practice, $e$ is typically a small odd prime fixed and chosen before $N$ and its factors. In any case, $e$ must be odd and at least $3$.
The factors of $N$ must be large distinct primes, and not one more than an integer sharing a prime factor with $e$. They must be randomly and secretly generated and combined into their product $N$. Standard practice is to select two primes $p$ and $q$ as about uniformly random primes in range $[2^{(n-1)/2},2^{n/2}]$ with $\gcd(p-1,e)=1=\gcd(q-1,e)$, simplifying to $p\bmod e\ne1$ and $q\bmod e\ne1$ when $e$ is prime; then compute $N=p\,q$.
A private exponent $d$ is most commonly secretly computed from $e$ and factors of $N$. The smallest working positive $d$ is $d=e^{-1}\bmod\lambda(N)$ with $\lambda(N)=\operatorname{LCM}(p-1,q-1)$ when $N=p\,q$. It is also common to use $d=e^{-1}\bmod\varphi(N)$ with $\varphi(N)=(p-1)(q-1)$.
No attempt should be made to significantly shorten $d$ ("small decryption key") by choosing $e$ or the factors $p$ and $q$ of $N$ for that purpose; that's not possible anyway when following advice in 2 and 3 above. It is known that $d$ shorter than $0.292\,n$ is unsafe; see Dan Boneh and Glenn Durfee, Cryptanalysis of RSA with Private Key $d$ Less than $N^{0.292}$, in proceedings of Eurocrypt 1999. It is unclear what a safe minimum would be; and better speedup is achieved by a common implementation of the private-key function uisng the Chinese Remainder Theorem.
The textbook public-key function $x\to x^e\bmod N$ should be used for encryption, and/or the textbook private-key function $x\to x^d\bmod N$ used for signature generation, only when $x$ is

essentially random in some large interval (with bit size of its width close to $n$) and not under the control of an adversary; for example, $x$ can safely be a random bitstring of $n-1$ bits, converted to integer from binary, encrypted as $y=x^e\bmod N$, decrypted as $x=y^d\bmod N$, and then considered a shared secret, used in part as an encryption key for a message encrypted using symmetric cryptography;
or produced by some appropriate padding technique adapted to the usage (encryption or signature); a recommendable encryption padding is RSA-OAEP; a recommendable signature padding is RSASSA-PSS.

Care should be taken that implementations using a private key (decryption, signature generation) or secret data (encryption) can be vulnerable to side-channel or fault attacks.

Cautionary note: many uses of textbook RSA in introductory literature, and even in the industry, violate 6 to some degree. There is anecdotal evidence that when making goofs there, choosing very small $e$ (like $3$, or much smaller than $n$) makes things worse; but there is no evidence that $e=3$ is less safe than $e=2^{16}+1$, or that any low public-exponent attack applies, when abiding to 6.


Research question: usefulness of newly discovered symmetric key cryptosystem both myself and my collaborators are pure mathematicians with only tangential experience in the study of cryptographic systems, so if this question is unclear or does not belong here, please do let me know.  I apologize for the length of this question, after necessary background my questions appear in the last part.

As previously stated, my collaborators and I are pure mathematicians and over the coming months we will be publishing work on a new class of mathematical system we have discovered (it relates to many different areas in mathematics, the details are not important for the purpose of this question).  One of my collaborators pointed out that certain properties of this system make it ideal for use in cryptography, and indeed upon further analysis this is what we have found.

Using the Alice/Bob/Eve analogy, the basic distinguishing properties of such a cryptographic system are as follows.  Because this is a symmetric key system, Alice and Bob must meet to generate their random key.  Once Alice and Bob wish to send a message, they publicly chose a particular type of mathematical object at random, call it $T$ (the type of mathematical object is not important), and use this along with their key to generate a set of coordinate points that will each uniquely map to a 0 or a 1.

With this, Alice can send Bob a subset of these coordinates (with each coordinate mapping to 0 or 1), and because Bob has the same set of coordinates he can "decrypt" the message of coordinates to obtain the bit string Alice wished to share.

So far this description appears to offer nothing new, and in fact if Alice wishes to only send Bob one message this is equivalent to the one-time pad.  The issue with the one-time pad of course and similar systems is that sending multiple messages with the same key leads to leaks, so for every new message Alice and Bob must use a new key, which of course means sharing the keys in the first place which is difficult.

The unique (we think) property of the cryptosystem offered by this mathematical discovery is that so long as Alice and Bob publicly choose a new particular mathematical object ($T$) to apply their key to before each message sent (of which there is a continuum of choices for $T$), they can use the same initially chosen key to send an arbitrary number of messages, for we can prove that it would be mathematically impossible for Eve to ever determine the key if such a method was used.

In fact, we can also prove that so long as Alice and Bob publicly choose a new $T$ for each message, to Eve each message of coordinates sent between Alice and Bob would random, so no cryptanalysis would work.

Further, one of my collaborators has a (light) background in quantum computing and is highly confident that this system is not susceptible to brute-force attack from quantum computers (much less classical ones).  We also remark that this encryption scheme is highly efficient, and its encryption/decryption time complexity scales linearly with just the size of the secret key chosen (and the complexity of the encryption scales exponentially with the length of encryption key).

My questions are as follows.  Does a cryptosystem exhibiting such properties already exist? Would a cryptosystem exhibiting these properties be of any possible use to the community?  Even if not (ie. analogous systems already exist), should we pursue publishing the method in a journal?  If so, can anyone here recommend any journals, and things to watch out for when publishing in cryptography?

I know I have been incredibly discrete in discussing the details of the mathematical system for I cannot give too much more at the moment, but I hope this information is sufficient for giving general answers to the questions.

Thank you all so much for your time and help.

The unique (we think) property of the cryptosystem offered by this mathematical discovery is that so long as Alice and Bob publicly choose a new particular mathematical object ($T$) to apply their key to before each message sent (of which there is a continuum of choices for $T$), they can use the same initially chosen key to send an arbitrary number of messages, for we can prove that it would be mathematically impossible for Eve to ever determine the key if such a method was used.

Actually, that can easily shown to be impossible, as long as we make a few minor assumptions:

We will assume that the adversary is computationally unbounded (that is, he can perform any finite number of computations)
We will assume that the adversary has access to a number of encrypted messages (along with their corresponding $T$ values); we'll denote these pairs as $(T, C)$ values.
We will assume that the adversary can recognize an incorrect decryption (perhaps he knows the contents of some of the encrypted messages, which is a standard assumption in cryptography)
We will assume that, if some keys act the same (that is, they encrypt and decrypt identically), then finding any key in the same equivalence class as the 'correct' key would count as success for the adversary

So, here is what our adversary would do; he would go through all possible values of the key $K'$, and with each possibility, decrypt every ciphertext $(T, C)$ and see if it results in a plausible plaintext.  If it every $(T, C)$ pair results in a plausible decryption, then the value $K'$ is declared correct.

It should be obvious that, if $K'$ were not the correct key (or in the same equivalence class), then some ciphertext would have decrypted incorrectly; hence this finds the correct key.

Now, the above procedure shows that key recovery is mathematically possible (and we could make the proof less hand-wavy if we shifted to the question of unknown message decryption, which is what the adversary is really interested in).  Of course, if the space of possible keys is large, this procedure is impractical (as we really don't actually have an adversary with unbounded computation), but does leave open the question of whether there are computational optimizations that would make it practical.  That I don't know the answer to, and frankly speaking, neither do you.

And, to answer your questions:

  Does a cryptosystem exhibiting such properties already exist?

Do we have efficient symmetric cryptosystems that are believed to be secure?  Sure, we have quite a number of them.

  Even if not (ie. analogous systems already exist), should we pursue publishing the method in a journal?

Actually, in cryptography, there really aren't many journals (there's the Journal of Cryptology, but that's about it, not counting predatory ones that everyone ignores); all the exciting new work is published in conferences.  On the other hand, I can't think of any conference that would be interested in what you have; the next level down is publishing on eprint (or arXiv), however I'm not certain that even the eprint editors would be that interested in taking this (unless you do some work to show that you've done the basics to ensure that your system isn't trivially weak).

If you do want to pursue your idea, then things to consider:

Is your system still strong even if the adversary knows some of the encrypted messages?  What if the attacker can pick some of the messages (and use what the ciphertexts look like to decrypt other messages of unknown contents)?
How would your system respond if an adversary modifies one of the ciphertexts $(T, C)$, and passes that modified ciphertext to be decrypted?  Will the modified ciphertext be rejected by the decryptor?  That can be handled by other means, however that slows things down (and modern fashion is that encryption and integrity protections should be provided by the same cipher).
You say your system is efficient; what do you mean by that?  For example, if it were implemented on a modern CPU, how long (in CPU cycles) would it do encrypt a message of size L?  If it takes T cycles, what's the size of $T/L$?  If it's more than 5 or so, well, your system wouldn't be considered efficient (by modern standards).


No IV for one off symmetric file encryption My question is (hopefully, for somebody) a simple one; but my project is holding as I'm not sure.

I read on SO that generating encryption keys without an IV is a bad idea, so is using a constant IV as the first part of any cipher block will be the same across multiple encryptions.

If you're encrypting a single file (a private key for local disk storage for example) is it safe to use a constant IV (as the users password will vary)? The problem is, every time I rehash/generate the encryption key from the plain text password, a new random IV is generated resulting an a completely different decryption key for that file.

As already mentioned by fgrieu in a comment, you seem to be mixing up the initialization vector for the cipher with the salt for the key derivation. They play similar roles — both are here to insure that different values of the IV/salt lead to different keys/ciphertext — but they are used in different ways and they have different security properties in this scenario.

When you generate a key from a password, the number of likely passwords is far less than the total number of possible keys. A pretty good password may have 44 bits of entropy; a password used in the wild tends to have a lot less. Compare to 128 bits of entropy in a randomly-generated AES-128 key. This makes the key space vulnerable to brute force search (“I'll derive the key for password1 and try to decrypt. Nope. swordfish? Nope. Tr0b4dor&3? Nope. Tr0b4dor&4? Win!”).

In order to mitigate this problem, deriving a key from a password must include two elements:

Slowness, because spending .1s instead of .1ms to derive the key when the user types his password isn't a performance problem, but it multiplies the work needed by an attacker by 1000.
Uniqueness, so that an attacker cannot precompute all the keys derived from likely passwords and then crack a lot of password-encrypted files by a simple table lookup.

The issues are the same as password hashing — and indeed most password hashing schemes are password-based key derivation algorithms.

To derive a key from a password, you need a password-based key derivation function, which includes a step of key stretching for slowness and uniqueness. The salt, which provides uniqueness, is an input to the KDF, alongside the password. bcrypt, PBKDF2 and scrypt are the three recommended password-based key derivation algorithms nowadays; scrypt has the nicest properties (it's less easy to brute-force with dedicated hardware) but is still a bit new.

The salt must be unique for everybody who uses the same KDF, not just among your files. The best way to ensure this is to have a sufficiently long random salt.

All message encryption algorithms use an IV or nonce to ensure that if you encrypt the same message twice, this isn't visible in the ciphertext (at least the algorithms that are semantically secure — it is occasionally useful to sacrifice this property in the interest of deterministic encryption but that applies to specialized scenarios). If you only ever encrypt one message with the same key, you don't need an IV — the standard thing to do in this case is to use an all-bits-zero IV.

If you only ever encrypt one file with the same key, you don't need an IV. Do consider that if you use the same key for multiple versions of the file, you should use an IV. You may want to derive a new key with a new salt in this situation, though.


Chosen Ciphertext Attack on the Public Key in PGP In Secrets & Lies (2000), Schneier describes a chosen ciphertext attack on the public key under PGP:

  "Since RSA and ElGamal are malleable, known changes can be made to the symmetric key that is encrypted. This modified (encrypted) key can then be sent along with the original message. This opens up the possibility of related-key attacks on the symmetric algorithms. OR, a weak ciphertext can be found whose decryption under the symmetric key algorithm reveals information about the modified key, which then leads directly to information about the original key." [P. 327-328. Schneier, Bruce. Secrets & Lies. 2000]

Could you explain (a) how this attack works and (b) whether it's still feasible in 2016?

TL;DR: This attack extends the standard chosen ciphertext attacks on RSA and ElGamal to the hybrid encryption setting, but requires some huge IFs which no longer even have a slight possibility of being fulfilled.

To understand this attack, one first needs to understand how data is encrypted for PGP according to this snippet. Let's assume you have a recipient key $pk$, a message $m$, an encryption function $E_{pk}( \cdot )$ (either textbook RSA or textbook ElGamal), a random, symmetric key $K$ and a well-known symmetric cipher $E_K( \cdot )$. Now form the ciphertext $C$ as $C=E_{pk}(K)||E_K(m)$ with $||$ denoting reversible pairing (e.g. you can extract both parts later on).

The next step is to note that you can arbitrarily, multiplicatively modify the message in textbook RSA and textbook ElGamal, by performing specific (simple) operations on the ciphertext - only knowing the public key. Note that you can apply the two linked attacks on the encrypted "header" $E_{pk}(K)$ from above.

Now you use these attacks and change the $K$ value to $K'$, preferably in a clever fashion. If the cipher is suceptible to related-key attacks you generate the related keys for this attack this way and then apply your attack on it, possibly by abusing the user as a decryption oracle. Now it also may be, that you stumble across something a ciphertext that looks weak under the new key and allows you to deduce some information from the cipher text about the key, thus easing a brute-force attack.

Is this attack still feasible nowadays? As always, it depends.
The similar encryption mechanisms RSA-KEM and ECIES use a hashing function in between the symmetric cipher and the public key encrypted symmetric key, so they are immune.
If you use RSA-OAEP or an IND-CCA2 secure variant of ElGamal, you're also safe, as the malleability property no longer applies.
Additionally, authenticated (symmetric) encryption also makes this sort of attack much harder, as you first need to find a related key, that doesn't yield an invalid tag and thus reduces you amount of information from "a full decryption under this related key" to "a message whether decryption succeeded under this related key" which is likely not enough for a recovery attack.

If your cipher is (sufficiently) resistant to related-key attacks and doesn't have "weak ciphertexts", you're also safe. Most decent modern ciphers are "sufficiently safe" against related-key attacks, even AES which had some devestating experiences with these attacks is still safe enough.

It's especially the last mitigation that applies nowadays. Nearly everybody is using AES or a comparably strong cipher and thus the required related key attacks do not exist and this is more of a theoretical weakness, than a practical one.


Making a secure file sharing scheme usable I am trying to realize a secure file sharing scheme based on asymmetric crypto. Users will access this via browser.
In short, it works like this:

Users register and set their username and password. From this password, a public/private key pair is deterministically generated and the pk is published to the server.
Once someone wants to publish a file to a selection of receiving users (organized as a room or group), they retrieve the respective list of public keys and generate a symmetric key. They then encrypt the file with the symmetric key and that key with each of the receiver's public keys respectively. Then they send those keyfiles and the encrypted file to the server.
To receive the file, another user can download their keyfile and the encrypted file, then decrypt the keyfile with their own private key and the file with the decrypted symmetric key.

Now there is two main drawbacks to this (in descending priority):

After logging in by providing their password, in order to generate the asymmetric key pair and thus be able to encrypt and decrypt files the client (browser) has to somehow save the password or ask for it anytime it is used.
I want to be able to add a new user to a room/group so that they can access the published files in there. To do this, that user needs to get the "permission" of another member of that room to access the file (by that user reencrypting the keyfile). Can the effort required by another user be reduced?

Do you think those can be fixed within this scheme or how can it be changed to not have these drawbacks?

Here's one obvious problem that you don't mention:

Users register and set their username and password. From this password, a public/private key pair is deterministically generated and the pk is published to the server.

That means if someone downloads the password list from the server, he can go through his list of weak passwords, convert them all into a key pair (using the deterministic process) and see if that public key is listed as anyone's public key.  Given how often weak passwords are used, that's bad.
Even if the username is stirred into the algorithm, it's still bad (the attacker needs to work on each public key separately, that increases his work effort somewhat).
Here's a modification that might make it not so bad; we have the end users generate their public/private keypairs randomly, and then store the private key on the server in an Opaque-type protocol (and the public key in the clear).
That is, the user would take his password $p$ (hashed along with his user name using Argon-2), selects a random value $r$, and computes the EC point $rpG$ over an elliptic curve (where $G$ is the point generator, and the curve may be Curve25519), and sends that to the server, which computes $s(rpG)$ (where $s$ is the server private key) and sends that back to the client; he then computes $r^{-1}s(rpG) = spG$; he then sends that through a KDF, generating a symmetric key $k$, and uses that key to encrypt his private key, and sends that off to the server.
Then, when it comes time to log in, the user enters the password $p$, and repeats the above process, obtaining $k$; the server also gives him the encrypted private key, which he then decrypts.
The disadvantage of this is that the user must interact with the server every time he logs in.
The advantage of this is that an attacker must interact with the server for each password for each user he wants to test; the server can easily notice that it is being queried literally thousands of times for a particular user, and take appropriate action.
And the server never learns the user's private key (it has the encrypted version; however he doesn't learn the symmetric key to decrypt it)


How can I use an XML detached signature when the file may be stored anywhere? How can I use an XML detached digital signature in Java when the URI where the file is being signed will not be the same as when the file is being validated? Specifically, the file to be signed is created and signed on one server, then shipped to another server where it should be verified. The URI is file:///....
Similar to RFC 5485, the need is for the file to be signed "to be stored anywhere without hindering signature validation". Unlike RFC 5485, the need is for an XML formatted detached signature. The Java implementation seems to require the full URI to be the same at the signing time and at the validation time.

You do not need to include a URI in the Reference element of a detached signature. Just include the signature algorithm and the digest value, then you can associate signature and file by yourself.


How much weaker is AES-64 than AES-128? It's hard to say exact QC specs, but let's assume we have decent a quantum computer using Grover's algorithm that is able to half AES-128 keyspace to that of AES-64.

How long will a bruteforce attack take on a AES-64 protected key? What about AES-128 or AES-256? Also, would we be able to increase to AES-512 and still maintain the same level of security?

Since the keyspace is halved, does it also introduce any other possible vulnerabilities to attack vectors (in addition to any attacks that can be done on a QC)?

The main complexity of attacks using a quantum computer with Grover's attack is explained here. I'll use the remainder of the answer to indicate some possible misconceptions in your question.

  It's hard to say exact QC specs, but let's assume we have decent a quantum computer using Grover's algorithm that is able to half AES-128 keyspace to that of AES-64.

Quantum computing won't change the dynamics of the cipher itself. Although the complexity of the attack may be altered, it won't magically change AES-128 into AES-64.

  How long will a bruteforce attack take on a AES-64 protected key? What about AES-128 or AES-256? Also, would we be able to increase to AES-512 and still maintain the same level of security?

Neither AES-64 or AES-512 is well defined. With AES the number of rounds and the key schedule are both dependent on the key size. It's therefore wrong to even talk about AES-64 and AES-512 as you wouldn't know the number of rounds or key schedule, and the security of a cipher depends on those parameters.

  Since the keyspace is halved, does it also introduce any other possible vulnerabilities to attack vectors (in addition to any attacks that can be done on a QC)?

I don't see how it would be able to do that. This would only be the case if additional attack vectors or a better understanding is retrieved from a GC attack. That doesn't seem all too likely.

AES-256 is considered safe against quantum computing attacks; a security margin of 128 bits is considered unbreakable. So there is not much need for AES-512 as currently foreseen.

In general - especially for symmetric algorithms - an increase of key size, block size, internal state and/or output size does seem to satisfy most crypt-analists with regards to attacks based on quantum computing. Instead of just increasing the key size it would probably be wise to use a larger block size and internal state as well (you could use one of the SHA-3 finalists such as Keccak/Keyak or Skein/Threefish as base).


Prove that textbook RSA is susceptible to a chosen ciphertext attack Given a ciphertext $y$, describe how to choose a ciphertext $\hat{y} \neq y$, such that knowledge of the plaintext $\hat{x}=d_K(\hat{y})$ allows $x=d_k(y)$ to be computed.

So I use the fact that the decryption function is multiplicative: $d_K(y_1)d_K(y_2)= d_K(y_1y_2)$.

Thus we have $d_k(y\hat{y})=x\hat{x}$.

Now if $y\in \mathbb{Z}_n$ is a unit then we set $\hat{y}=y^{-1}$ and thus $x\hat{x}=1$ implying that $x=(\hat{x})^{-1}$

And if $y\in\mathbb{Z}_n$ is a zero divisor then we choose $\hat{y}$ such that $y\hat{y}=0$ and thus $x$ is the zero divisor associated to $\hat{x}$.

Is this correct?

You can choose a random number r, and let $\hat{y}=y\cdot r^e \mod n$. Then, invoke the decryption query on the ciphertext $\hat{y}$ and suppose that the answer is $x'$. Then, you can extract $x=x/r\mod n$.


What are the strenghts and weaknesses of Whirlpool Hashing Algorithm I want to find out if the Whirlpool hashing algorithm have any weaknesses. There are quite a bit of articles explaining the strengths of this algorithm, but for some reason I cannot find any on its weaknesses...perhaps there aren't any?

This far there are no known significant cryptographic weaknesses in Whirlpool hash algorithm.

The biggest practical concern would appear to be:

Whirlpool performance is lower than many other hash functions (see e.g., http://www.cryptopp.com/benchmarks.html)

Because of this speed issue, something like SHA-512 often gets more use.


Is it possible to create an open-source SecurID? As far as I understand it, the hardware key-fob two-factor systems such as RSA SecurID depend on secret algorithms, and employ tamper-resistant hardware to prevent reverse engineering.

Is there some mathematical fact that prevents a system like SecurID from operating with open-source software (including the server and token algorithms, hardware token provisioning server) and hardware?

I would assume that, in the past, power requirements prevented the use of public-key algorithms in these little tokens. If it were designed today, would it be feasible to use that sort of approach in long-lived portable hardware tokens?

The best we can do today, in matter of token similar to SecurID (that is with the restriction that the authenticating value produced by the token is keyed-in by a human), is

open-source software on the verifier side, provided that

we accept that there is a secret key on that side
or we have some communication link to the token able to transfer more data than a normal human can do pressing buttons on the token

a public specification for the token, with open-source software and hardware

except for the heart of the cryptographic function used, implemented in a device with physical security such as a Smart Card IC
or if we accept a sizable residual risk that one particular security token could be cloned by a resourceful adversary that gets physically hold of it.

We have to distinguish open-source verifier from without secrets on the verifier's side, and three variants of the later.

It would possible to create a SecurID-like system with open-source verifier. In fact, the security of modern SecurID, or any cryptography following the second Kerckhoffs's principle, is supposed not to depend on any secret in the algorithm itself, but rather on how well the key is kept secret.

However, SecurID-like systems have the requirement that communication from the token is by keying-in short messages, and that is clearly antagonist to having a public method to check a token and no communication to the token: it would be enough to enumerate the possible answers to find an acceptable one.

With the addition of communication to the token with sizable bandwidth (e.g. a 2-D barcode read by the token with a camera, or just an animation on the screen read by photodiodes on the token), that is possible (e.g. make the token decipher the challenge sent RSA-enciphered by the authenticator). I remember seeing, well over a decade ago, a device (perhaps named "La grenouille") that I thought was doing just that (with photodiodes).

If communication to the token is limited to few bits (e.g. using a keyboard on the token), I doubt there is a solution.

As to open-source token: that is hard. The algorithms used by the token can and should be public, but there has to be some secret key in the token. And cloning the token is part of the complete threat model.

Currently it is unheard-of that a physical device with a fully open design holds any secret key tightly secret, facing a resourceful adversary able to manipulate the device. All Common Criteria evaluation of security devices like Smart Cards or HSMs assume some level of secret in the design.


What are the dangers of using CPU clock drift for generating random data? From what I understand, a physical source of true randomness could be achieved with a multi-core processor, by using clock drift between two or more cores.

However, a processor is easier to manipulate than nuclear decay or thermal noise when it comes to true random number generation.

My questions are:

Are there any attacks?
Are any of them practical?
Are there any steps that can be taken or conditions satisfied to prevent attackers from effectively manipulating the output of the processor?
And finally, how easy is it to bias the cpu virtually compared to properly implemented and secure CSPRNG libraries offered, like java SecureRandom?

My last question is really subjective to different libraries but if you can provide examples and scenarios or comparisons of potential attack vectors it would really help me understand.

I am currently under the impression that using a CPU for a TRNG is about as good as a software based CS-PRNG, but I could be wrong.

A TRNG is never used instead of a CSPRNG. They serve different purposes. A TRNG is used to seed a CSPRNG. A CSPRNG alone isn't enough to generate random data since it's reproducible. A hardware entropy source alone isn't enough to generate random data because all entropy sources have biases.

For any purpose that's related to security or cryptography, a random generator (CSRNG) is built by seeding a cryptographically secure pseudorandom generator (CSPRNG) with an entropy source, which is some physically obtained unpredictable, secret input. The CSPRNG whitens the entropy source.

The CSPRNG turns a small amount of data (typically a few thousands of bits) into an effectively endless stream of bits, and ensures that all the bits are independent. More precisely, a CSRNG must have the property that if an adversary sees all the output bits except one (but does not get to see the RNG's internal state), they have no clue what that hidden bit is: it could be either 0 or 1 and the adversary can only guess with a chance of success that's extremely close to $1/2$ — no more than $1/2+2^{-N}$ for a CSRNG with $N$-bit quality (e.g. $N=128$). A CSPRNG guarantees that property provided that its seed is sufficiently “varied”, in that the adversary can't guess the seed with a chance of success that's better than about $2^{-N}$.

A discretization of a physical phenomenon always has biases: some sequences of bits are more probable than others, due to characteristics of the physical phenomenon or to measurement errors. Using this as input to a CSPRNG destroys all the correlations between successive bits. The CSPRNG also has other benefits, including the ability of combining multiple phenomenons, with the safety that combining sources together never weakens the result (even if one of the sources turns out to be partially or totally known to the adversary, the quality of the resulting RNG is still at least as good as the other sources).

Now the real question is, is clock drift (jitter) useful as an entropy source? The answer is yes, it is used in practice. Fast Digital TRNG Based on Metastable Ring Oscillator by Vasyltsov et al. (2008) gives an overview of work in that domain in §2.

If you're an application writer, that's not something you need to care about. Entropy gathering is done by the operating system.

If you're a system integrator, you have to take care that your system has proper entropy sources. All modern PC processors (RDRAND) and smartphones (running iOS, Android or Windows) have hardware RNG (using phyiscal phenomenons that differ from chip to chip). Embedded devices are a very varied breed, some have good entropy sources, others don't; clock drift is often irrelevant in this realm because there aren't enough distinct clocks (unless one has been provided for the very purpose of generating entropy through drift, in which case the manufacturer will generally provide a some firmware or driver code to perform the required measurements).

Measuring clock drift is not trivial. You need to make sure that you're reading data from clocks that aren't synchronized. You need to give the system enough time to get initialized and then for the clocks to get out of synch. You need to beware of environmental parameters; for example some clocks may be effectively unpredictable at sufficiently high temperature but completely predictable at lower temperature. A good hardware RNG will provide a quality estimate. Statistical tests on an entropy source can sometimes help figure out whether it's operating correctly, but often the types of biases depend on the physical construction of the source and tests need to take this physical construction into account in order to be effective.


How do TLS 1.1 and 1.2 generate IVs (initialization vectors) for each record? According to RFC 4346

  Explicit IVs

  [CBCATT] describes a chosen plaintext attack on TLS that depends on
     knowing the IV for a record.  Previous versions of TLS [TLS1.0] used
     the CBC residue of the previous record as the IV and therefore
     enabled this attack.  This version uses an explicit IV in order to
     protect against this attack.

How are the IVs generated in concrete implementations? (like openSSL, BouncyCastle)

An implementation should generate the IV from any cryptographically secure PRNG. TLS 1.1 further details the possible ways to do that:

The IV can be obtained from a PRNG.
A random string $r$ can be generated from a PRNG, and added to the plaintext to encrypt where the IV should go; then the whole lot is encrypted with either a fixed IV, or even the last block of the previous record as IV. This method is easier to map on existing implementations of CBC encryption, because the IV is treated like plaintext. It is safe because $E(r \oplus iv)$, for a given $iv$ (e.g. the last block from the previous record) and encryption function $E$, is as uniformly random as $r$ itself.
The same method, but with $r$ being a fixed string.

It is unclear whether the third method is safe or not. It relies on the encryption $E$ to "act as a PRNG". The TLS 1.1 specification includes this:

 The following alternative procedure MAY be used; however, it has
  not been demonstrated to be as cryptographically strong as the
  above procedures.  The sender prepends a fixed block F to the
  plaintext (or, alternatively, a block generated with a weak PRNG).
  He then encrypts as in (2), above, using the CBC residue from the
  previous block as the mask for the prepended block.  Note that in
  this case the mask for the first record transmitted by the
  application (the Finished) MUST be generated using a
  cryptographically strong PRNG.

Since the specification gives it as a "MAY", one must assume that some implementers may have used this third method. Its advantage is that it does not require a PRNG invocation for every record, only for the first record, so a relatively slow PRNG can be tolerated.

Interestingly, all these detailed paragraphs have been removed from TLS 1.2, which merely states the generic "The Initialization Vector (IV) SHOULD be chosen at random, and MUST be unpredictable".


Does Off-The-Record protocol provide future (backward) secrecy? I know Signal provides future (backward) secrecy, and that it is based on Off-The-Record protocol. However, does OTR by itself also provide future secrecy?

I think so. OTR generates a new DH key pair for each round of message, similar to the DH ratchet in Signal. Also, OTR stands out by having a property called deniable authentication. This basically means the messages are only authenticated during a session between the communicating parties but not after the session. In fact, the MAC key will be revealed after the session is closed.


Multiple signatures on one OpenPGP key. How are they combined? Where are they stored in OpenPGP certificate? When one OpenPGP public key is signed multiple times by different keys, how these multiple signatures become visible on one OpenPGP certificate/key?

For example, I participated in a key signing party and got my public key signed by different people, some people emailed me my signed key, some people uploaded the signed key to key server by themselves, how all of these signatures become visible on my public key (in the OpenPGP certificate)?

Also how long can OpenPGP certificate be? For example, if I had my key signed by 10.000 people how will it look like?

OpenPGP keys are formed by a whole bunch of individual OpenPGP packets, for example the public key itself, user IDs, and also certifications. RFC 4880, OpenPGP provides the specification and a list of possible packets together with their explanation (very technical indeed, but you're descending into the inner details of OpenPGP now).

When fetching a newer copy of the key from any source (let it be a local file import, from the key server network, from local files, ...), GnuPG or other implementations of OpenPGP just merge the individual packets together, adding those it didn't know yet. There is no artificial limit on the number of signatures or other packets, but the individual implementations are likely to have some technical ones (32 bit integers, addressable memory, ...).

You can look at a key's structure using gpg --list-packets or pgpdump. An example output for my own key with some explanations added, originally this is one large stream:

gpg --export a4ff2279 | gpg --list-packets | less

The public key:

# off=0 ctb=99 tag=6 hlen=3 plen=1037
:public key packet:
        version 4, algo 1, created 1356475387, expires 0
        pkey[0]: [8192 bits]
        pkey[1]: [17 bits]
        keyid: 4E1F799AA4FF2279

A user ID packet:

# off=1040 ctb=b4 tag=13 hlen=2 plen=49
:user ID packet: "Jens Erat (born 1988-01-19 in Stuttgart, Germany)"

Binding signature connecting key and user ID, and carrying configuration:

# off=1091 ctb=89 tag=2 hlen=3 plen=1083
:signature packet: algo 1, keyid 4E1F799AA4FF2279
        version 4, created 1356516623, md5len 0, sigclass 0x13
        digest algo 2, begin of digest 18 46
        hashed subpkt 27 len 1 (key flags: 03)
        hashed subpkt 11 len 5 (pref-sym-algos: 9 8 7 3 2)
        hashed subpkt 21 len 5 (pref-hash-algos: 8 2 9 10 11)
        hashed subpkt 22 len 3 (pref-zip-algos: 2 3 1)
        hashed subpkt 30 len 1 (features: 01)
        hashed subpkt 23 len 1 (keyserver preferences: 80)
        hashed subpkt 2 len 4 (sig created 2012-12-26)
        hashed subpkt 25 len 1 (primary user ID)
        subpkt 16 len 8 (issuer key ID 4E1F799AA4FF2279)
        data: [8189 bits]

A newer binding signature:

# off=2177 ctb=89 tag=2 hlen=3 plen=1080
:signature packet: algo 1, keyid 4E1F799AA4FF2279
        version 4, created 1356475387, md5len 0, sigclass 0x13
        digest algo 2, begin of digest 44 77
        hashed subpkt 2 len 4 (sig created 2012-12-25)
        hashed subpkt 27 len 1 (key flags: 03)
        hashed subpkt 11 len 5 (pref-sym-algos: 9 8 7 3 2)
        hashed subpkt 21 len 5 (pref-hash-algos: 8 2 9 10 11)
        hashed subpkt 22 len 3 (pref-zip-algos: 2 3 1)
        hashed subpkt 30 len 1 (features: 01)
        hashed subpkt 23 len 1 (keyserver preferences: 80)
        subpkt 16 len 8 (issuer key ID 4E1F799AA4FF2279)
        data: [8192 bits]
# off=3260 ctb=89 tag=2 hlen=3 plen=284

A certification issued by another key:

:signature packet: algo 1, keyid CBC2613CD745722B
        version 4, created 1356529414, md5len 0, sigclass 0x13
        digest algo 2, begin of digest d3 ec
        hashed subpkt 2 len 4 (sig created 2012-12-26)
        subpkt 16 len 8 (issuer key ID CBC2613CD745722B)
        data: [2048 bits]


Firmware update - 34C3 CTF solution I saw this recently published riddle and its solution in
this link.
My mathematical background is not so strong. Is it possible that someone here to solve the riddle? My background in math is not strong.
I understand that there is some problem in that they repeatedly XOR each (file_name + '\0' + file_content) with the prev. (file_name + '\0' + file_content), and only then use it for authentication against the asymmetric signature.
I understand that our goal is somehow to zeroed our added files hash by XOR with some calculated unique file names, but I do not know how to do it without weakness in the hash algorithm itself.
Please explain the solution in simplest possible way (but at the same time I want to understand exactly what the weakness here is and what exactly is the solution).

The relevant mathematics is elementary linear algebra.

Focusing on the relevant part of the problem, the defender calculates a signature
$$S(m_1, \ldots, m_n) = H(m_1) \oplus H(m_2) \oplus \ldots \oplus H(m_n)$$
where $\oplus$ is bitwise xor, $H$ is a cryptographic hash function and $(m_i)$ is a family of messages (which are file names) of variable size. The goal of the attacker is to find a family of messages such that:

The signature is equal to some value $S_o$ which is the signature of the legitimate message.
One of the messages has a specific content which is the payload that the attacker wants to inject.
No two messages can be equal, because there can only be a single file by a given name.

So we need to find $n$ and $m_1, \ldots, m_n$ such that
$$S_0 = H(m_0) \oplus H(m_1) \oplus H(m_2) \oplus \ldots \oplus H(m_n)$$
i.e.
$$H(m_1) \oplus H(m_2) \oplus \ldots \oplus H(m_n) = S_1$$
where $S_1 = S_0 \oplus H(m_0)$.

If $H$ was invertible, we'd just take $n=1$ and $m_1 = H^{-1}(S_1)$. But since $H$ is a cryptographic hash function, this approach is out. Nonetheless, let's look a bit more at what we could do if we could find messages whose hash has a specific value.

$H(m)$ is a 256-bit value. Suppose we could find 256 messages $(M_1,\ldots,M_{256})$ such that $H(M_i)$ is all-bit-zero except that the $i$th bit is set. Then we could take a subset of these messages corresponding to the bits that are set in $S_1$: $S_1 = \bigoplus_{i \mid \text{the \(i\)th bit of \(S_1\) is set}} H(M_i)$.

We're trying to express $S_1$ as the xor of a bunch of values. The xor operator is linear: it satisfies all the axioms that define a vector space over the field $GF(2) = \mathbb{Z}/2\mathbb{Z}$. In the field $GF(2)$, the elements are $0$ and $1$, the addition $\oplus$ satisfies $1 \oplus 1 = 0$ (i.e. it's xor) and three's only one way to define multiplication ($0$ times anything has to be $0$ and $1$ times anything has to be that thing). Bitwise xor on 256-bit numbers is vector addition in the vector space $GF(2)^{256}$. And expressing a vector as the result of adding a bunch of vectors is a well-studied problem: we're trying to express $S_1$ as a linear combination of some values.

Any value can be expressed as a linear combination of $100\ldots0$, $0100\ldots0$, $00100\ldots0$, …, $0\ldots010\ldots0$, …, $0\ldots01$. Picking the bits that are set in the resulting value means taking each term $0$ times if the corresponding bit in the result is clear and $1$ times if the corresponding bit is set. A set of vectors such that any value can be expressed as a linear combination is called a generator set of the vector space. A set of vectors such that none of them is a linear combination of the others is called linearly independent. A linearly independent generator is called a basis of the vector space.

If a vector space has a finite basis, then all of its bases have the same number of elements. This number is called the dimension of the vector space. Here we're working in a vector space with a 256-element basis, so it's a 256-dimensional space. The dimension has other nice properties, including the fact that in a vector space of dimension $d$, if a set of $d$ vectors is a generator then it's a basis, and if a set of $d$ vectors is linearly independent then it's a basis.

Recall that our problem is to find a way to express $S_1$ as a linear combination of some vectors. Furthermore each vector must be the hash of some message. We can do that by:

Finding a basis made of vectors that are the hashes of known messages.
Expressing $S_1$ as a linear combination of this basis.

For part 1, recall that it is enough to find 256 hashes that are linearly independent: since the vector space has dimension 256, such a set of 256 hashes will be a basis. $H$ is a cryptographic hash function, so it behaves essentially at random. We can take any message, calculate its hash, and if we don't like the resulting hash then we take a different message and try again. We can construct 256 successive messages such that each new message's hash is not a linear combination of the previous ones. That is:

Take an arbitrary $m_1$. While $H(m_1) = 0$, change $m_1$ and try again.
Take an arbitrary $m_2$. While $H(m_2)$ is either $0$ or $H(m_1)$, change $m_2$ and try again.
Take an arbitrary $m_3$. While $H(m_3)$ is a linear combination of $\{H(m_1),H(m_2)\}$, change $m_3$ and try again.
Take an arbitrary $m_4$, etc.

After building $k$ messages $(m_1,\ldots,m_k)$, there are $2^k$ hashes that are linear combinations of the hashes of those messages. This means that the number of forbidden hash values at each step is $2^0$, $2^1$, $2^2$, etc. At the 256th and last step (i.e. after building 255 messages), the number of forbidden hash values is $2^{255}$, which is half of the total number of possible hash values. This means that the probability of a successful draw is $1/2 = 1-1/2$ for each attempt at the last stage, $1-1/4$ at the previous stage, $1-1/8$ at the stage before, etc. Note that the probability of success is always at least one half, so this randomized algorithm is practical, it won't get stuck trying to find something that's almost impossible to find.

Part 2 is a classical problem in linear algebra which led to the definition of multiplication of matrices. We saw above how to express any vector as a linear combination in the basis made from vectors with all-bits-zero-except-one. We now want to express the old basis in terms of the new one, i.e. to express each all-bits-zero-except-one vector as a linear combination of the new basis. This means finding the inverse of the matrix that expresses the new basis in terms of the old one, which is equivalent to solving a system of 256 linear equations (one for each bit position) with 256 unknowns (the coefficient of each vector in the basis).


How does one provide a secure and authentic communication channel? Let assume two participants Alice and Bob who perform a given protocol which is a sequence of messages exchange between them.

My question is: How can I provide a secure and authentic communication channel using cryptography, so that when Bob sends a message "M" to Alice, the latter will be able to know whether or not the message "M" is from Bob?

Is there a solution without using certificates?

"Authentic" is defined with regards to an identity. A message from Bob is authentic only insofar as Bob is distinct from Charlie. There must be something which, from the outside, makes Bob and Charlie two different entities.

In a computerized world with networks, Alice can "see" other people only through the data they send. Moreover, everybody can buy a computer, so what Bob can compute, so can Charlie. The only remaining way for Bob to be distinct from Charlie is what Bob knows. That's how identities are defined in cryptography: you are what you know.

So Alice can make sure that a given message $M$ comes from Bob (and not Charlie) only if Bob does some computation over the message $M$ which involves some data that Bob knows, but not Charlie.

A basic, traditional setting is when the "secret" known by Bob is a sequence of bytes which Alice knows too. That sequence of bytes can then be used as key in a Message Authentication Code: this is a kind of checksum, which Bob can compute over $M$, and that Alice can recompute over $M$ since she also knows the "secret"; that's how Alice verifies the MAC. But Charlie cannot compute the MAC since he does not know the secret. The shared secret can also be used as key for symmetric encryption, so that the message contents can remain confidential: there again, Alice can decrypt the data encrypted by Bob (since she knows the secret) but Charlie cannot. Combining symmetric encryption and a MAC while using the same secret as key for both can be somewhat perilous; there are subtleties.

The traditional scheme has the drawback of having a shared secret between Alice and Bob: since identities are "what we know", this means that Alice and Bob are really the same entity, "Bobalice". The scheme above is about Bobalice talking to himself/herself. That's not a useless model: that's what happens when you encrypt some data so that you can store it, and decrypt it back later; i.e. you are talking with yourself through time. In practice, for two distinct human beings, this means that Alice can authenticate Bob's message, but cannot prove it, because whatever MAC Bob computes, Alice could have computed as well. Also, setting up a shared secret between two people can be hard in some contexts (they must have met beforehand, or something like that). Finally, in the context of software (which is, by definition, quite dumb), there can be some issues if an attacker tries to send back to Alice one of her own messages: Alice knows that a message $M$ is from Bob because only Alice and Bob know the secret value which is needed to compute the MAC, and (that's the critical point) Alice remembers that she did not send that specific message -- so it must be from Bob. The "remember" bit can be tricky; a simple way is to add the sender name in each message (so that a message from Alice always begins by "From Alice").

To go further, we need public key cryptography. This leads to the following protocol: Bob has a key pair for an asymmetric encryption algorithm (e.g. RSA) or a key exchange algorithm (e.g. Diffie-Hellman). The "public" part of the key is known by everybody (that's what "public" means), including Alice. The "private" part of the key is known by Bob only (it is "private"). Alice choose a random sequence of bytes $K$ and encrypts $K$ with Bob's public key; she sends the result to Bob. Bob uses his private key to decrypt $K$, at which point ALice and Bob have a shared secret ($K$) and they can use it as above, with symmetric encryption and a MAC.

With public key cryptography, Bob is distinct from everybody else, including Alice; he has his very own private key. Bob's identity is defined as "whoever controls the private key corresponding to that public key". This still requires Alice to be able to know, in a reliable way, Bob's public key, where "reliable" means that Alice will not be induced into mistakenly using Charlie's public key. That's where certificates come into play: a certificate is a piece of data which is signed by an authority and says: "this is Bob's public key". It is a way to distribute public keys (and their binding to identities) in a verifiable fashion. There can be other ways.

For instance, in the SSH protocol, a client (which tries to connect to a remote server) knows the server public key by remembering it (the client stores a local copy of the public key). This requires a specific bootstrap procedure, for the first time the client connects to a given server, but afterwards the server key is known to the client, and the client just uses it to authenticate the server.


DSA generate signature and verify I'm trying to generate a signature for DSA with the following parameters:

$p = 23$ , $q = 11$ , $g = 3$ , $H(m) = 8$ , $x = 5$

for the life of me, I cannot choose a random $k$ ($0 > k > q$) that will give me $r$ , $s$ that 'add up' when calculating $w$, $u1$, $u2$, and verifying.

I don't know if I'm just doing my maths wrong, but I've tried every possible $k$ between $0$ and $11$ and I just can't get $v = r$ at the end of verification.

can someone please please help and show your working out if possible?

Ok, back to my initial answer (which I edited to the last version, thinking that you did not choose an appropriate generator):

I now think that you may calculate the inverses wrongly:

I tried it with $k=2$ and get:

$r=9,k^{-1}=6, s=10, w=10, u_1=3, u_2=2$ which works out.

Just as an additional comment:

Choosing a generator

Since the order $11$ is prime, you can simply choose an arbitrary element of $Z_{23}^*$, say $h$, and then compute your $g$ as $g=h^{22/11} \pmod{23}$, i.e., every element that lies in this subgroup is a generator of this subgroup.

Take for instance $h=2$ and compute $g=h^{2}\pmod{23}=4$ (in your case, $3$ is also fine).

General case: For the general case $Z_p^*$ with $p$ being prime, an element $g$ is a generator if it holds that all for all prime divisors of the order $p-1$ the following holds:

$g^{(p-1)/q_i}\neq 1 \pmod{p}$.

Typically, you construct $p$ as a safe prime, i.e. choosing prime $q$ and set $p=2q+1$ as, then you know the prime divisors $2$ and $q$ by construction.


Zero-Knowledge Proof of honest function execution - Is this possible? Assume Alice and Bob share a well-known function $f(x)$. Bob asserts that he has a $y$ such that $f(y) = true$. Bob's $y$ is secret, but he is willing to share a hash of it. Alice wants to purchase $y$ from Bob, but only if she can be assured that $f(y) = true$ before the purchase happens.

I've studied Zero-Knowledge Proofs, but the examples I've seen seem to be focused on proving knowledge of a value without revealing the value itself. This seems different... Alice must somehow know that Bob executed $f(y) = true$ truthfully, without altering $f(x)$ or substituting a different value for $y$. Is this possible without a trusted third party?

I am not totally clear on what the procedure for actually "buying" something in your protocol should be, but I'd point out that a (totally) fair exchange between Alice and Bob is impossible.
This follows from the fact that no 2 party secure computation protocol can achieve fairness (impossibility result). In a nutshell: When Alice and Bob run a protocol to exchange some secrets, then one party can always abort as soon as it gets its result without letting the other party know their secret.
As pointed out by Yehuda Lindell in the comments this is not true for all functionalities, see link in the comments.

Lets focus on how Bob can convince Alice that he has some secret $x$ that fulfills some predicate $f$.

In the case of arbitrary predicates $f$, like "I know a pre-image to a specific SHA-1 output", you can use something called zero knowledge using garbled circuits. This approach first appeared in the following paper: zero knowledge using garbled circuits.
The high level idea is to use so called garbled circuits that are, in general, used for secure two party computation (which your problems is a special case of).
For your setting, Alice is the verifier and Bob the prover.
The protocol proceeds as follows:

Alice garbles a circuit representing the prediate $f$ and sends this circuit to Bob (note Alice has no input to that circuit).
Bob uses oblivious transfer to retrieve the wire input labels to the circuit that correspond to his input $x$.
Bob evaluates the circuit and commits to his output wire(s)
Alice "opens" the garbled circuit she sent in step 1 to convince Bob that she did not cheat by garbling some malicious circuit
Once Bob is convinced everything was Ok, he opens his commitment.

On a high level Bob cannot cheat because the only thing he is doing is retrieving some input wire labels, and running them through the circuit.

This may sound like a terribly slow approach, but it is actually not that bad and it strongly depends on what you want to do with it.

Garbled circuits, where only one party has an input are more efficient then the general garbled circuits (see Two halves make a whole in the "privacy-free garbling" section).

Another fairly efficient protocol was recently proposed ZKBoo. This protocol also does something similar to using garbled circuits. However, they focus on reducing the computational costs, but slightly increase the bandwidth overhead, which is already the bottleneck in all garbled circuit approaches.

For less general predicates there may be more direct and more efficient solutions.

Update/Answer to comment:

Whether garbled circuits are practical for "complex" predicates very much depends on how well you can represent them as a computation of a boolean circuit. As a rule of thumb, if you have lots of array accesses, e.g. binary search, then circuits are probably not your best option. There are protocols for general secure ram computation (that's where you have array accesses) and even tailored protocols for zero knowledge proofs using secure ram computation (see Efficient Zero-Knowledge Proofs of Non-Algebraic Statements with
Sublinear Amortized Cost). I don't know how efficient this would actually be in practice, but if you want to play around with this, then you should maybe check out the obliv-c library (https://github.com/samee/obliv-c). Even though their protols are not specifically tailored to the zero knowledge setting, it's easy to use and I think the implementation of their oram extension described in the following recent paper Revisiting Square-Root ORAM is also available on their github page.

Regarding your concrete example of a spell checker you should look at a concrete algorithm and then just take the stuff I wrote above into account.


Hashing passwords with a salt - why use different salt for everyone? Given a database where we have usernames and passwords, we want to secure users' passwords by hashing them. We should not use only username and passwords in this hash, as someone having data from other sites that uses the same hashing function can come to the same results and thus know our passwords. If we try hashing the passwords by themselves it would be easy to bruteforce the entire database and guess all the passwords. In normal applications, passwords are hashed with a random salt that is stored along with them to prevent them from being bruteforced easily.

However, we could just use username, password and the same salt for every record in the database. This option would save one data field for each record, while the combination of username and password would be unique for our entire database. Is such a solution just as safe as the traditional password hashing scheme, or are there some security drawbacks to them I am not aware of?

Let's try to avoid random per-password salts. If the only requirement for salt is to be unique, which is the case for good password hashing schemes, you'll need:

$globalSalt$ is a secret random 32-byte string.
$userId_n$ is a unique user identifier.

You can use, for example, $HMAC$-$SHA256(globalSalt, userId_i)$ to generate salt for each user $i$. Or, with PBKDF2 or scrypt, you can just concatenate the values of $globalSalt$ and $userId_i$.

This scheme achieves uniqueness for salt only when you don't allow users to change their passwords. If you do, salt will be unique per user, not per password, so if someone changes their password, their salt will stay the same. In which case, if there are database leaks at, say, three points in time, given that the salt is unique per user, not per password, the attacker gets some information about passwords (e.g. if the user changed their password to the same value.)

To make salt unique per password, you also have to include some counter of password changes, which you have to update and store, and concatenate with $userId$. Storing this counter per-user defeats the original intention, so you can have a single global counter, making sure it never repeats, in which case you can also drop $userId$ and just use this counter along with $globalSalt$.

If $globalSalt$ is leaked, the only advantage the attacker gets is that he will be able to precompute future hashes for current and future $userId$s, which doesn't seem very useful.

We avoided generating and storing random salts by building a more complex and less secure system. Thus, it's much simpler and more secure, as others said, to use random salts instead of bothering with implementing your own scheme.


Does security against a CCA1 attacker imply security against a CPA attacker? I've seen it mentioned multiple times, but have not seen a formal proof of how security of an encryption scheme against a non adaptive chosen-ciphertext attacker (under non-malleability or ciphertext indistinguishability) implies security against an adaptive chosen-plaintext attacker.

Does IND-CCA1 imply IND-CPA (and NM-CCA1 imply NM-CPA)?

Simply consider the two games and a reduction between them. From the contapositive you need to show that every attacker against CPA yields a CCA1 one. Now, from every CPA adversary you can always construct an adversary that breaks CCA1 but simply makes/requires no decryption query (clearly the same holds for CCA2).


How to find the generator of an elliptic curve? If the elliptic curve has prime order of points, then all of its points are generator. Is this true? If so, how can I find the optimized generator(which generates more number of points) among them?

If the elliptic curve has prime order of points, then all of its points are generators.

Almost: The point at infinity is not a generator, but (if the number of points is prime) all finite points are. This is a consequence to Lagrange's theorem.

  If so, how can I find the optimized generator (which generates more points) among them?

This does not make sense: Any generator of a group must generate all the points, otherwise it wouldn't be called a generator (by definition).
Note also that generally, the choice of base point does not matter, thus one typically uses random points or points with "interesting" (e.g. small) coordinates.


Is HKDF one-way, namely given `Ko` it's hard to guess `Ki`? For background, a HKDF (hmac based key derivation function) takes the form of Ko = KDF(Ki, Label, Context, Len) where Ki is the input key and Ko is the (usually longer) output key, computed by iteratively applying HMAC (initially keyed by Ki) until the desired length is reached. See pseudocode here.
Can I assume HKDF is one-way, namely given Ko it's hard to guess Ki? It seems intuitive, as HMAC output should not lead to recovery of the MAC key.

Very shortly, yes, this is the case.
A KDF is secure if an adversary cannot make a distinction between the output of the KDF and random output (with a larger probability of ${1 \over 2} + \epsilon$). The attacker gets to know the salt and is able to choose the $Info$ parameter and output size (i.e. all the other input parameters) as well as any previous output. This is basically a plaintext excerpt of chapter 3 of the original paper "Cryptographic Extraction and Key Derivation: The HKDF Scheme".
It is easy to see that the above definition fails if the input source keying material is known to the attacker. Hence it is of vital importance that the KDF is one-way with regards to the input keying material. Usually all the output of a KDF is generated by one-way functions in the first place, usually a hash based MAC. In the case of HKDF this is HMAC. In the paper they generally talk about a one-way function as primitive.
This is rather expected; the whole idea of key derivation is to decouple the output from the input to any adversary. Other methods of establishing a key may not carry this property though; there is a reason why HKDF has decided to include a security definition of KDF inside the paper instead of pointing to another document. The fact that the security of HKDF is formalized is one of the big strengths of HKDF and has probably helped it getting standardized by NIST.
HMAC is relatively complex because it requires protection against length extension. When e.g. SHA-3 is used you could use KMAC or a similar construction instead. KMAC already generates as many output bits as required, which makes a KDF-expand function easier to define as well.