Is Rfc2898DeriveBytes random? C# I am trying to wrap my head around encryption in .NET. I am trying to implement a simple solution in ASP.NET Core to encrypt a cookie containing some non-meaningful numbers to outsiders. I need to be able to read the cookie content again.

This example (http://www.saipanyam.net/2010/03/encrypt-query-strings.html) uses Rfc2898DeriveBytes and RijndaelManaged but I don't understand if Rfc2898DeriveBytes is producing a random key tied to e.g. machine key or something else.

I need to be able to move software to a new server without managing machine keys, Redis or similar (just looking for something very simple to encrypt data).

// is this random? And if so, will I be able to read cookie contents in potentially 2 years of time?
keyGenerator = new Rfc2898DeriveBytes(ENCRYPTION_KEY, SALT);
key = keyGenerator.GetBytes(32);

// entire code from link above (clean up)

public static class MyHelper
{
    private const string ENCRYPTION_KEY = "some-secret-key";

    /// The salt value used to strengthen the encryption.
    private readonly static byte[] SALT = Encoding.ASCII.GetBytes(ENCRYPTION_KEY);
    private readonly static byte[] key;
    private readonly static byte[] iv;
    private static readonly Rfc2898DeriveBytes keyGenerator;

    static MyHelper()
    {
        keyGenerator = new Rfc2898DeriveBytes(ENCRYPTION_KEY, SALT);
        key = keyGenerator.GetBytes(32);
        iv = keyGenerator.GetBytes(16);
    }

    /// Encrypts any string using the Rijndael algorithm.
    /// A Base64 encrypted string.
    public static string Encrypt(string inputText)
    {
        //Create a new RijndaelManaged cipher for the symmetric algorithm from the key and iv
        RijndaelManaged rijndaelCipher = new RijndaelManaged { Key = key, IV = iv };

        byte[] plainText = Encoding.Unicode.GetBytes(inputText);

        using (ICryptoTransform encryptor = rijndaelCipher.CreateEncryptor())
        {
            using (MemoryStream memoryStream = new MemoryStream())
            {
                using (CryptoStream cryptoStream = new CryptoStream(memoryStream, encryptor, CryptoStreamMode.Write))
                {
                    cryptoStream.Write(plainText, 0, plainText.Length);
                    cryptoStream.FlushFinalBlock();
                    return Convert.ToBase64String(memoryStream.ToArray());
                }
            }
        }
    }

    /// Decrypts a previously encrypted string.
    /// The encrypted string to decrypt.
    public static string Decrypt(string inputText)
    {
        RijndaelManaged rijndaelCipher = new RijndaelManaged();
        byte[] encryptedData = Convert.FromBase64String(inputText);

        using (ICryptoTransform decryptor = rijndaelCipher.CreateDecryptor(key, iv))
        {
            using (MemoryStream memoryStream = new MemoryStream(encryptedData))
            {
                using (CryptoStream cryptoStream = new CryptoStream(memoryStream, decryptor, CryptoStreamMode.Read))
                {
                    byte[] plainText = new byte[encryptedData.Length];
                    int decryptedCount = cryptoStream.Read(plainText, 0, plainText.Length);
                    return Encoding.Unicode.GetString(plainText, 0, decryptedCount);
                }
            }
        }
    }
}

No, Rfc2898DeriveBytes itself represents a deterministic algorithm. Any randomness it produces comes from a combination of randomness in the password (incorrectly named ENCRYPTION_KEY in the code) and the salt (the correctly named SALT). The other input options (such as the iteration count and string encoding) are configuration options and do not add significant randomness while still altering the final result.

Generally the output of Rfc2898DeriveBytes is made random by using a random salt which is then stored with the ciphertext (or resulting password hash, if it is used for that purpose). During decryption that same salt is used as input so that the same output key material can be produced to perform the decryption.

There are ways of constructing a class instance in such a way that the salt is generated internally, e.g. Rfc2898DeriveBytes(String, int) where the final int is the salt size. That's however not used in the code that you've shown.

Notes:

The inaptly named Rfc2898DeriveBytes class implements PBKDF2 and therefore should have been named PBKDF2DeriveBytes or just PBKDF2.
As indicated, PBKDF2 operates on a password, not a key. You can directly use a key with a unique or random IV to encrypt ciphertext if you already have a key.
A sentence such as "just looking for something very simple to encrypt data" will make any cryptographer cringe. You either do cryptography right or you can forget about security; there is not all that much middle ground.


Seed / reseed DRBG too often? There are limits to how much you can use a the DRBG before you have to reseed
it, but are there any limits to how much you must use it before reseeding?

Take the following scenarios as an example…

Usually you seed the DRBG once, then you use that instance until you reach the
reseed limit. Like so:

seed     = seedFromUrandom    // Reads entropy from /dev/urandom
genStart = drbgFromSeed seed
(v1, gen1) = genBytes genStart // Generates random data and the next state
                               // of the DRBG as a tuple
/*
    Code using the random data in v1
*/
(v2, gen2) = genBytes gen1 // Generates more random data and the next state
                           // of the DRBG as a tuple. Note that gen1 is
                           // used here and not genStart.
/*
    Code using the random data in v2
*/

What if you created a newly seeded instance each time you want to generate
random data? Like so:

seed     = seedFromUrandom    // Reads entropy from /dev/urandom
genStart = drbgFromSeed seed
(v1, _)  = genBytes genStart // Generates random data and ignores the
                             // next instance of the DRBG.
/*
    Code using the random data in v1
*/
seed     = seedFromUrandom    // Reads entropy from /dev/urandom
genStart = drbgFromSeed seed
(v2, _)  = genBytes genStart // Generates random data and ignores the
                             // next instance of the DRBG.
/*
    Code using the random data in v2
*/

Please note:

When I say “DRBG”, I mean the NIST standardized number-theoretically secure
random number generator. Either HMAC (SHA512), Hash (SHA512), or counter
(AES 128).
Like stated in the pseudo-code, entropy is read from /dev/urandom.

/dev/urandom itself is an acceptable crypto-quality (P)RNG. Therefore it can't hurt security to call it as often as you want. Assuming that /dev/urandom operates correctly (i.e. returns bit that cannot be predicted), the probability for an observer to correctly predict the bits generated by drbgFromSeed decreases (very slowly) with the number of generated bits.

You could, in fact, read from /dev/urandom and never use a DRBG internally. There are reasons not to do that, but they aren't security:

The most common reason to avoid reading /dev/urandom too often is performance.
You may prefer to use a know PRNG internally and keep outside sources as strictly entropy injection. This would make your application portable to platforms that don't provide a usable PRNG, and you have to make do with something else (e.g. downloaded or pre-seeded entropy).
Using your own DRBG implementation (or a known good one) can help if you need to demonstrate the security of your application.
Maybe you need the determinism property at some point — but then you're better off using an explicit KDF.

What you need to be extremely careful of is never using the same DRBG state more than once. Discarding a DRBG state is fine. The DRBG state has an affine type (your syntax looks like Haskell, beware that without a monad to enforce linearity, the mistake of reusing a DRBG state is a lot more likely than in an imperative language).


If there is an algorithm A can calculate the modular square root of input n, How to use it to get prime factors? Suppose you are given an algorithm $A$ which takes $y \in \{0, 1, \ldots , N − 1\}$ as input, and outputs $x \in \{0,1,\ldots,N − 1\}$ such that $x^2 \equiv y \pmod{N}$. Design an efficient, randomized procedure that uses $A$ to get prime factors.

This is a homework problem for the graduate algorithm course.

It's similar to this question. The difference is that we don't have a specific number 51733469. My idea is that we can randomly pick a number $a$ between $[1,n-1]$, use $A$ to calculate it's modular square root and do exactly like the solution here? Or the randomly-picked number $a$ should satisfy any sort of condition?

How many solutions are there for equation $x^2\equiv y\pmod N$?

That problem is easier when $N$ is odd and $\gcd(y,N)=1$ (notice that when either does not hold, we have a factor of $N$): there are either $0$ or $2^k$ solutions, where $k$ is the number of distinct primes $p_i$ dividing $N$. Proof starts with $N$ prime (see Legendre symbol), then a power of a prime, then the product of powers of distinct primes (using the Chinese Remainder Theorem).

  Why the algorithm $A$ would always return the same output?

The proof thought to answer the question should work including when the algorithm $A$ always return the same output $x$ for input $(y,N)$, because nothing in the question's assumption "Suppose.." says that $A$ will return all solutions, or would eventually return all solutions when invoked repeatedly. Many algorithms are deterministic, that is always perform the same operations for a given input, including producing the same result. Actually, in cryptography, we often implicitly restrict to such deterministic algorithms, considering that a random behavior must come from an explicit extra random input.

Hint: you want to have two solutions: one you know beforehand, and one that the algorithm will give you. The algorithm can't read your mind, thus there's a chance that it will return another solution, and perhaps that will be helpful.


Simulator in semi-honest model in real/model paradigm Does a simulator in the semi-honest model in IDEAL/REAL model paradigm necessarily make use of the corrupted party's input?

For example, suppose a simulator given an input named $I$ and an output named $O$, tries to simulate the view of the real world. In this case, should the simulator necessarily use the input $I$ for the simulation? Or the simulator can simulate without the use of the input? Does it depend on the scenario?
If you need the exact scenario, please refer to the below link:

Exact Scenario

It depends on the scenario. My intuition says that typically it would be used. In particular, the transcript that is generated during simulation includes the randomness of the corrupted party/parties and their incoming messages. Given this, it is possible to compute the outgoing messages sent by the corrupted parties. Since these messages must somehow embed the corrupted parties' inputs in a real execution, they would need to also be embedded in the IDEAL simulated messages.

Having said the above, note that it may be implicit. For example, in the EGL oblivious transfer protocol (see for example, Section 2.1 of this paper by Iftach Haitner), the receiver sends a message to the sender, and the sender replies. If the sender is corrupted, then the simulator only needs to generate the first message, and the second message which embeds the corrupted party's input is implicit (generated from the incoming message, input and randomness). As such, the simulator itself never needs to relate to the message.


Multiple public key encryption Sorry for the newby question but would this work: Alice encrypts a message X with John's public key to form Y. Alice then encrypts Y with Bob's public key to form Z. Alice then sends Z to Bob and John.

Would I be correct in assuming that to decrypt Z,  Bob would have to use his private key on Z to get Y.  After this John would have to decrypt Y with his private key to get X?

Thanks

No. Alice encrypted X by John's public key to have Y. e.g. Enc(key_John, X)= Y.
So the only work that John is able to do is decrypting Y by his private key to have X.

Generaly, first Alice here has encrypted X by John's key, then encrypted the result by Bob's key. Therefore both Bob and John have recieved: Enc(key_Bob, Enc(key_John, X))

So to get X again from Z, you must first achieve Y from Z( by decrypting Z via Bob's key), then achieve X from Y ( by decrypting computed Y via John's key). which means:

Dec(key_John, Dec(key_Bob, Enc(key_Bob, Enc(key_John, X)))

Note that each person only can decrypt the message which is encrypted by his key.


What requirements would lead to the development of a new security protocol? I recently completed a semester studying some basic amount of cryptography. So my knowledge is not very broad/deep.

What I currently see is that we have a bunch of fairly secure encryption modes to encrypt data and fairly secure authentication protocols to authenticate/identify subjects.

Now security protocols are a broad domain. Sticking to encrypting data and authenticating users, are there any use cases (ability to process encrypted data or special authentication case, if any) that the current set of well known protocols  don't cover? Do industry researchers need to spend time coming up with their own protocols?

There are plenty of security issues which are not yet solved with widely used protocols:

At the low level there are reflection/amplification attacks. DNS (and in particular DNSSEC) is known to be vulnerable to this. DNS cookies have only recently been standardized, and is not yet widely deployed. Other protocols are lacking in this area as well.
Logins are still performed in ways that allow servers to see passwords in clear. Rather than fixing this at the protocol layer we have tried to educate users to use different passwords for all sites. It is still a possibility that improvements in this area may become popular.
Anonymity is not very well protected by current protocols. At the moment there are big players actively trying to undermine users' anonymity. New protocols might try to address this.
Confidentiality could be protected better with opportunistic encryption. Opportunistic encryption where identification of the peer being communicated with is optional can improve security compared to a setting in which communication is done unencrypted due to the complexities of key management.


How can Alice prove that a message has not been tampered with? In terms of the usual suspects.

The problem I have is that Alice wants to send Bob a message M, which gives Bob permission to perform some actions.  However Alice wants to verify, from time to time, that the Bob has not changed the message in anyway, allowing himself more privileges than Alice originally intended, without having Bob send the message M back to Alice.

Obviously Alice cannot keep asking the same question as Bob could successfully answer once, change the message, and repeat the first answer every time.

Other contributing facts, Alice obviously knows the message M that was sent, and knows that she was talking to Bob, and can trust that the messages and responses are not modified in transit

There are two parts here, and not just one message to Bob.  Alice's authorization should be viewed as a packet within a packet.  This is often referred to as a token.  The message from Alice to Bob may be email, but the token is a cryptographic value.  Bob can't decrypt the token and play with it, because Bob doesn't have the keys needed.

The permissions Alice is granting are not intended to go to Bob as the final recipient.  She isn't telling Bob "you have read access to the database."  She is telling an authorizing system "Alice is granting Bob read access to the database."  So Alice needs to securely communicate her intent to the authorizing service.  In your scenario you describe Bob as seeking Alice's approval, and she replies to him with a message.  But Bob is responsible only for receiving the token from Alice and delivering the token to someone else.  He might forward it on to the authorizing system, or he might pass it along to the database (who would pass it to the authorizer.)

Think of Bob not as the recipient of the token, but as Eve (the eavesdropper) or Mallory (the malicious attacker) standing between Alice and the authorization system.  The token has to be secured against Bob's tampering.  When done right, it doesn't matter if those messages are seen by Bob as they flow through his hands.

See Kerberos for an example of a security system that behaves as you describe.


Upper bounds on difference of RSA primes I was wondering whether given a concrete $N = p \cdot q$ whether we can find a upper bound  on $\Delta = | p - q|$ as function of $N$ e.g, $N^\delta$, and thus test whether a given $N$ is vulnerable to Fermat-Factoring?

Given that $p$ and $q$ are prime, they must be at least $2$, so $|p-q| \le \frac 12N - 2$. I'm pretty sure that's the only hard upper bound one can give.

Of course, typically $p$ and $q$ are chosen at random from among primes having the same bitlength in binary, meaning that the expected value of $|p-q|$ is roughly proportional to $N^{\frac12}$.


BOOLEAN FUNCTIONS: generate a function $f: \{0, 1\}^n \rightarrow \{0, 1\}$ from a $n \times n$ S-Box I want to calculate the hamming weight of a S-Box using this formula:
$\text{hw}(f) = \sum_{x=0}^{2^n-1} f(x)$.
Where $f: \{0, 1\}^n \rightarrow \{0, 1\}$

My problem is that I don't know how to get the $f$-function.

I found that helpful paper: THE DESIGN OF S-BOXES. At Page 9 (18) boolean functions are described. But she only prints the truth table (Table 2.1) without describing her $f$-function. She only says $f$
is a linear function, therefore I think $f$ depends on my S-Box?

For example, if I have this $2 \times 2$ S-Box:

0    1    2    3
1    3    0    2

$00 \rightarrow 01\\
01  \rightarrow 11\\
10  \rightarrow 00\\
11  \rightarrow 10$

What are the $f$-functions and what is the hamming weight?

Your n x n S-Box can be seen as a set of $ n $ boolean vectors of size $ n $. Actually you have got $ n $ functions, each one is the truth table of one particular vector (or column).
In your example there are 2 columns thus 2 functions. For each column the number of 1's is 2.


Is OTP with homomorphic encryption trivial? If my key size is as large as the data I'm encoding, is it trivial to devise a theoretically secure homomorphic encryption scheme for integers (or else any finite/infinite group with order) that supports $+$ as an operation on encrypted data? Plus points if your scheme is computationally inexpensive or easy to understand.

Formally, $e(k,a+b)$ can be computed quickly  from $e(k,a)$ and $e(k,b)$ where $k$ is the key. Theoretically secure means it should be impossible to determine any $a_i$, given a large number of samples $e(k,a_i)$ unless $k$ is known. Also $e(k,a)$ shouldn't be constructible for known $a$ unless you know $k$

I tried coming up with an example, which I couldn't but it does appear quite doable.

A use case for this could be say secure online voting, wherein the vote count is a small data value but it would be good if the votes can be added in by servers who themselves don't have access to the vote count.

For encryption by a determinisitic function as suggested by the question's notation $e(k,a)$, "perfect security" as asked is not possible, because the homomorphic property allows to decipher many ciphertexts. In particular, if we know the encryption of $1$, we can use it to find the encryption of $2=1+1$, thus decipher the unique ciphertext for $2$, and that extends to every positive integer. Notice that One Time Pad encryption is not a deterministic function either (encrypting the same plaintext multiple times usually yields different results).

Here is a trivial scheme that is homomorphic and information-theoretically secure, in the sense that a ciphertext leaks nothing about the value it conveys, even to an arbitrarily powerful adversary.

Plaintext consists of $b$-bit bitstring, assimilated to integers in range $[-2^{b-1},2^{b-1})$ per two's complement. Everything is big-endian.
Key is a One Time Pad of $2^k\,b$ bits, enough for $2^k$ encryptions.
For encryption, it is consumed $b$ bits from the OTP/key, and these are added modulo $2^b$ with the plaintext. The ciphertext consists of that, followed with the encoding over $k$ bits of how many ciphertext(s) where produced previously.
Addition of two ciphertexts is the addition modulo $2^b$ of their first $b$ bits, followed by the concatenation of what remains.
Decryption takes the ciphertext, extracts the first $b$ bits as an integer, and from this repeatedly subtract modulo $2^b$ the $b$-bit integer at position $i\,b$ in the OTP/key, for each integer $i$ of $k$ bits parsed from the rest.

That matches all the question's explicit goals. Notice however that (as pointed by Ella Rose's comments)

Whether a ciphertext was generated by encryption (and then when in sequence) or homomorphically generated (and then how) is in clear in that ciphertext, and distinguishible from random, contrary to e.g. Paillier encryption where ciphertexts are computationally indistinguishable from random.
The homomorphic property creates a link between plaintexts when one is obtained homomorphically from another, and we correspondingly loose the information-theoretic property that leaking a plaintext leaks nothing about any other.

Extensions:

The limit of $2^k$ encryptions can be waived with a more complex encoding scheme for $i$, and of course an arbitrary-length key/OTP.
For some use cases, what follows the encrypted count can be compacted. For example, when adding vote counts, it makes sense to forbid adding the same encrypted count multiple times. That allows to use a bitmap of fixed size for what follows the encrypted count, and combine disjoint bitmaps with bitwise-OR. Regular bitmaps can be further compacted.


Compare two approaches for cracking RSA key I came across these questions while studying for a crypto course, does anyone have any ideas on how to answer these?

(a) Random prime numbers of size 1536 bits are chosen to generate
an RSA modulus of size 3072 bits. Knowing that the number field sieve
factorization algorithm would succeed in factorizing an RSA modulus of this
size in $2^{128}$ elementary operations on average, compare the two following
approaches for cracking this RSA key:

i. factorizing the modulus using the aforementioned number field sieve
factorization algorithm; or

ii. factorizing the modulus by enumerating candidate prime factors and
looking for one that divides the modulus.

(b) Same question as above, but this time the primes p and q that make up the
modulus n = pq are no longer randomly chosen, but derived deterministically
from a user-supplied password. (E.g., we can use a pseudo-random generator
to map the password to a pseudo-random number r of the right length, then
use primality testing to find the first prime that is greater than r.) Feel free
to make any reasonable assumption you need regarding the password.

For part(a.ii), I am presuming that "enumerating candidate prime factors" means that we have a precomputed list of all 1536-bit primes, which we can simply test one at a time.

To determine average running time we can use the prime number theorem, which states that the number of primes less that $N$ is approximately given by

$\pi(x) \sim \frac{N}{\ln N}$.

As such, there are approximately

$\frac{2^{1536}}{\ln 2^{1536}} = 2.24 \times 10^{459}$

candidate primes to test. In reality, division of numbers this large is not an elementary operation, but even assuming it were to be one, on average we'd need half that number's worth. I think it's safe to say that (a.i) is the better choice.

As for part(b), I'm may be getting confused, but what I believe this is stating is that our key is generated by taking an input password $p$ and using it to seed a PRNG. We then generate an output stream of 1536 bits, and then select the next prime greater than our output as the first prime? And I presume this implies that we have access to said password?

If so then on average we'll have to look at

$\frac{1}{2} \cdot \ln 2^{1536} \approx 533$

different numbers before we find a prime. We'll have to do this twice though, so that's a little over a thousand primality tests on average. So the speed is then dependent on the number of elementary operations in our testing algorithm and PRNG, but assuming modern constructs (say, ISAAC and Miller-Rabin) the candidate approach should work better.

Sorry if I understand the question incorrectly. It's not the best written.


Shamir Secret Sharing Scheme - some doubts not answered earlier my first question on here.

I've gone through some examples of Shamirs Secret Sharing Scheme, but I have 2 rather  pressing doubts -

i. Why do we choose the co-efficients of the polynomial from the set {1,..., p-1}?

ii. Why should we have p (the choice of prime) > n (total number of parties involved in the secret sharing scheme). I am able to reason why p > k but not the above!

Thanks very much in advance.

You need a finite algebraic object, resulting in exact arithmetic and exact recovery of the secret. So infinite fields such as $\mathbb{C,~R}$ are not suitable.

Since the scheme is based on polynomial interpolation, you need two operations, i.e., a field. It can be a prime field $\mathbb{F}_p$ or an extension field $\mathbb{F}_{p^m}.$

Since each user is assigned their secret by specifying $y_i$ at point $x_i,$ you need at least $n+1$ points, the value at zero of the polynomial normally being used for specifying the secret.


Constant size commitment to a bivariate polynomial In this paper by Kate et al, a constant size polynomial commitment scheme is described.

The commitment scheme assumes a public reference string:

\begin{align*}
\Big\{
\{ g^{ \tau^i }, g^{ \alpha \tau^i }  \}_{i=-d}^{d} \}, \ \
\{ h^{ \tau^i }, h^{ \alpha \tau^i }  \}_{i=-d}^{d}, \ \ e(g, h^{\alpha} )
\Big\}
\end{align*}

where $\alpha, \tau \in \mathbb{F}$ are two secret values and $d$ is a large integer. The commitment goes as follows:

Commit: let $f \in \mathbb{F}[x]$ with degree at most $d$. The commitment is a group element $F$ defined by
\begin{align*}
F := g^{\alpha f(\tau) }.
\end{align*}
To open the commitment to a certain value $z$, compute the proof $W$ which is another field element, defined by:
\begin{align*}
W := g^{ \frac{ f(\tau) -f(z) }{ \tau-z } }
\end{align*}
To verify a correct opening given $(F, z, (v, W) )$:
\begin{align*}
e(W,  h^{\alpha \tau}  )  \cdot  e(g^v \cdot W^{-z}, h^{\alpha} )  == e(F, h^{\alpha } )
\end{align*}

We note that the the commitment to the polynomial $f$ is constant size, as well as the proof of correct opening for a given value $z$.

My question is,

  Given the above reference string, or a similar reference string of roughly the same size (linear in $d$), is there a known constant size commitment scheme to a bivariate polynomial?

I think the main issue for the bivariate polynomials is the coefficients of the polynomial $f(x,y)$. Since $\tau$ is a secret value then to calculate $g^{\alpha f(\tau)}$ we can use the public parameters. As you know, the users can obtain the coefficients based on a standard basis and then solve a multiplication.
$$g^{\alpha f(\tau)}=\prod_{i=0}^{n}{(g^{ \alpha \tau^i })}^{f_i}$$
For a univariate polynomial, the coefficients of $f_i$ are constant while if we consider bivariate polynomials then it is necessary to evaluate a second polynomial on the $\tau$. Precisely, the standard basis $(1,X,X^2,...,X^d)$ forms the univariate polynomials and the coefficients for a bivariate polynomial are changing by the second variable.


Curve25519 function, scalar multiplikation This is the main paper for Curve25519. In section 2: Specification there is a important theorem. In this theorem Bernstein defines the function $X_0 : E(F_{p^2}) \rightarrow F_{p^2}$.

First Question: Curve25519 is a Montgomery curve and uses the projektive arithmetic, which only needs the x-coordinate. The defined functions makes a scalarmultiplication and then takes the x-coordinate from the result. Therefore why isn't it defined as $X_0 : E(F_{p}) \rightarrow F_{p}$? ( or $X_0 : F_{p} \rightarrow F_{p}$ )

Second Question: When making a scalar multiplication on a point of a elliptic curve, the result is always a point. So why is it defined as $X_0 : E(F_{p^2}) \rightarrow F_{p^2}$ and not as $X_0 : E(F_{p^2}) \rightarrow E(F_{p^2})$? One can say, that $E(F_{p^2})$ is not the x-value of a point. In this case, why is it not defined as $X_0 : E(F_{p^2}) \rightarrow F_{p}$?

I got the answer now! Curve25519 does not have key validation. Usually you have a point $P =(x,y)$ on a elliptic curve $E$ over $F_p$. But there is not a point $P$ on the elliptic curve for every value in $F_p$. If you make a key exchange with such a system, you will get a point, or a x-Value (using Montgomery x-only computation). Now you have to test, wether the given point is on the elliptic curve or not, because you can't calculate with a point, thats not on the curve.
Now as i said Curve25519 does not have key validation, because it takes time. But the theorem (in which $X_0$ is defined, too) in the paper about Curve25519 that says, that there is a Point for every x-Value over $F_p$. So you don't need key validation!
The bottom line of is, that you only need the extension field $F_{p^2}$, because you don't want key validation.


OpenSSL: How to maintain padding from encryption after decryption? One of my professors mentioned in class that there is a way of using PKCS#7 padding to have the padding persistent after decryption.

For example, if I encrypt a 20-byte file using

openssl enc -aes-128-ecb -in input.txt -out encrypted.txt -K 0123456789 -v

I obviously get the padded difference of:

bytes read   :       20
bytes written:       32

So 12 bytes of padding was added.

After decryption of the file, I want the padding to remain.

The only method I could think of was making the bytes in the original input.txt file the same character that PKCS#7 uses to pad, so that when it's time to unpad, it doesn't know what to unpad.  I haven't been able to find exactly which character it uses, or if it's not a character.  I've read some about the standard here and here, but with no real luck.

I'm still reading on it, but I haven't had any eureka moments yet.

An example of what I'm looking for would be if I gave it a 4-byte file such as:

AAAA

And it encrypted it, but added 12 bytes of C at the end, I'd want the decrypted file to be:

AAAACCCCCCCCCCCC

In OpenSSL there is an -nopad option. If you don't want the OpenSSL removing the padding bytes, add the -nopad option.

openssl enc -d  -nopad -aes-128-ecb -in  encrypted.txt -K 0123456789 -v -out decrypted.txt

Note that you cannot see as C because the OpenSSL doesn't print in hex.

To see in hex you can use xxd command

 xxd -r decrypted.txt

00000000: 3132 3334 3534 3334 3837 3433 3733 3838  1234543487437388
00000010: 3431 3431 3433 3436 410a 0606 0606 0606  41414346A.......

See, the 6 06 and the plaintext was

123454348743738841414346A

Note: Note: In PKCS#7 padding with 128-bit block cipher we don't see Cs, but we have 0C, 1C,2C,3C,4C,5C,6C,7C. What you mention is PKCS#5. See the difference in What is the difference between PKCS#5 padding and PKCS#7 padding


How was this Mersenne Twister seed for a 20-character string known a priori found? Someone generated a seed for the Mersenne Twister, with the intent of that seed producing this string:

"9!dlroW ,olleH"ck,@

Which is 20 characters long. Why he did it is explained below, but I don't know how he hacked it.

Why he did it:

The user feersum on Code Golf did this to generate a Hello, World! program in the Seed programming language. Obviously he didn't merely brute force his way to this seed, which is 4200 digits in length. How did he do this? Furthermore, this user has other answers in which he uses what is presumably the same trick, see: this answer.

What we know: The seeds tend to be quite large (much larger than if they were brute forced by addition-and-generation). Furthermore, every seed he finds must generate 624 integers with the seed before twisting the next 20 to produce the above string's numerical data. The complexity to brute force a string of n length is O(96^n), very complex indeed.

What I suspect: He filters what seeds he generates in such a way as to reduce the complexity for n length to about O(log(96^n)), which simplifies to O(1). I don't think that "he has access to a supercomputer" is a viable answer.

An acceptable answer: Anything which explains how he might have done this, even if he actually did it differently. It might take a long time for the answer to this to be known.

Interesting Mersenne Twister trivia: You can generate the state of the Mersenne twister with as little as 624 outputs, then predicting future output from it.

Note: Several bounties were pledged on the Hello, World! question for him if he were to explain how he did it. Years have passed, and he is not budging. Maybe those bounties will be passed on to you for having explained this.

How did he do this?

Actually, you gave much of it away when you mentioned:

  You can generate the state of the Mersenne twister with as little as 624 outputs, then predicting future output from it.

This is true, but you can do other things with it.  You can also generate previous output (that is, what the Mersenne twister output would be on blocks previous to the one you saw),previous states (that is, what the twister state had to be so that, after an iteration of the twister, you would get the selected state) and also compute the necessary seed to obtain a specific state.

Hence, most likely here's what he did:

Created an output of 624 integers, which consisted of the "9!dlroW ,olleH"ck,@ (which is 20 bytes or 5 integers), along with 619 arbitrary values.  These last 619 integers will be ignored, and hence it doesn't matter what values you select for them.
Reconstructed the internal twister state needed to generate this output.
Generated the previous twister state needed to generate this state after going through the twister permutation
Generated the seed needed to generate this twister state

And that's it.  The above is a bit tedious to do by hand; it'd be fairly trivial for a program.


Derive a key from a password and another key? I would like to encrypt some data using a password. I want to use a function like PBKDF2 to turn my password into a key. However, I would like to also require a keyfile, for added security.  My data should only be decryptable if I have the password and the keyfile.

What is the "best" way to do this?

From what I understand, I should not be using the salt for this purpose, correct? I.e. I could use the salt as my "key file", and the password entered by the user as the password, but most literature I can find does not recommend using the salt this way.

So the advantage of the keyfile in addition to the password is that it is basically a form of two factor authentication: You have a password (something you know), and a token (something you have).

The problem is that your salt must be available in order to derive your password based secret, which would mean your token (the salt) is not really separable from your password - this means you don't really have two factor authentication anymore, as the salt can't be separate from the password. So using the salt as the keyfile would not really improve security at all.

One way to accomplish what you are looking for is to generate your keyfile using /dev/urandom or equivalent to generate an appropriately sized token (128-256 bits). Then keep this keyfile on a USB drive. This way, whenever you need to access your secret, you require both knowledge of your password, and possession of the physical token.

After validating the password and keyfile, you could generate a single master key via something like hash(keyfile || password_derived_secret).


Decrypting message as MSB in regev scheme I was watching this FHE video and it define Regev encryption scheme as fallow :
kyegen:

sk : choose $t = (1,s)^t \in \mathbb{Z}_q^{n+1}$
pk = $A \in \mathbb{Z}_q^{m*(n+1)}$ random except $[A * t]_q$  small

Enc: for random $r \in \{0,1\}^m $ output and $\mu \in\{0,1\}$

$c \leftarrow (\mu,0,...,0).\frac{q}{2} + r.A$

Dec : compute
$$\langle c,t\rangle =  \mu.\frac{q}{2} + r.A.t = \mu.\frac{q}{2} + \; small \; (mod \; q)$$

Decrypt $\mu$ as MSB$([\langle c,t \rangle]_q)$

But i can not understand how decryption works? what i think is  for example for $q = 8$ if $[\langle c,t \rangle]_q \in [2,6)$ message is 1 and if $[\langle c,t \rangle]_q \in [6,8) \cup [0,2)$ message is 0 (if absolute value of small in $\langle c,t\rangle$ be less thatn $q/4$). I cant understand how the message would be MSB$([\langle c,t \rangle]_q)$ ? for example if we use 3 bits for each number MSb of both 0 and 3 would be 0.
Edit
responding to @kelalaka answer. beside $q$ being odd which is important but not very much what made me confused at first place was this section of Regev's paper. I think what you said is true when "small" bounded like $0<= small < q/2$. for example for $q = 7$ we have something like
$$000\\001\\010\\\\011\\---------\\100\\101\\110$$
and what i said when $-q/4<= small < q/4$ and depends on error distribution you choose at first place. but still not sure.
Edit 2 : actually it was kinda a silly question. for future reference if somebody(with low probability) came across this question. Homomorphic Encryption is a good paper from SHai Halevi, the guy in the video. and at secction 2.1    Notations and Basic Definitions you can find definition of $[\;\;]_q$ and much more.

You have some errors on the definition of the Regev's Scheme

Keygen($1^n$):

sk : choose $t = (1,s)^t \in \mathbb{Z}_q^{n}$ where $q$ is an prime between $n^2$ and $2n^2$
pk = $B \in \mathbb{Z}_q^{m\times n}$ random except $[B \times t]_q$  "small"

$Encryption(B,\mu \in \{0,1\}$:  For random $r \in \{0,1\}^m $ output and $\mu \in\{0,1\}$
$$c \leftarrow (\mu,0,...,0) \cdot \frac{q}{2} + r \times B$$

$Decrypt(c,t)$ : Compute

$$\langle c,t\rangle =  \mu \cdot \frac{q}{2} + r \times B \times t = \mu \cdot \frac{q}{2} + \text{ "small"} \pmod q$$

Recover $\mu$ as MSB$([\langle c,t \rangle]_q)$

Details

the secret key is a $n$ dimensional vector in $\mathbb{Z}_q^{n}$ where the first component is $1$

The public key is a matrix except that when you multiply with the secret key $t$ you will have a vector in $q$ that hash small values $[B \times t]_q$

The random $r$ is a bit vector of size $m$, $r \in \{0, 1\}^m$.

The message It is a bit, yes you encrypt either $\mu \in \{0, 1\}$, and  for a vector of size $n$, $(\mu,0,...,0)$

Encryption :

$$c \leftarrow (\mu,0,...,0) \cdot \frac{q}{2} + r \times B$$

Decryption :

\begin{align}
\langle c,t\rangle &= \langle (\mu,0,...,0) \cdot \frac{q}{2} + r \times B ,t\rangle\\
 & = (\mu,0,...,0) \cdot \frac{q}{2} \times t + r \times B \times t \\
 & = (\mu \cdot \frac{q}{2},0,...,0) \times t + r \times B \times t \\
 & = \mu \cdot \frac{q}{2}+ r \times (B \times t)
\end{align}
remember $[B \times t]_q$  was chosen as "small" and  $r$  was a bit vector. If you consider the final integer in $\mod q$.
$$\mu \cdot \frac{q}{2} + \text{"small"}$$
The "small" in the beginning is adjusted so that $r \times B \times t$ never exceeds $q/2$.
Now, calling the MSB on the result will provide the $\mu$ since $\mu \cdot q/2$ makes the MSB 0 or 1 depending on the $\mu$.
Correctness
The small term is also called the error $e$ term. The correctness requires that $|e| < \lfloor q/2 \rfloor /2 $

Note: I did not go to verify the example, since $q$ is so small to work. The bounds must be carefully controlled.
The below sageMath code is working, however, one needs to tune the "small", that is left!

q = 129 # n^2 < 129 < 2n^2
R = IntegerModRing(q)
n = 10 # vector size
m = 10 # random vector size

def randSecretKey(R, size):
    v = vector(R,sample(range(q), size))
    v[0] =1
    return v

def randPublicKey(R,m,n):
    m2 = random_matrix(R,m,n)
    return m2

def randomBitVEctor(R,size):
    v = vector(R,[randint(0, 1) for i in range(size)])
    return v

def smallPKSK(R,m,n,sk,q):
    trials = 0
    small = false
    while not small:
        trials += 1
        inrange = true
        pk = randPublicKey(R,m,n)
        c = pk*sk
        for i in c:
            if i > 50:
               inrange = false
        if inrange == true:
            print( "number of =", trials)
            return pk

def encodeMessage(R,bit,m):
    mu = zero_vector(R,m)
    mu[0] = bit
    return mu

def encrypt(R, q, mu, r, B):

    return mu * R(64) + r * B

def decrypt(R, c, t):
    return c*t

sk = randSecretKey(R,n)
print("\nsecret key = ", sk)

pk = smallPKSK(R,m,n,sk,q)
print("\nPublic key\n")
print(pk)

pk*sk

r = randomBitVEctor(R,n)
print( "r = " , r)

mu = encodeMessage(R,1,m)
print("mu = ",mu)

c = encrypt(R, q, mu, r, pk)

print("ciphertext = ",c)

p = decrypt(R, c, sk)

print("plaintext = ",p)
Integer(p).digits(2)


How to securely combine multiple sources of entropy? Suppose that I have $n$ secure 32-bit keys that were generated separately using methods that are known to be secure. For example, one of them might have been generated by using a proven CSPRNG. Another may have been generated using PBKDF2.

Now, I want to turn all of these keys, combined together in to a new key that I can use to encrypt and decrypt data.

The important thing is that I want to require all of the keys to be present in order to perform the encryption and decryption.

What I want to know is, what is the best way to combine these keys and maintain the highest level of security against attacks?

For example, I could just concatenate all the 32-bit keys and then run them through PBKDF2 again:

# pbkdf2(key, salt, iterations, derived_key_length)
# Also, "a + b" indicates concatenating a + b as strings, i.e. "hello" + " world" = "hello world"

new_key = pbkdf2(key1 + key2 + key3, some_salt, 10000, 32)

Or, instead of concatenating them, I could concatenate some of them in the salt:

new_key = pbkdf2(key1, key2 + key3, 10000, 32)

Or, I could iteratively run pbkdf2:

temp_key = pbkdf2(key1, key2, 10000, 32)
new_key = pbkdf2(key3, temp_key, 10000, 32)

Or, I could concatenate them all and hash them:

new_key = sha1(key1 + key2 + key3)

Or, I could iteratively hash them with concatenated versions of the previous hash:

a = sha1(key1)
b = sha1(a + key2)
new_key = sha1(b + key3)

Or, I could produce a hash using one of the above methods and then run that hash through PBKDF2:

hash = sha1(key1 + key2 + key3)
new_key = pbkdf2(hash, some_salt, 10000, 32)

Or, I could xor them all together:

new_key = xor(xor(key1, key2), key3)

Or, xor them all together, and then run though pbkdf2, etc. etc.

Clearly there are a ton of ways to combine these keys to produce a new secure key.

Is there any prior work on this? What is the best and most secure way to do this?

If any of the above methods are not secure, can you explain why?

P.S. As an additional aspect of this question, I am curious if the "password" or the "salt" are more or less secure places to put entropy. For example, are both of the following equally secure?

new_key = pbkdf2(key1 + key2, key3, 10000, 32)

and

new_key = pbkdf2(key1, key2 + key3, 10000, 32)

If your keys, taken together, have sufficient entropy to support your desired security level, then HKDF (paper) is a conservative solution here, because it assumes that the input keying material to the HKDF-extract might not be uniformly distributed.

The most conservative way of using it in your case would be to supply the concatenation of your keys as the IKM ("input keying material") parameter to HKDF-extract, and do not use the optional salt.  Then either use the PRK result directly, or as a further input to the HKDF-expand function.

A less conservative way of using it, if you are confident your inputs are indistinguishable from uniform random and mutually independent, would be to skip the HKDF-extract function supply the concatenated input directly to HKDF-expand.


Could there be a floating point CSPRNG? I recently answered no to Is there a floating point CSPRNG? Unpredictable rounding errors, especially across dissimilar hardware were my reasoning.

In it's most basic form, a CSPRNG can be constructed by securely hashing a randomly initiated counter. This is what happens inside the secure random function for Java. So if we can find a hash that operates with floating point numbers, we'd have a floating point CSPRNG as originally asked for.

The following abbreviated abstract is from this paper:-

  This paper shows how one of these systems can hash messages at
  extremely high speed—much more quickly than previous systems at the same
  security level—using IEEE floating-point arithmetic.

My problem is that I can't understand the working. It's all Greek to me, but I can spot multipliers of 0.98 , 2.2 and 1.01 which are clearly floating point numbers.

Was I wrong, and floating point CSPRNGs are actually possible if not common?

Clarification:  Some comments are appearing that are only relevant to a non deterministic RNG or generating floating point output.  The original question asked for a native floating point deterministic generator. So internally it should only work with floating point numbers, as does (I think) my linked paper. It's clarification of this last fact regarding the linked paper that I'm looking for as that would pave the way for a native floating point CSPRNG.

Addendum

I've now come across Uni64() which is a random number generator that uses double precision variables.  It's by George Marsaglia.  This is an extract of the initialisation:-

const double r=9007199254740881.0/9007199254740992.;
const double d=362436069876.0/9007199254740992.0;
static double c=0.; static int i=97,j=33; double x;

Without doubt, r,d and c are double precision variables.  So for example, r = 999.999999999987676524e-3 and d = 40.2384869730987304592e-6.  To be honest, I don't know what this means.  Is r meant to be 1 an I've rounded, or it this correct?  Not sure what d could be rounded to.

"the uni64() doubles have been multiplied by 2^53"

Is this the secret?  Rounding /accumulation errors do occur as expected.  But by shifting left 53 times, they effectively become part of the randomness in the lower significance bits.  What seems like random errors in precision become part of the randomness.  And if so, this would appear to be a floating point random number generator...

Floating-point arithmetic is just rounded arithmetic on a simple integer-based representation of a subset of real numbers.  Floating-point arithmetic is not unpredictable—on the contrary, it is extremely well-standardized in IEEE 754 (paywall-free), unlike, e.g., signed integer arithmetic which sometimes traps or wraps or behaves unpredictably in cases of overflow, shift of negatives, etc., depending on hardware, programming language, compiler, and operating system.
Every computer you are likely to encounter supports IEEE 754 arithmetic, and most of them will by default behave in exactly the same way (32-bit x86 with x87 FPU excepted, though configuring it to do IEEE 754 binary64 arithmetic is easy), giving bit-for-bit identical answers, for the most common arithmetic operations: addition, subtraction, multiplication, division, and a few others.  Floating-point arithmetic is typically very fast, is vectorized by many CPUs, and even usually turns out to be constant-time on finite normal numbers.
Specifically, a binary64 (or double-precision) floating-point finite normal number is a real number of the form $$2^e\cdot(1 + f/2^{52})$$ where $f$ is an integer in $\{0,1,2,\dots,2^{52} - 1\}$ and $e$ is an integer with $-1021 \leq e \leq 1023$.  There are a few other binary64 floating-point numbers, $\pm\infty$ and subnormals, and there are also floating-point values that are not numbers, namely NaN values, but they're not likely to matter for cryptographic applications.
The basic arithmetic operations are defined so that for any floating-point numbers $x$ and $y$, $x \oplus y = \operatorname{round}(x + y)$, where $\oplus$ is floating-point addition and $\operatorname{round}$ yields the floating-point number nearest to the real number $x + y$, or the floating-point number with least-significant significand digit zero in the case of a tie.  (Yes, you can configure other rounding modes, but by default this is the one you will get.)
There are subsets of floating-point numbers on which $x \oplus y = \operatorname{round}(x + y) = x + y$.  For example, the set of integers in $[-2^{52}, 2^{52}]$ have this property.  The hash127 paper you cited uses this property to reliably compute integer arithmetic modulo the large prime $2^{127} - 1$ using floating-point arithmetic on an eight-digit representation $t_7 2^{112} + t_6 2^{96} + \cdots + t_1 2^{16} + t_0$, where each term $t_i 2^{16i}$ is represented by a floating-point number.
Floating-point rounding is reliable enough that you can use it to mask off the top or bottom bits of an integer, e.g. to get the limbs $t_i$ in the above form.  For example, let $x = \text{0x896da38f}$, or 2305663887 in decimal.  Suppose you want to compute $y = x \mathbin\& \text{0xffff0000} = \text{0x896d0000}$, i.e. mask off the bottom sixteen bits of $x$, using binary64 arithmetic, which has 53 bits of precision.  You can add a sufficiently large number that the bottom sixteen bits get rounded away, and then subtract it: $(x \oplus 3 \cdot 2^{16 + 53 - 2}) \ominus 3 \cdot 2^{16 + 53 - 2}$ gives $2305622016$ in decimal, or $\text{0x896d0000} = y$ as intended.  Here $3 \cdot 2^{16 + 53 - 2}$ is a binary64 floating-point number already, so it can be represented exactly, and $\oplus$ and $\ominus$ are floating-point addition and subtraction in the default rounding mode.
However, while floating-point arithmetic can be reliably exploited for fast constant-time vectorized integer arithmetic, what floating-point arithmetic does not provide is bitwise operations or Galois field arithmetic.  For example, there's no easy fast way with floating-point arithmetic to compute $f + g$ for degree<=32 polynomials $f, g \in (\mathbb{Z}/2\mathbb{Z})[x]$ or two elements $f, g \in \operatorname{GF}(2^{32})$—also known as 32-bit xor.
So while you can do integer arithmetic and mask off chunks of an integer at a time with floating-point arithmetic, manipulating individual bits is tricky, and manipulating them in parallel as vectors is even costlier, whereas integer units in CPUs do it nearly effortlessly.  Thus it would be hard to compute, say, the Keccak or Salsa20 permutations fast with floating-point arithmetic—Keccak probably even harder than Salsa20, because at least Salsa20 has some 32-bit integer addition that could take advantage of a floating-point adder.
Could you use floating-point arithmetic to build a CSPRNG?  Sure—you could even implement Keccak or Salsa20 using floating-point arithmetic, and you might even conceivably want to do that in some contexts such as Python in which integer arithmetic is notoriously leaky due partly to the small integer cache (if for some reason you couldn't just write a C extension).
Would it beat speed records for existing CSPRNGs at a comparable standard security level?  Probably not, and any cryptanalysis of it would no doubt be based on the bit-string-to-bit-string functions just like any integer- or bit-based CSPRNG rather than any numerical analysis.
(I'd guess the floating-point representation would probably just make the analysis more irritating, so it would get less scrutiny.)
Note that the ‘hash’ of hash127 does not mean fixed preimage-resistant hash function like MD5 or SHA3-256.  Rather, like Poly1305, hash127 is a universal hash family (paywall-free; Wikipedia)—specifically, hash127 a family of functions $H_r$ indexed by $r \in \mathbb{Z}/(2^{127} - 1)\mathbb{Z}$ with difference probability $\Pr[H_r(m_0) - H_r(m_1) = \delta]$ over uniform random $r$ bounded by $\ell/2^{128}$ for every difference $\delta$ and all messages $m_0$ and $m_1$ up to $\ell$ bytes long.


Password hash that can be upgraded without plaintext password Most password hashes have a cost parameter that indicates how long the algorithm should take. Is there an algorithm where you can increase that cost for a particular hash, without access to the plaintext password?

So I have existing hashes in the database with cost=10, and I want to upgrade these to cost=20, without access to the plaintext password.

This isn't possible for PBKDF2 and bcrypt, because these use the password in each iteration. Is there any algorithm that supports this? Is there a specific name for this property?

This is called Client-Independent Update, according to the
Catena paper.

  It is desirable to be able to compute a new password hash (with some higher security parameter) from the old one (with the old and weaker security parameter), without having to involve user interaction, i.e.,
  without having to know the password. We call this feature a client-independent update of the password hash.

The Rig password hash adopted this term:

  Client-independent update: Our design supports client independent
  update, i.e., server can increase the security parameter without knowing the password.

This article even shorts it to CIU.

Battcrypt and Parallel have CIU or are easily modified to have it.
POMELO mentions that you could just run the algorithm twice to get CIU.
Yescrypt seems to have CIU.

An overview:


Does observing amount of changes in encrypted disk ciphertext have a well-known attack name? Let us assume that I have two partitions on my hard disk, and unencrypted one and an encrypted one. Let us also assume that I shut down the computer when sleeping or away, and an attacker has physical access to my computer. In fact, the attacker takes a copy of the disk image every day without me knowing it. Obviously, the attacker does not know the passphrase of the encrypted disk partition, so the attacker can only observe changes in ciphertext (let's assume now that the attacker doesn't know that keyloggers exist or doesn't want to take the risk of me noticing it).

Now, there's a particular 100 MB file that is a copyright and trade secret violation. I don't want to delete it, but I'm becoming slightly suspicious that my computer is used without my permission, so I store it into the encrypted partition, deleting it from the unencrypted partition.

Now, the attacker will observe that 100 MB of the ciphertext of the encrypted partition differs from the old ciphertext. In fact, from the daily disk images, the attacker sees that the amount of changes in the encrypted disk is usually zero, and this was practically the only exception for that. The attacker will also observe that the 100 MB file was deleted from the unencrypted partition. Thus, the attacker concludes that I still have the file.

My question is: does this kind of attack against full disk encryption have a name? Do any full disk encryption schemes offer resistance against this kind of attack, e.g. by randomly rewriting blocks with a new per-block key even if no plaintext block actually changed?

I'm not sure about a formal name but I can comment on your other questions. A lot depends on the level at which you do the encryption. There are three main approaches I'm aware of:

The disk data itself is encrypted,
The file system encrypts data stored in it but is itself stored in plain text on the disk (e.g. CryFS),
Individual files are encrypted but directory structure and file system level meta data (size, timestamps, etc) is not (e.g. EncFS). This is basically what ransomware does.

Generally speaking, none of these approaches encrypt an entire disk worth of data as one long cipher text. They break it down to some degree, whether by sector (in the case of 1), by file (in the case of 3) or arbitrary chunks (in the case of 3). There's a practical reason for this: all the cipher text within an encryption unit (block, sector, chunk, file, etc.) should change if any part of it is changed. If your entire disk were one encryption block then simply viewing a file (modifying the access time) could result in the entire disk being rewritten.

You can generally assume that an OS will put some metadata onto a disk as soon as it's mounted (and maybe even periodically) so the cipher text will change from day to day. However, it won't be the entire disk that changes, just certain portions that become predictable to a diligent observer after a while.

Now...the disappearance of 100MB of clear text coinciding with the appearance of 100+MB (a sane disk encryption system will have data authentication overhead) of ciphertext is a pretty strong indicator that you encrypted the sensitive file. There are things that will complicate this depending on the exact scheme used. First, the amount of change on the encrypted partition will be rounded to the smallest encryption unit (which can be quite large). Second, if a scheme does not store your new file contiguously (is fragmented, intentionally or unintentionally) then significantly more than 100MB of new ciphertext will be created/changed. The last factor can make it much more doubtful whether the sensitive file has just been encrypted but does not apply at all to scheme #3.

Of course, if the attacker is aware of the scheme you're using and are only missing the key then they'll know with high confidence that you simply moved the file. The only way I can think of that would make it doubtful whether you still have the file is if you were able to store the file in a different form by:

compressing it to reduce the written size
padding it arbitrarily to increase the size

You would still have the timing signal though. That is more an operational issue than anything. You have to avoid unlikely coincidences like that if you are to be able to meaningfully use the encrypted partition in a hostile environment. Even if the file weren't on the other partition, the release of a controversial file online coinciding with the appearance of a similar amount of cipher text on your partition is quite revealing.

You could have a script randomly creating, deleting and touching files, rotating encryption IVs, moving data across block boundaries, etc so you end up with a few hundred MB of changed ciphertext daily without anything really happening from your perspective. If you're clever enough you could have this system gradually create an opening for your sensitive file through various blank hidden files and then slowly "garbage collect" this back into one contiguous file again over time. You'd have to be exceedingly clever to have this process not become a side channel for information about the clear text of the partition though.

P.S.: If someone has a way of extracting an entire disk image on a regular basis without your knowledge it's probably just as feasible for them to replace it with a file system that's more convenient for them (think "decrypts on mounting then only pretends to encrypt thereafter") just as discreetly.


Is there an upper bound to the private exponent in RSA? In the RSA algorithm, we choose $p$ and $q$ as prime numbers and we select a value $e$ which is coprime to $\varphi(pq)=(p-1)(q-1)$.

Then we calculate $d:=e^{-1}\bmod\varphi(pq)$.

My question is: What could be the maximum value of $d$? Is there an upper bound to it?

Mathematically speaking, there is no upper bound on the private exponent in RSA: assuming $d$ is a valid private exponent, then the valid exponents are the set of $d'=d+k\cdot\lambda(p\cdot q)$ with $k\in\mathbb Z$, where $\lambda(p\cdot q)=\operatorname{lcm}(p-1,q-1)$ since $p$ and $q$ are distinct primes; this set is unbounded.

If you compute $d$ as an integer with $d\equiv e^{-1}\pmod{\varphi(p\cdot q)}$, then by definition $d$ verifies $e\cdot d-1$ multiple of $\varphi(p\cdot q)$, and is unbounded. If you compute $d$ as the integer $d=e^{-1}\bmod\varphi(p\cdot q)$, by a common definition of that notation, $d$ is additionally non-negative and less than $\varphi(p\cdot q)$, which is then an upper bound.

In practice, available memory and time, existing software, or standards, limit the value of $d$. A most common standard, PKCS#1, requires $0<d<n$; the FIPS 186-4 standard requires $2^{\lceil\log_2(N)\rceil/2}<d<\operatorname{lcm}(p-1,q-1)$; some implementations allow $0<d<256^{\lceil\log_{256}(p\cdot q)\rceil}$; $d\ge\varphi(p\cdot q)$ is unusual.


Using HMAC-SHA256 with short passwords and sliced outputs for short-lived secure hashing I don't have much background in cryptography, so forgive me if I'm using the wrong mathematical terms to explain my needs.

Following this question, I learned that taking a random secret 16-bytes password and some random 16-bytes msg, and calculating output = HMAC_SHA256(password, msg), it will take an attacker that knows output and msg an unreasonable amount of time (more than 20 years) to restore password, or even to find a different password (say password2) that gives a collision, i.e. the same output for HMAC_SHA256(password2, msg).

What would happen if I use a shorter password of 14 bytes (and the attacker knows that)? How much time would it take the attacker to find password or a colliding password2?

What if I slice the output and save only output[:14]? How much time would it take the attacker to find a colliding password2 such that:
output[:14] = HMAC_SHA256(password2, salt)[:14] ?

What about less than that, like 12 bytes or 10 bytes?

The hashing mechanism should be "unbreakable" for a really short time of only 1 minute - the final purpose is creating a hash-chain for an OTP with a dumb client that stores the whole list and each minute sends the previous "password" in the list (its hash gives the "password" that was sent a minute ago).
The memory on the client is limited (every byte counts), but I don't want it to make complex calculations than a lookup from an array.

According to my uneducated estimations, a 2 bytes shortening (to 14 bytes) means it would take at least $\frac{20}{2^{16}}$ years, which is around 2.7 hours. Am I right?

Thanks

--- New Estimations ---

Using a 14-bytes password for life time of 1 minute shouldn't be a problem. If an attacker had an algorithm to recover 14-bytes passwords in a minute, he could develop an algorithm to recover 16-bytes passwords in 65536 minutes (brute force the extensions), which is around 45 days (much less than 20 years).

Slicing the output is shouldn't be a problem even when it comes to finding collisions.
There are 65536 times more collisions that would match output[:14] than the full output, so it would be 65536 times "easier" to find one (i.e. $\frac{20}{2^{16}}$ years $\approx 2.7$ hours).
Saying that the password is 14-bytes is equivalent to saying that it is a 16-bytes password that ends with \00\00 (this is how HMAC treats short passwords anyway). This will only make it harder for the attacker to find a collision, because the collision must end with \00\00 too.

Does anyone disagree?

-- Newer Estimations --

Bad news - The output of HMAC_SHA256 is 32 bytes long, not 16!
Slicing the output to 14 bytes would make it $2^{8 \cdot (32-14)}$ times easier to find a collision ($\frac{20}{2^{144}}$ years $\approx$ no time at all).
Hmmm... right?

It is very hard to estimate time it takes for attacker to brute-force password.
This is because HMAC-SHA256 can be calculated billions of times per second on some devices, and there are some devices existing which take millisecond to calculate one  HMAC.

BTW, I understood that password is actually a 128-bit cryptographic key, i.e. it can may contain any bytes, right? Usually term password is used for something that is much weaker.

If your adversary has thousands of high-end GPUs or dedicated ASIC chips, it is amazing how many passwords they can try. For this reason, it is very hard trying to estimate how strong is strong enough.

Earlier very good answer from T. Pornin to question on brute-forcing: Cost of brute-forcing AES-128. Although AES-128 is different algorithm than HMAC-SHA256(128 bit key), similar formula can be used to estimate costs. Short answer: if password is 16 truly random bytes, you would not break it even if you had all the money in the world.

The output of HMAC-SHA256 indeed is 32 bytes. Should you truncate it, depending on how you use HMAC, you may risk collisions. When the HMAC is used as MAC (message authentication code), it is in fact almost customary to truncate the output. (HMAC-SHA256-128 i.e. truncated to 128 bits is quite common.) If you use it in some "hash-like" application, or if you use the function vary many times, the 128 bits is indeed below what is recommended due to the birthday effect.

BTW, when working with time estimate like 20 years, you need to remember that processing power double every two years or so (Moore's law). For that reason, if something takes 20 years, large part of processing is done within the last three years. Also, 20 years may expect that there will be some new ways to crypto analyze SHA256 can be found during the time frame (but not full break.).


What is hardened SHA-1, how does it work and how much protection does it offer? From the shattered website:

  You can use the online tool above to submit files and have them checked for a cryptanalytic collision attack on SHA-1. The code behind this was developed by Marc Stevens (CWI) and Dan Shumow (Microsoft) and is publicly available on GitHub.

  It is based on the concept of counter-cryptanalysis and it is able to detect known and unknown SHA-1 cryptanalytic collision attacks given just a single file from a colliding file pair.

And later:

  Is Hardened SHA-1 vulnerable?

  No, SHA-1 hardened with counter-cryptanalysis (see ‘how do I detect the attack’) will detect cryptanalytic collision attacks. In that case it adjusts the SHA-1 computation to result in a safe hash. This means that it will compute the regular SHA-1 hash for files without a collision attack, but produce a special hash for files with a collision attack, where both files will have a different unpredictable hash.

finally from the GitHub pages - which I assume is called "hardened" SHA-1 above:

  ... More specifically they will detect any cryptanalytic collision attack against SHA-1 using any of the top 32 SHA-1 disturbance vectors with probability 1:

I(43,0), I(44,0), I(45,0), I(46,0), I(47,0), I(48,0), I(49,0), I(50,0), I(51,0), I(52,0),
I(46,2), I(47,2), I(48,2), I(49,2), I(50,2), I(51,2),
II(45,0), II(46,0), II(47,0), II(48,0), II(49,0), II(50,0), II(51,0), II(52,0), II(53,0), II(54,0), II(55,0), II(56,0),
II(46,2), II(49,2), II(50,2), II(51,2)

What precisely are these vectors? Could there be other vectors that are vulnerable? How much protection does "hardened" SHA-1 offer?

Hardened SHA-1 detects collisions built of a certain form, If someone were to find a collision using brute-force birthday attack (currently not feasible) the detection would not work.

The vectors are specific small differences which may help to convert a near collision into a full collision.

The details are in the paper: https://marc-stevens.nl/research/papers/C13-S.pdf

This will detect an attack which has a similar construction to the attack performed. Future cryptanalysis may however lead to other forms of attack. It is worth mentioning  any hash function that is may be vulnerable to new kinds of attacks though. SHA-3 may also be vulnerable to attacks that are yet unknown.

Hardened SHA-1 tries to be identical to SHA-1 almost all the time with a probability of differing in honest usage of less than $2^{-90}$. Yet it should be resilient to attacks by detecting them and changing the output to something that differs.

SHA-1 has been collision free until very recently. Hardened SHA-1 should be secure in this regard; much more secure then SHA-1. It is obviously better than thoroughly broken options such as MD5.

Hardened SHA-1 tries to be backwards compatible with SHA-1. If you don't need this backward compatibility don't use it, use SHA-3 or SHA-2, even if you have to truncate to 160 bits.


Are HAIFA-construction based hash functions (e.g. Argon2) resistant to length-extension attacks? Would a HAIFA-construction based hash function like Argon2 resistant to length-extension attacks?

I say that Argon2 is HAIFA-based because BLAKE is, and Argon2 is based on BLAKE.

Yes.

The HAIFA construct as introduced in A Framework for Iterative Hash Functions - HAIFA by Eli Biham and Orr Dunkelman is proposed with the explicit goal of eliminating various pitfalls of the classic Merkle-Damgaard construct.


1-2 Oblivious Transfer - Can the recepient obtain both secrets by manipulating v? Refer to the chart on 1-2 oblivious transfer : https://en.wikipedia.org/wiki/Oblivious_transfer
I'm Bob, I know N,e,x0,x1. Can I send Alice a v value that, by knowing the m'0,m'1 received, I can crack both m0 and m1?
Thank you

Can I send Alice a v value that, by knowing the m'0,m'1 received, I can crack both m0 and m1?

One would hope not; if Bob can, this would show that the proposed protocol does not meet the security requirements of an OT protocol.
However, in this case, selecting such a $v$ value would appear to be difficult.  What Bob would need to do is find two values $y, y'$  that map to two values with an Alice specified difference, that is, $y^e - y'^e = x_1 - x_0$.
If Bob can do that, we can learn both values (by setting $v = y^e + x_0$.  Conversely, if he knows a value $v$ for which he can learn both secrets, he can compute such a $y, y'$ pair, hence this reformulation of the problem is tight.
However, the mapping $x \rightarrow x^e$ acts unpredictably (if you don't know the factorization); there is no known way to find such a pair for a random difference $x_1 - x_0$.


What curve and key length to use in ECDSA? I'm developing a client/server system in Java which is not interacting with third-party software, so I don't have to worry about compatibility.
At a certain point, I need the client and server to exchange a digitally signed value. I thought to use ECDSA, but I'm not sure what curve and what key length should I use. I'm mostly worried about the security rather than the computational time or the length of the signature.
I'm using BouncyCastle for security-related operations, so the curve and key length must be supported by it. Here you can find a list of curves supported by BouncyCastle.
Do you have any advice?

SafeCurves lists some ways to compare the security of elliptic curves. Their security criteria are split to "ECDLP security" and "ECC security". Failing the former basically means "there is no way to use this curve securely in general" while the latter "it is difficult to implement this curve securely".

None of the (few) BouncyCastle-supported curves that have been looked at on SafeCurves pass all the criteria. Some fail the "rigidity" ECDLP criteria, which means that there is no way to show that the parameters haven't been chosen so there is a backdoor. If you fear that e.g. NSA has backdoored ECC, you should avoid those curves.

The one that does best is brainpoolp384t1. If passes all the ECDLP criteria as well as having twist security. That means it is the easiest to correctly implement. The other Brainpool curve they've looked at, brainpoolp256t1, also passes all the ECDLP criteria and so can be implemented securely. Without knowing anything about BouncyCastle's implementation, it is impossible for me to know whether the former curve has an advantage or even if both are in fact broken.

Regarding key length, there are various recommendations by different parties. They mostly agree that 256 bits is enough through at least 2030. So either of the two Brainpool curves I mentioned above would fit the bill. 384 bits is enough for Top Secret according to NSA.

In short, then, brainpoolp384t1 would be a conservative choice, since you don't care about computational time or space usage. That's not to say any of the others are bad choices, or that some other curve (e.g. one of the 512-bit Brainpool curves) isn't even better.


are outputs of sha256 independent when padded with different seed each time, in other words, when inputs can be somewhat related So I was wondering about what will be the dependence of the outputs when I padded one input with two different strings two times for technically generating two different strings, say the input string is 123 and the first time I have padded 12 before 123 $$H(12\mathbin\|234)$$ and next time I have padded '24' before '123' $$H(24\mathbin\|234).$$  Can I safely deduce that the outputs are completely independent even if the inputs are somehow related?
Asking this because I don't completely know the internal mechanisms of sha256 and how they are hashing stuff like this. I have good ideas about universal hash functions but kind of ignorant of cryptographic hash functions. So I have something developed using 3 wise independent hash functions but I am trying to shift everything using sha256 and in order to prove a lot of theoretical part concepts, I was looking for answers like this. I was looking for some sort of rigorous math proof/conceptual proof in this regard. Would appreciate any sort of help.

You are making a domain seperation with a prefix, and that is very common in random oracles (RO) instead of initiating another RO, one can use domain separation to use only one RO. Since the RO are like hash functions the same idea is used in the hash functions, too. That is the correct term and the correct way.
We expect that SHA256 outputs are indistinguishable from uniformly random.
Also, we expect that SHA256 ( like any cryptographic hash functions) has the avalanche effect;

a one-bit change in the input bits flips each output bit with a 50% probability. So some bits flip some bits doesn't.

If hash values with the prefixes are not independent there will be lots of problems for the used hash function. Also, consider that due to the padding, there are already lots of similar parts at the end of each message that didn't cause dependency.
One might note that SHA256 is vulnerable to length extension attack ( not only SHA256 though), but this may also be a problem for your scheme or not. Assume you have $h= \operatorname{SHA256}(12\mathbin\|234)$ then the attacker can use the output hash $h$ as the initial value for $\operatorname{SHA256'}(h,\text{extension})$ where this function controls the initial values of SHA256, then they can extend the message with a different hash value without knowing the prefix or the message. If $h= \operatorname{SHA256}(\text{prefix}\mathbin\|234)$ is used for MAC, although the attacker cannot produce the same output for the extended message, they can inject the extended message to execute a forgery.


How constant value 0x63 in affine transformation is chosen or generated while AES Substitution Box is formed? Me and one of my friends are working on AES algorithm. We have understood how multiplicative inverse table is generated. Rijndael AES algorithm shows us how S-Box is generated through the affine transformation process. In the original algorithm they have multiply each byte of the state with an constant matrix and then add the result with another constant byte which is 0x63 to get the substitute value. We have understood how the constant matrix is generated as there is a formula to generate it but couldn't find out why 0x63 constant value is chosen. We have already gone through many resources but could not find any appropriate solution. Can any one help us in this regarding issue?

According to the Rijndael AES proposal (emphasis mine):

  We  have chosen an affine mapping that has a very simple description per se, but a complicated algebraic expression if combined with the ‘inverse’  mapping. It can be seen as modular polynomial multiplication followed by an addition: $$b(x) = (x^7 + x^6 + x^2 + x) + a(x)(x^7 + x^6 + x^5 + x^4 + 1) \mod x^8 + 1$$ The modulus has been chosen as the simplest modulus possible. The multiplication polynomial has been chosen from the set of polynomials coprime to the modulus as the one with the simplest description. The constant has been chosen in such a way that that the S-box has no
  fixed points (S-box($a$) = $a$) and no ’opposite fixed points' (S-box($a$) = $\bar a$).

I'm not personally aware of any other design considerations in the choice of the additive constant 0x63, although it's worth noting that it does have a fairly nice and simple binary representation (0x63 = 0b0110 0011), which might perhaps simplify some implementations slightly.


can we know the sign of a ciphertext (homomorphic) Is it possible to know the sign (positive or negative) of an homomorphic ciphertext particularly under paillier scheme ?

Pallier encryption works over the finite ring modulo $n^2$.  The distinction between positive and negative numbers don't exist there (or in any finite ring or field), so there isn't really a sign that works like the sign of integers.
Of course you can use signs in the notation, e.g. $-1$. But that is just the same element as $n^2-1$. Both represent the same residue class modulo $n^2$.


What is the largest key size that could be carried by a shuffled deck of playing cards? If you are carrying a standard 52 card pack of cards (no jokers) what is the largest key size, or the amount of data the cards can hold?
Without the cards being marked or distinguishable from an identical pack, but some cards may be placed in the deck upside down.

Any set of $N$ distinguishable objects can be permuted in $N!$ different ways, thus giving you the ability to represent $N!$ different keys, resulting in a representable keylength of $\log_2(N!)$ bits. For $52$ distinguishable playing cards, this would be $\approx 225$ bits.

However with the additional property, that each object can have two distinguishable states -- a card can be face up or face down in the deck -- we can encode one additional bit of Information per card, since for each permutation there are $2^N$ different configurations. For your $52$ playing cards with the two states "face up" and "face down" you can thus represent $52!\cdot 2^{52}$ many keys, or a key length of $277$ bits.


Does piping MT19937 random stream into SHA512 make the state of MT unrecoverable in practice? It's well known that state of a Mersenne twister is quite easy to recover after you observe enough samples. But what happens if we pipe blocks comming out of MT into SHA512 and give this as output.
Since there is no mathematical proof that SHA512 is not invertible there probably wouldn't be a way to proove that MT state recovery in this scenario is impossible.

Is there any real practical way to obtain the MT state in this setup and hence be able to predict next blocks?
Or maybe prediction is somehow possible without state recovery?
I have read that there are CSPRNG designs that use an MT generator internally. Do they work like this, just take an MT stream and obfuscate it in some way or are they completely different?

Thank you!

The main issue would be the MT seed size. MT has a large enough state, but the seed is generally just a 32 bit word $w$. See here for more information.
SHA on the output won't guard you from a brute force attack on the seed; an attacker can just try and generate the stream and perform the SHA calculations and compare.
So you need to somehow extend the seed size and initialize the state. The state is pretty large and MT has a large period, so the plumbing is already there. If you can then just call it MT is the obvious next question.

Is there any real practical way to obtain the MT state in this setup and hence be able to predict next blocks?

Yes, as the initial state is derived from a generally small seed.

Or maybe prediction is somehow possible without state recovery?

I don't see that happening, but if you can retrieve the initial state, then you don't need to go there.

I have read that there are CSPRNG designs that use an MT generator internally. Do they work like this, just take an MT stream and obfuscate it in some way or are they completely different?

I haven't heard of them, but if they don't allow for a large seed as input, then they're in trouble.

The final question is indeed if you have gained anything when you're finished. Plenty of DRBG's based on hash functions exist, and adding a fast PRNG at the backend may not make much sense. The large state would not sit well with many cryptographers and secure software / hardware developers either.


XOR cipher with three different ciphertexts and repeated key, key length known. How do I find the plaintexts? Let us say we have three different plaintexts (all alphabets, A-Z): $x$, $y$ and $z$, each of length $21$. Let the key, $a$, be also of length $21$.

Now, what we have is $x \oplus a$, $y \oplus a$ and $z \oplus a$. How can we find out $x$, $y$ and $z$ from this?

I have looked around the web and found that the usual way to break this is to do statistical analysis and dictionary attack on the values of type $x \oplus y$ which we can get from ${(x \oplus a)} \oplus {(y \oplus a)}$. I used xortool for this and the key which I got from it gave random garbage for the plaintexts and so, that didn't work.

I cannot help but think that since we have three different ciphertexts (as opposed to just two which are used in most dictionary attacks), we must have some extra constraint that  we can impose on the possible set of keys but I'm coming up short. Any help is appreciated. If you can provide links to any tools, that would be great as well.

You're using bytewise xor, and three plaintexts $x,y,z$ with a small alphabet (A-Z, which I assume means ASCII values 0x41-0x5a). Then knowing $a \oplus x$, at a certain index, we know all possible values of $a$, at that same index, namely $\{0x41 \oplus (a \oplus x),\ldots, 0x5a \oplus (a \oplus x)\}$. But we have 2 more constraints from $a \oplus y$ and $a \oplus z$ at that index. The intersection of these three sets is the set of options for $a$ at that index. This already reduces the options at each index, probably.

Then you have to use probable plaintext, say 'THE' (if you have English text). You can try 'THE' at all positions as part of text $x$, compute $a$ on these corresponding places, and then compute $y$ and $z$ as well. Check whether the results look like (parts of) English words, and try to extend words in those other texts. Also try 'THE' in texts $y$ and $z$ in all positions. You can immediately abort all attempts where $a$ is not in the sets we computed above. Google "reading in depth". With three texts this should give pretty fast results. All of this is easily automated.

Doing statistics only on 21 characters will not get all the way, I think. You do need some idea of the language for the plaintext, etc.


can a key be applied to half the cipher text id like to ask if we encrypt the word "hello" as "olleh" but then we apply the key to only "oll" will it be converted into its orginal form i.e "llo". this was just for example. another thing id like to as is that how much time would it take to encrypt a 1.6 mb file with an average encryption algorthm. in seconds or miliseconds. like half a second?

can a key be applied to half the cipher text

Stream ciphers or Block Cipher with CTR mode can do so.

  how much time would it take to encrypt a 1.6 mb file with an average encryption algorthm. in seconds or miliseconds. like half a second?

It depends on hardware (CPU, speed of the driver, etc), software (OS, the programming language, etc) and the algorithm; but 1.6M Bytes should not take 0.5 seconds.

For example:

With the AES-NI, AES(ECB) can encrypt 2G+ Bytes/s with G4500 using Java, Windows 7;
without it, AES(ECB) encrypts around 120M Bytes/s with G2020 using Java, Windows 7.
Twofish encrypts around 110M Bytes/s with G2020 using Java, Windows 7.
Idea encrypts around 65M Bytes/s with G2020 using Java, Windows 7.


Better truncate a CMAC from MSB or LSB I want to truncate an AES128-CMAC from 16 down to 8 bytes length.
Citing RFC, "[...] It is possible to truncate the MAC. The result of the truncation should be taken in most significant bits first order. [...]".

When using CryptoJS to generate such a CMAC over "Hello World" using the key "0xDEADBEEF CAFEBABE DEADBEEF CAFEBABE", this yields: 0x2425a8ff 14cea36d 0a14b3e8 3dbfc68e.

I am not sure, whether my truncated CMAC according to the afore-mentioned definition is either 0x2425a8ff 14cea36d or 0x0a14b3e8 3dbfc68e.
Or in other words: Is 0x24 of the CMAC the most- or least-significant-byte?
How does it affect security when taking the wrong 8 bytes?

Since 8 is half of 16, there are alternative solutions whereby you use both upper and lower bytes but still get 8 bytes out.

XOR adjacent pairs of bytes.
Fold the MAC, XORing 1st and 9th bytes etc.

These techniques are good for when you just can't decide which byte you like best and only take a few lines of code...


Possible ways to crack simple hand ciphers? We had a quiz in class today where we had to break the ciphertext with the key given, but not the algorithm. Suffice to say that I wasn't able to decrypt it within the allotted time of 12 mins and will probably get a 0% score on the quiz.

So, I was just wondering if there are some kind of standard techniques that are followed when decrypting a simple substitution ciphertext.

When trying to break an unknown cipher, one first needs to figure out what kind of cipher one it is.  Generally, a good starting point would be to start with the most common and well known classical ciphers, eliminate those that obviously don't fit, and try the remaining ones to see if any of them might work.

An obvious first step is to look at the ciphertext alphabet: does the ciphertext consist of letters (and if so, in what alphabet), numbers, abstract symbols or some combination of those?  If it's letters, does it include spaces, punctuation or case distinctions — and, if it does, do they look like they're also scrambled somehow, or are they perhaps just left as they are in the plaintext?

Compiling a letter (or symbol) frequency table of the ciphertext, and comparing it to the corresponding table of plain English text, can often yield information about the general type of cipher one is dealing with:

If the ciphertext is written in letters, and their frequencies more or less match those of plain English text (the nonsense phrase ETAOIN SHRDLU is handy to remember for this), you're probably dealing with a transposition cipher.  (If the most frequent letters don't quite match, but still look plausible for natural text — mostly vowels and a few simple consonants — it might be a transposition of text in some other language.)
If the rank–frequency distribution looks similar to that for plain English, but the letters are obviously scrambled (e.g. most frequent letters are G, X and Q instead of E, T and A), the cipher is likely to be a monoalphabetic substitution (possibly combined with transposition).
If the frequency distribution is closer to uniform than one would expect for natural language, you're probably looking at a polyalphabetic substitution cipher.  With experience (and enough ciphertext), one may even be able to guess at the most likely cipher just based on the frequency distribution.

Knowing whether the cipher has a key or not, and what form the key takes (word, number, sequence of numbers, etc.) can also help reduce the range of possibilities.  For example, let's say that the ciphertext is uppercase letters with no spaces or punctuation, and that we know it has a key which is a word or a short phrase.  That narrows down the likely choices quite a bit:

If it's a transposition cipher, the obvious thing to try would be columnar transposition and its variants like double transposition.
If it's a monoalphabetic substitution and has a keyword, the keyword cipher described by mikeazo in his answer is the obvious choice.
If it's a polyalphabetic substitution, there are more choices.  The first ciphers I'd try would be Vigenère, autokey and Playfair; if those don't work out, Beaufort, two-square and four-square may be worth trying too.

Since you already know what the key is supposed to be, testing each cipher should be pretty straightforward: just try to decrypt the message with the key and see if the output makes sense.

Note that, in some cases, effort can be shared between ciphers.  For example, the Vigenère and autokey ciphers are identical for the beginning of the message; they only start to behave differently when the end of the keyword is reached.  It may also be a good idea to try simple variants of these ciphers, such as switching the encryption and decryption rules around; some of them work equally well in both directions, and may have been used so.


With randomized encryption, ciphertexts must be slightly longer than plaintexts in order to allow for more than one possible ciphertext per plaintext Can anyone give me a simple example of this?

  "For example, if there are $2^{64}$ possible cipher texts per plain text,
  cipher texts must be at least 64 bits longer than plain texts"

This is what book said but I don't really get this.

Think about it in the other direction; there are $2^{64}$ ciphertexts which will all decrypt to the same plaintext, and this holds for every plaintext.  There are a total of $2^n$ plaintexts of length $n$; hence, there must be $2^{64} \cdot 2^n = 2^{n+64}$ distinct ciphertexts which all decrypt to plaintexts of length $n$.  If we assume that all those ciphertexts are the same length, they must be at least $n+64$ bits long (because there aren't enough ciphertexts of shorter length).

Of course, if we don't require all the ciphertext lengths to be the same length, then it is possible that some of the ciphertexts may be shorter than $n+64$ bits (but only at the cost of having other ciphertexts be more than 64 bits longer than the corresponding plaintext).


Java recover the public key by only having the privatekey possible? Source:

https://stackoverflow.com/questions/48521925/java-recover-the-public-key-by-only-having-the-privatekey-possible

How to solve this problem programmatically

try {
    KeyPairGenerator keyGen = KeyPairGenerator.getInstance("ECDSA", "BC");
    SecureRandom random = SecureRandom.getInstance("SHA1PRNG");
    ECGenParameterSpec ecSpec = new ECGenParameterSpec("prime192v1");
    // Initialize the key generator and generate a KeyPair
    keyGen.initialize(ecSpec, random); // 256 bytes provides an
                                        // acceptable security level
    KeyPair keyPair = keyGen.generateKeyPair();
    // Set the public and private keys from the keyPair
    privateKey = keyPair.getPrivate();
    publicKey = keyPair.getPublic();

    System.out.println("Private and public keys:");
    System.out.println("PRIVATE: " + StringUtil.getStringFromKey(this.privateKey));
    System.out.println("PUBLIC: " + StringUtil.getStringFromKey(this.publicKey));

} catch (Exception e) {
    throw new RuntimeException(e);
}

OK, I will take a stab in the dark and ask the cryptographic question at hand.

  Given a private key, can we recover the public key?

The answer is it depends, but usually you can.

If we are talking about RSA, then the private key sometimes is depicted as "only" being $d$, which isn't enough to recover $e$ and $n$ (even though $e$ is usually fixed). However practically, all decent forms of encoding and libraries should store auxiliary information as their private key, which usually includes $d,n$ and some other values and from $d$ and $n$ we can easily derive, guess or brute force $e$ (see this Q/A on the site for more information).

If we are talking about elliptic curves, then the private key is some integer $a$. Again this integer alone is not enough to recover the public key, but as soon as we also learn which curve is used (which is usually stored in the private key format as well), we can recover the public key the same way as we do during key generation, using scalar multiplication on the curve, i.e. $P=[a]G$.

Now on your StackOverflow post, people have commented "nope" or similarly unhelpful statements. These are false (as you can see above).  However, they apply for the converse statement. That is, given a public key, you can't (easily) recover the private key.


Is obfuscation always reversable? Let's say we have a program that only accepts numerical inputs and the output is simply an increment by one of the input.

Example with input "a" and output "b":

$$Input: a = 7$$

$$Output: b= a+1 = 8$$

So it would be easy to know what the program is doing.

Is it possible to obfuscate the program code in such a way that we can never be sure how it's done?

For example our program could take the input:

$$7$$

double it:

$$14$$

subtract input - 1

$$14 - (7 - 1) = 8$$

Is it possible to obfuscate the exact functionality, so that it can't be reverse-engineered? If not: Could such an obfuscation scheme exist one day or is there something fundamental that prevents it?

I think what you are asking for here is the so-called notion of black box obfuscation where the behavior of the obfuscated code and a literal blackbox oracle can't be distinguished.

Sadly this has been proven impossible in "On the (Im)possibility of Obfuscating Programs" by Barak, Goldreich, Impagliazzo, Rudich, Sahai, Vadhan and Yang with a nice blog post by Green also touching and more informally explaining the topic.

To be more precise about "this" being used above: "this" means here the existence of a general "compiler" taking any program and returning a black-box obfuscated version. Special programs, e.g. functions which only evaluate to true at exactly one point or conjunctions (PDF; thanks Weiken Chen) can be black-box obfuscated.

What is possible though is so-called indistinguishability obfuscation (iO) which allows you to take two programs implementing the same functionality and run them through an obfuscator and now nobody can efficiently tell with which obfuscation they are presented.


Standard basis representation of elements in binary field In Remark B.1 from this paper it says:

  We assume canonical representation for binary fields $\mathbb{F}$, given by an irreducible polynomial and a primitive element $g \in \mathbb{F}$ for it (i.e., $g$ generates $\mathbb{F}^*$). We use the standard basis {${1, g, g^2, ..., g^{n-1}}$} to represent $\mathbb{F}_{2^n}$ over $\mathbb{F}_2$.

I think I understand the first sentence, but the second sentence confuses me. Shouldn't there be $2^{n}-1$ elements generated by $g$? If so, the elements would be {${1, g, g^2, ..., g^{2^n-1}}$} - right? Am I missing something?

Your basis is the polynomial basis.
The terminology basis comes from adopting a finite extension $F=\mathbb{F}_{q^m}$ of the finite field $K=\mathbb{F}_{q}$ as a vector space over $K$. We can see that the extension as the dimension of the vector space so we need $m$ elements to form a base.

Polynomial Basis
Let $K$ be a degree $m$ extension of the finite Field $F$ and let  $\alpha$ be a root of a primitive polynomial of degree $m$ then the powers of $\alpha$ (defining elements) forms a polynomial basis. $$\{1,\alpha,\alpha^2,\ldots,\alpha^{m-1} \}$$
Example: Let $\alpha \in \mathbb{F}_8$ be a root of an irreducible polynomial in  $x^3+x^2+1$ in $\mathbb{F}_2$. Then, $\{1,\alpha,\alpha^2\}$ is a polynomial base. With this base the 8 elements of the extension field can be represented as;
$$\{0,1,\alpha, \alpha +1, \alpha^2, \alpha^2+1, \alpha^2+\alpha, \alpha^2+\alpha+1\}$$
When we talk about the multiplicative cyclic group $F^*$ of the field $F$, the element zero is excluded $$F^*= F \backslash \{0\}.$$
In this example;
$$\mathbb{F}^*_8= \{1,\alpha, \alpha +1, \alpha^2, \alpha^2+1, \alpha^2+\alpha, \alpha^2+\alpha+1\}$$
In this multiplicative cyclic group, there are elements $g$ such that $F^*=\langle g \rangle$

Normal Basis
Let $K = \mathbb{F}_q$ and $F = \mathbb{F}_{q^m}$. Then a basis of $F$ over $K$ of the form $\{\alpha, \alpha^q, \ldots, \alpha^{q^{m-1}}\}$, consisting a suitable element $\alpha \in F$ and its conjugates with respect to $K$, is called a normal basis of $F$ over $K$

Note: these two are not the only basis that we can form, these two is the well-known basis.


authentication and access control in IoT I am researching in authentication and access control in IoT. Is there any difference between working in wireless sensor nodes and IoT in the topic authentication and access control as both require lightweight designs?

Not much, my impression is that the problems are more or less the same. People change the term to IoT because it sounds sexier than wireless sensors (and they can sell the same thing again as new). Another similar term is pervasive (ubiquitous) computing. Yet another related term is edge computing or fog computing.

The main underlying research challenges for security in all those are often the following:

resource-limited devices
lack of trust
decentralized
weak physical security
hard to update
often has energy constraints

just to name a few.