What mathematics do I need to study in order to understand fully homomorphic encryption? I am currently working on a project that requires me to use the HElib library that implements the BGV homomorphic encryption scheme described in this paper. I need to be able to tune the parameters correctly so I am trying to understand the underlying concepts. However, I find the mathematical notation in the paper quite complicated. Perhaps someone can suggest a set of mathematical concepts that I should study before reading the paper.

Edit: I've just finished my third year in a computer science undergrad program. So my background includes basic courses on discrete math, linear algebra, probability and statistics, theory of computation..etc. I have self-studied some basics of cryptography such as AES, DES, RSA..etc.

Knowing more about your background, you will definitely want to brush up on some abstract algebra. The book I link to below is pretty popular and introductory. I think it's just at your level. Also, understanding concepts like groups, rings (see below), homomorphisms, and fields are useful in understanding modern crypto. You won't be wasting your time at all.

Probably the most important skill is that vague term known as mathematical maturity, part of which includes

  fearlessness in the face of symbols

Along with this is understanding how to read a mathematical proof.

You should know about provable security as well, in particular how a problem can be reduced to another, such as how the security of the lattice shortest vector problem (SVP) can be reduced to the security of RLWE.

You should be familiar with big-$O$ notation.

You should be familiar with probability distributions, in particular the uniform and Gaussian distributions, and what it means to sample from a distribution.

As mentioned in the comments, you need to learn some abstract algebra. Back in the day, I learned enough to start from Pinter's A Book of Abstract Algebra. It has some very gentle prerequisites. You'll definitely need to learn about rings and quotient rings (RLWE means "ring learning with errors").

You'll need some linear algebra (especially norms and inner products) and lattices.

You'll need some algebraic number theory (see section 5.1.1).

Now, this is a lot, and I don't know if you just want to "get the gist" of the paper or hopefully start contributing original research. But again, "mathematical maturity", or trying to cultivate it, is the most important thing regardless!


How does Web Cryptography API produce secure PRNG? How does Web Cryptography API (eg window.crypto.getRandomValues) produce secure PRNG?

Specifications:

https://dvcs.w3.org/hg/webcrypto-api/raw-file/tip/spec/Overview.html#RandomSource-interface
https://developer.mozilla.org/en-US/docs/Web/API/window.crypto.getRandomValues

How can the method be trusted? Or is it event trustworthy?

How does Web Cryptography API (eg window.crypto.getRandomValues) produce secure PRNG?

Like the specification says:

  Implementations should generate cryptographically random values using well-established cryptographic pseudo-random number generators seeded with high-quality entropy, such as from an operating-system entropy source (e.g., "/dev/urandom").

If the OS gives sufficient entropy and the PRNG is cryptographically strong, that is a secure PRNG setup.

  How can the method be trusted? Or is it event trustworthy?

If you don't trust the browser vendor to not be malicious, you can't do crypto in the browser, period.

E.g. WebKit-based browsers (Chrome1, Safari) seem to use an ARC4-based RNG that drops the early keystream and mixes in OS entropy every ~1.5MB. That can be secure, if correctly implemented.

1 Nowadays Chrome and Chromium use Blink, which does not use ARC4, but uses OS RNGs directly.


A problem in secret sharing and mixed operators over $\mathbb{Z}$ Recently, I studied an article in which it was written that having $(A-B)\oplus C$ and $B\oplus C$, we cannot find $A$. The authors used this result to build a secret sharing scheme, but they did not provide any proof for this claim. In general case, is this claim correct?
Note that in special cases(as an example, in $GF(2^m)$), we can find $A$ easily(since $A-B=A+B=A\oplus B$).
Edit: I don't remember the exact link for my question, but the similar thing is in this paper.

I'll consider that 2's complement is used for negative numbers in $\Bbb Z$, or that $A\ge B\ge0$. Even with such provision, the question's claim is too imprecise to be settled:

  having $(A-B)\oplus C$ and $B\oplus C$, we cannot find $A$

Fact is, what we learn about $A$ from $(A-B)\oplus C$ and $B\oplus C$ depends heavily on $D=(A-B)\oplus B$, which we can compute from the givens as $D=((A-B)\oplus C)\oplus(B\oplus C)$ (and this reduction of the two givens to the single $D$ did not change what we can learn from $A$, if nothing was known from $C$ we eliminated).

That information we get on $A$ from $D=(A-B)\oplus B$ varies from

the low-order bit of $A$, which always matches the low-order bit of $D$;
to (at least) the low-order $k$ bits of $A$: we can prove by induction that for any integer $k$, $D\equiv-1\pmod{2^k}\implies A\equiv-1\pmod{2^k}$;
or even the whole of $A$: using 2's complement, when $D=-1$, $A$ can only be $-1$ and $B$ can take any value.

A true statement could be: for random choice of the low-order $k$ bits of $A$, $B$ and $C$, probability that we can determine with certainty the low-order $k$ bits of $A$ from $(A-B)\oplus C$ and $B\oplus C$ decrease as $O(2^{-k})$.


Is it true that 7zip doesn't use any salt with its KDF? This issue claims that 7zip does not use any salt with its key derivation function: https://github.com/magnumripper/JohnTheRipper/issues/1679

If that's true, wouldn't that mean you can crack multiple 7z files at very little extra cost?

From looking at the source or 7zip that seems to be the case. The format has a place for a salt, as SEJPM's link shows. It is mixed into the homebrewn iterated SHA-256 hash before the key. The 7zip decoder even seems to support salts. However, the encoder never uses a salt.

Oddly there is even code for generating a random 4-byte salt, but it is commented out. In the latest release of the code at least: I do not know if previous versions may have had it enabled.

For example, below is the salt generation part from the encoder (from 7zAes.cpp). Code calling this has also been commented out in various places.

/*
STDMETHODIMP CEncoder::ResetSalt()
{
  _key.SaltSize = 4;
  g_RandomGenerator.Generate(_key.Salt, _key.SaltSize);
  return S_OK;
}
*/


Homogenous vs heterogeneous unbalanced Feistel networks? Unbalanced Feistel networks can be homogenous (F-function identical in each round), or they can be heterogeneous (F-function not always identical in each round).
The advantage of heterogeneous UFNs is, that their internal properties change each round, making it more difficult to find specific characteristics which propagate through the different rounds.
On the other hand, homogenous UFNs seem to be cheaper (from a “resource-friendly” point of view) to implement in hardware, and related software implementations tend to be smaller.
Questions:

Is there any way to generally define how much “security” we trade in when choosing a homogenous UFN over a heterogeneous UFN, or does that strongly depend on the individual implementations?
I’m assuming the later to be true, but it would be comforting to have a confirmation on that.

Except for the “cheaper” and “smaller” arguments, are there any other reasons why one would (or maybe even should) choose to use a homogenous UFN instead of a heterogeneous UFN?
Differently asked: Does the choice between homogenous UFN and heterogeneous UFN merely depend on the available resources, or does any situation/scenario/protocol exist which would imply that one should prefer to use a homogenous UFN due to some specific reason?

There is no “generally definable” security trade-off, unless there’s something wrong with one of the algorithms itself… and if, that could be proven easier in the case of homogenous UFNs.
Using homogenous UFNs makes security proofs easier as they are easier to analyze while heterogenous UFNs tend to make cryptanalysis (and security proofs) more problematic. This can be a valid argument to choose a homogenous over a heterogeneous UFN.


How safe is a book cipher? How would you break it? This might not be a very specific question, but I was wondering this morning.

If one were to encode a message by making a string out of an entire book and writing the message by searching for a random occurrence in the "book-string" of each letter in the message and replacing it with the string index of the letter. Additionally you could make sure no number appears twice in the message as there is normally more than one occurrence of each letter in a book. This way no "letter" in the encrypted message would repeat.

How safe is this, assuming you passed on the key safely, and how would you go about breaking it?

This isn't very secure. Generally, partial knowledge of the plaintext should not lead to leakage of other parts of the plaintext. In your book cipher it clearly does.

Say we guess the first part of the message. Then we can try and see which books would be correct for the given ciphertext. After the book (the key) is found we can then decrypt the rest of the message.


Can I construct a feasible stream cipher out of HMAC and a secure hash algorithm? I have constructed a stream cipher from a secure hash algorithm and a HMAC. Here is a brief description of the algorithm:

Let: (Actually Objective-C styled pseudo code)

[data SHA512Hash]: SHA-512 hash of data,
[data SHA512HMAC:key]: SHA-512 HMAC of data with key,
[data xor:another]: bitwise XOR of two data and another which have the same length,
[data bytesTo:index]: first index bytes of data,
[data removeFirstBytes:count]: remove first count bytes from data,
[data length]: length of data.
[data concat:other]: Concatenate other after data.
[Data new]: allocate an empty buffer.

Pseudocode: (Or actual Objective-C code?)

Data hkey = [key SHA512]; // Hash to make lengths match.
Data segKey = [IV SHA512];

Data dest = [Data new]; // This will be the output
Data last = (Some constant)

do {
    // Cut off hash-sized chunks of source data
    Data segment = [data bytesTo:[hkey length]];
    [data removeFirstBytes:[hkey length]];

    // Derive a new segment key
    segKey = [segKey SHA512HMAC:hkey]; // or [segKey SHA512HMAC:[hkey concat:last]]? If so, how to decrypt?

    // XOR
    last = [segment xor:[segKey bytesTo:[segment length]]] // Truncates to make length match
    dest = [dest concat:last];
} while ([data length] > 0)

From some other questions I am suggested that this is SHA-512 HMAC running in OFB mode but what about the change in the code comment?

This code seem to decipher itself when given the same key.

Here is your algorithm in formula form, which might be easier to understand for non-objective-C-experts:

Encryption:

$P_1 \mathbin\Vert P_2 \mathbin\Vert \dots \mathbin\Vert P_n := P$ (split plaintext in blocks, same size as hash output, except the last one)
$K := \operatorname{SHA256}(\mathit{key})$
$O_0 := \mathit{IV} (= K)$
$O_i := \operatorname{HMAC}_{\operatorname{SHA256}}(K, O_{i-1})$ for all $i \in \{ 1, \dots, n\}$ (key stream)
$C_i := P_i \oplus O_i$  for all $i \in \{ 1, \dots, n\}$ (the usual stream cipher XOR)
$C := C_1 \mathbin\Vert \dots \mathbin\Vert C_n$

(where the last block $O_n$ is truncated to match the length of $P_n$)

Decryption: same, but with $C_i$ and $P_i$ swapped.

$P_i := C_i \oplus O_i$  for all $i \in \{ 1, \dots, n\}$

As you remarked right, this is output feedback mode (OFB) with HMAC-SHA-512, with the key reused as the IV. (The value you named IV – $K$ here – is actually the effective key, derived by SHA-256 from the original key, the IV is your first segkey, initialized to the same value).

If you use the commented variant with

$O_i := \operatorname{HMAC}_{\operatorname{SHA256}}(K \mathbin\Vert C_{i-1}, O_{i-1})$,

you have some new mode which is like a mixture of cipher feedback mode and output feedback mode, which uses the cipher feedback as part of the key (?). It is not a synchronous stream cipher anymore, as the keystream depends on the previous ciphertext. You can still decrypt it, you just have to use the previous version of segment instead of the previous version of last as input in the decryption function (i.e. you need one more variable in your program).

If you want to stay with established modes of operation, here is cipher feedback mode (CFB):

$O_i := \operatorname{HMAC}_{\operatorname{SHA256}}(K, C_{i-1})$

This is Counter mode (CTR):

$O_i := \operatorname{HMAC}_{\operatorname{SHA256}}(K, i)$

The analogons to ECB, CBC, PCBC don't work with a MAC (or other PRF like a keyed hash), as there is no inverse which would be needed for decryption.

Also, as Ivella remarked, your stream cipher is a lot slower than dedicated stream ciphers, or the same modes applied to a block cipher.


How do revocation certificates work in PGP? I've already read how to build and upload them, but I'm wondering how revocation certificates work, what informations they hold and so on.

Suppose my private key is compromised, but I have a revocation certificate hidden somewhere.
How the keyserver matches the revocation certificate to the compromised key? Is it possible to distinguish my revocation certificate from one generated by an attacker with the stolen private key?

A revocation certificate is a self-signature with signature type 0x20. It only says anybody with access to the private key has revoked it, you cannot distinguish between the real owner and an attacker that got hold of the private key.

You can read the details of what a revocation certificate contains by executing gpg --list-packets [revocation-certificate.asc]. For a revocation certificate of my key prepared in advance if everything including the regular backup fails, this will print:

:signature packet: algo 1, keyid 4E1F799AA4FF2279
    version 4, created 1356517877, md5len 0, sigclass 0x20
    digest algo 2, begin of digest 39 1b
    hashed subpkt 2 len 4 (sig created 2012-12-26)
    hashed subpkt 29 len 1 (revocation reason 0x00 ())
    subpkt 16 len 8 (issuer key ID 4E1F799AA4FF2279)
    data: [8192 bits]

Be aware that also the issue timestamp can be arbitrarily set by an attacker and does not help at distinguishing him from the real owner.


Encryption using matrix transformations I have been thinking lately about a block cipher which takes a block of bits and arranges them in a square matrix.  Then defining transforms on submatrices of the square matrix to scramble the bits.  The key would be a sequence of bits, which identify specific transformations to apply to the submatrices.  To unscramble the block simply reverse the order in which you execute the inverse of the transformations.  Has anyone else done any research along these lines?

For example:
Given a matrix of 100 x 100 bits. Divide the matrix into overlapping submatrices.

Define the following operation codes:

00 - rotate each sub-matrix clockwise by 90 degrees.
01 - flip each sub-matrix about it's left to right downward sloping diagonal.
10 - flip each sub-matrix about it's let to right upward sloping diagonal.
11 - rotate each sub-matrix counterclockwise by 90 degrees.

Thus a 1024 bit random number would be a mini program for executing these transformations.  Each transformation is invertible and the sequence could be processed in reverse order.

In many ways, it is like scrambling a Rubic's cube.  And I know that there are algorithmic solutions for solving Rubic's cubes.  But if you don't know the colors of each square I wonder if such algorithms would be much help.

I know that such an algorithm might be more memory intensive and possibly much slower than existing encryption algorithms, but if high throughput were not a primary consideration could such a cipher be deemed secure?

Unknowingly, you've actually answered your own question in the title.

  transformations

Imagine if you put and hold your finger on one of the bits in a test message. Then encrypt.  After a long time and possibly some cramp, your finger will have passed through the transformation matrix and out into the cipher text. One bit in and the same bit out, albeit possibly in a different position.   You're only transforming the position of the individual bits. This is entirely linear and is called a transposition cipher.  Security to cryptanalysis is very low indeed, and breaking one by frequency analysis is demonstrated in https://crypto.stackexchange.com/a/1578/23115.

Contemporary encryptions require other properties such as the following introductory list:-

Unbiased output - As only a single bit is transformed, there will be no uniformity of output frequencies.  Your message pops out the other side, only bit shifted, with exactly the same biases it had originally.
Confusion and diffusion -  Each bit should affect the other bits to a degree.  Your finger should morph into many, or even non.
Constant execution time - Cryptographers make huge effort to ensure that an algorithm flows/executes in constant time. Having major parts of it under control of the key/attacker gives too much away.
Some would argue that a 1024 bit key into a 10,000 bit block state may be unnecessarily high. There's some wonderful discussion of the futility of brute forcing large keys at How much would it cost in U.S. dollars to brute force a 256 bit key in a year?

There's quite a lot more to cipher design than my examples, but they give some context to the degree of weakness of design. Sorry.  There's a much more comprehensive list that answers What are the qualities of a good block cipher? Begginner, Intermediate, Advanced, Expert?


DES/AES invertibility My professor has posted a couple of practice questions that so far I haven't been able to find the answer for and I was hoping you could help.

DES  would  remain  invertible—it  would  still  be  ablockcipher—even if its S-boxes were arbitrarily changed (the number of input and outputbits remaining the same).
AES  would  remain  invertible—it  would  still  be  ablockcipher—even if its S-boxes were arbitrarily changed (the number of input and outputbits remaining the same).

I've been trying to figure out the "how" and "why", mostly.

DES is a Feistel cipher where the round function doesn't need to be invertible. Therefore, when designing a Feistel cipher you will have invertible and non-invertible S-box options.

In contrast, AES is a substitution-permutation network where the structure is completely different. If AES operations are not invertible, you will not be able to decrypt anything. So, the second claim is wrong.


Shift-rotating random number generator Let $\omega$ denote the set of non-negative integers. For $n\in\omega\setminus\{0\} $ define the rotation function $$\text{rot}_n:\{0,1\}^n \to \{0,1\}^n$$ by
$x \mapsto x'$ where

$x'_k = x_{k+1}$ for $k\in\{0,\ldots, n-2\}$, and
$x_{n-1} = x_0$.

Let $\bar{0}_n \in \{0,1\}^n$ be the constant $0$-sequence of length $n$. Fix $s_0\in \{0,1\}^n$ and define a function $f_{n,s_0} : \omega\to \{0,1\}^n$ inductively by setting

$f_{n,s_0}(0) = \bar{0}_n$, and
$f_{n,s_0}(k+1) = f_{n,s_0}(k) \;\oplus \; \text{rot}_n(f_{n,s_0}(k)) \; \oplus \; s_0$.

(By $\oplus$ we denote componentwise addition in $\mathbb{Z}/2\mathbb{Z}$, or equivalently, bitwise XOR.)
Question. For what values of $n\in\omega\setminus\{0\}$ is there $s_0\in \{0,1\}^n$ such that the image of the function $f_{n,s_0} : \omega\to \{0,1\}^n$ is all of $\{0,1\}^n$ (i.e. $f_{n,s_0} : \omega\to \{0,1\}^n$ is surjective)?

I think only for $n=1$.
The map $x\mapsto x\oplus\mathrm{rot}(x)\oplus s_0$ is 2-to-1 since $x$ and $x\oplus 1111\ldots 1$ both map to the same value. It follows that half of the values of $\{0,1\}^n$ do not lie in the image of this map. We can capture at most one missing value with our start point $0$, but the remaining $2^{n-1}-1$ points will never occur in the image.


What weaknesses would SHA256 hash array building and hashing the result have for password storage? You allocate a 1MB array.  Salt the password (this is the only time the salt is used other than being stored at the end) and hash the password with SHA256 8 times.  Place  31,250 copies (125,000 was an error) of the first hash to fill the array, so it cannot be de-allocated or used for anything else until the process is complete.  You then use the first hash as salt for the 1MB array and hash the entire array salted with the hash 8 times and place copies of the result in the second 1 KB block of the array.  Keep repeating the hash and fill procedure until the entire 1 MB array is over-written step by step and then finally hash the entire 1MB.  That is the hash you store next to your salt.
The default I am trying for is 8,000 SHA-256 hashes with a 1 MB memory requirement.
If the user wants higher memory requirements, the array can be 1 MB, 2 MB, up to maybe 8 MB.  The algorithm is simply copying intermediate hashes 125 times, 250 times, etc.  If the user wants more iterations, each hash is performed somewhere between 8 times, 16 times, 32 times etc.
I'm trying to make it so an attacker cannot de-allocate the 1 MB array or use it for anything else for the entire duration.
How would this stack up against BCrypt or SCrypt in terms of defending passwords against offline attacks?

The question's construction is an attempt at making a memory-hard function. This is more difficult than it seems, and the construction proposed has several flaws:

An adversary performing a password dictionary attack needs only a little over half a megabyte of memory per concurrently running process. This is because adversaries are not bound to "put 31,250 copies of the first hash to fill the array"; they can take advantage of the fact that the last copy will not get changed (become different from the but last) until the last of the passes in the process. For large $n$, this allows running nearly $2n$ processes interleaved (that is, with their stages of progress evenly distributed at a given time) using only $n$ megabytes of memory.

Independently, an adversary can save about 1/16 of the hashing effort by noticing that typically, in the step reading "hash the entire array salted with the hash 8 times", the beginning of what's hashed (on average, 0.5 MB out of 8 MB) is identical to what it was in the previous step.

It is hard to rule out that an adversary using an ASIC (or perhaps FPGA) for a password dictionary attack can organize things so that some of the (half-)megabyte of memory needed per process can be in relatively slow/cheap memory such as off-die DRAM, and only very little in fast on-die static RAM or flip-flops.

In a SHA-256 internal block hash, a sizable part of the computational effort goes into the so-called expansion of the 64-byte message block. Because most of the data hashed by the overall algorithm is hashed many times and with the same alignment to 64-byte blocks, it is theoretically possible to cache expanded message blocks and save most of that expansion work. That's quite worthwhile when repeatedly hashing the same data block, which happens nearly half of the time due to flaw 1.

Flaw 1 can be fixed by adding an outer loop performed many times, so that during all except the first of these loops the 32-byte blocks of the memory array have different and arbitrary-like content. However, that exacerbates the risk that flaw 3 becomes serious, and/or that memory even slower/cheaper than DRAM becomes usable.
Flaw 2 can be fixed by incrementing the first word of the first block before starting each hash.
Flaw 3 is the theoretically hardest to repel. Using data-dependent addresses might help, but tends to slow down legitimate use too, and may introduce undesirable side channel leakage.
Flaw 4 becomes merely theoretical after flaw 1 has been fixed: exploiting it requires a lot of extra memory, so that's most likely not worthwhile in practice.

Memory hard functions are like most crypto: anyone, from the most clueless amateur to the best cryptographer, can create one they can't break (Bruce Schneier). Thus the prudent thing is to use the ones that passed scrutiny; or if the objective is learning, study that. The current recognized standard is Argon2. It's worth reading about Balloon, too.


How to brute force sqlcipher encrypted file with MD5 hash of a 7 bit key? I have a database file that is encrypted using sqlcipher and MD5 hash. Sqlcipher to my understanding provides 256 bit AES encryption. The key is 7 bits long. How do I brute force it?

As SEJPM already hinted at in his comment, a 7 bit key is short enough to allow a plain and simple brute-force attack because there are merely 128 different keys to be tested.

Hint: 7 bit = 1111111 = 127, + 1 for the 0000000 key = 128 possible keys.

Even when using a low-resource device, testing 128 different keys to find the correct one should be a pretty quick and easy task to handle.

If the key would be longer than that – for example: 7 bytes – the time to brute-force all keys would rise exponentially to the number of bits. Staying with the example: 7 bytes = 7 * 8 bits = 56 bits, which would mean that a plain brute-force attack would need to test up to a maximum of $2^{56}$ keys, boiling down to $7.2057594037927936e16$ (= 72,057,594,037,927,936) different passwords to check… which makes brute-forcing things rather infeasable compared to brute-forcing a simple 7 bit key.

For more information about brute-force attacks, you might want to check the Q&As listed under the brute-force-attack tag and/or read the related Wikipedia article.

How to…

Practically, you only need to create a list of all possible keys and try decrypting the ciphertext by going through that list one by one until the plaintext resembles/fits the decrypted file data you are expecting. (Since you haven’t mentioned what kind of file you are trying to decrypt, I assume you are able to compare a decryption result to see if the decrypted data indeed fits the expected plaintext.)

The steps are easy, no matter the programming or scripting language you use. In this case, you could even do this manually due to the fact that you’ld only need to test a maximum of 128 different keys:

ciphertext $\rightarrow$ decrypt using key with 7-bit-value0000000 (hex: 0x00)
Does decrypted data fit expected plaintext? If “yes”, you found the key. If “no”, test next key.
ciphertext $\rightarrow$ decrypt using key with 7-bit-value0000001 (hex: 0x01)
Does decrypted data fit expected plaintext? If “yes”, you found the key. If “no”, test next key.
ciphertext $\rightarrow$ decrypt using key with 7-bit-value0000010 (hex: 0x02)
Does decrypted data fit expected plaintext? If “yes”, you found the key. If “no”, test next key.
…
ciphertext $\rightarrow$ decrypt using key with 7-bit-value1111111 (hex: 0x7F)
Does decrypted data fit expected plaintext? If “yes”, you found the key. If “no”, either the correct decryption key is not 7 bit, or you made a mistake when creating the testing keys (Ask yourself: Are you sure you’re feeding 7-bit keys and not something else?), or you have simply missed the correct key and decryption result while comparing the decryption result with the plaintext you expect. After all, this is the maximum key value a 7 bit key can have.

That’s all there is to it.

EDIT

As you’ve updated your question and added the info that the 7-bit key is hashed using MD5… be sure not to test a pure 7-bit key but MD5(potential-key) instead. Besides that, it does not influence the approach I’ve described above.

Pseudo-code:

for(i=0;i<128;i++)
{
    t = sqlcipherDecrypt(ciphertext, MD5(potential-7-bit-key[i]));
    if(verifyDecryptionResult(t) === TRUE)
    {
        output("Found valid key:" + potential-7-bit-key[i]));
        exit;
    }
}

Where verifyDecryptionResult strongly depends on what file format you expect the plaintext to be. This function can bluntly be trying to open the decryption result with some program, or comparing the decryption result with already available plaintext, or alike functionality. Anything that helps you check if the decryption result fits what you’re looking for. Listing all options would be too broad, but this should help you grasp the general idea behind the pseudocode and how to brute-force things.


True random numbers generated by sensors Is using sensor raw data a good way of generating true random numbers? I mean using an IPhone's gyro/accelerometer raw output as a base for generating an array of true random numbers.

Tl;dr: In theory, yes, if you do it carefully.  But in practice, it is better to use SecRandomCopyBytes().

Breaking it down a bit first, we step into a definition.  "True" random numbers of the kind you are discussing are those that are truly unpredictable, where the preceding data has absolutely no relationship to the next data.  This measure of unpredictability is called "entropy" by the random number crowd.

You are asking "are physical sensors good sources of entropy?"  The answer is "they can be", but it depends largely on what they're measuring and how often they're sampling it.

An accelerometer in an iPhone is a poor source of entropy if the phone is lying on your desk, because if I measure a string of values and they're all equal, the chances are pretty good the next one is equal as well.  It's also not a good source if you're simply reading it while the owner is performing a rhythmic activity, such as walking.  The motion of an accelerometer during walking is so predictable that smart pedometers (such as the fitbit) have an acceleration profile that can tell the difference between walking with it and just shaking it.

That is driven by the sampling rate.  If you are reading samples 60 times per second, that walking profile curve is going to be very visible.  But if you're sampling only once every ten minutes, even a marching band member is unlikely to yield predictable values over that duration.  Of course, sampling infrequently produces less usable entropy over time than does rapid sampling.

If you can recognize events with the accelerometer, such as a "walking step" or a motion reversal, you can measure the time between events using a high precision timer or a CPU cycle counter.  Repetitive human motion is precise only to a certain degree, such as a tenth of a millisecond.  Any measurements taken with a much more finely grained clock, such as nanoseconds, will be influenced by random biological variances between them.  If you take nanosecond timings (or CPU cycle counts) between two accelerometer events and keep only the bottom 8 bits, they'll all be unpredictable.

Most secure random number generators have an "entropy gathering service" continually running on a machine.  It's job is to harvest entropy from multiple sources over time.  Measuring user keypress timings and mouse movements using the high precision clock or the CPU cycle counter, the number of processes running at a given time, the total number of memory bytes allocated, network connection timings, hard drive seek times, all these things that the engineers "hope" are unpredictable are each measured just a few bits at a time, and those bits are mixed into and stored in an entropy pool.  The values in the pool are generally "stretched" by feeding them into a cryptographic algorithm (such as a stream cipher or block cipher) to produce a larger sequence of unpredictable numbers from a smaller input.  I believe Microsoft's CryptoAPI draws something like 512 bits from the pool and uses them as seeds to fill a buffer of random bytes.  Whenever a random number is requested, data is immediately returned from this buffer.   The buffer holds no more than 128 kb of random bytes, after which the random number generator returns to the pool for more seed bits and refills the buffer.

An accelerometer would be a good contributor to the pool if you were careful to recognize a stationary sensor and not harvest the bits generated when it's not moving, and use extraordinarily precise timings between events instead of directly sampling the raw values generated during the events.


Difference between known-plaintext attack and forward search attack I am looking at the different attacks on RSA. I came across known-plaintext attack where the public key can be used to encrypt all possible messages until it finds a match on the sent encrypted message. However, on the book I found in the library it seems this form of attack is also called "Forward search attack".

  If the message space is small or predictable, an adversary can decrypt a ciphertext c by simply encrypting all possible plaintext messages until c is obtained. Salting the message as described above is one simple method of preventing such an attack. -Handbook of Applied Cryptography

So are these attacks the same with different names or have I misunderstood it?

In context of public key encryption it is not really meaningful to consider known-plaintext attacks in the way this is done in context of symmetric encryption schemes (where an adversary gets hold of ciphertexts and knows the corresponding plaintexts and wants to recover the secret key). In public key encryption, everyone (as the public key is public) can produce ciphertexts for arbitrary messages of his choice. Consequently, an adversary can produce such pairs for any ciphertext of its choice and has not to wait to eavesdrop such pairs.

However, what is interesting in public key encryption is that an adversary who intercepts ciphertexts can not figure out which message is hidden in this ciphertext even if the adversary knows that the respective plaintext comes from a known set (in formal models this is reduced to a set of two elements, as discussed below).

The "forward search attack" in the HAC is a strategy the adversary can choose, i.e., to simply "trial encrypt" every element from the set and check if the ciphertext matches the intercepted. This attack strategy is feasible for
every deterministic public key encryption scheme (such as textbook RSA), where multiple encryptions of the same message with respect to the
same public key always yield the same ciphertext.

To formally treat security of public key encryption, we do not consider single attack strategies but a goal an adversary has to achieve within a concrete security model (attack class) and is typically modeled as a game between the adversary and a challenger. In indistinguishability games, the adversary can choose two messages and then gets back the ciphetext for one of these two and has to determine which message is hidden inside the ciphertext (where the adversary is given different "power", depending on the class of attack).

In the formal treatment of public key encryption, there is a model called indistinguishability under an
eavesdropping attack, which essentially says that an adversary is allowed to choose two messages, then gets the ciphertext for one of these messages and has to determine which one has been encrypted significantly better than guessing. As, however, in public key encryption, the adversary can built its own encryption oracle by means of knowledge of the public key, this aforementioned notion is equivalent to the well known notion of indistinguishability under chosen plaintext attacks (IND-CPA). This
attack game is essentially identical to the aforementioned, but the adversary additionally has access to an encryption oracle throughout the security game.

In the case of textbook RSA, an adversary can use this "forward search attack" as strategy to win the IND-CPA game. More precisely, when receiving the challenge ciphertext (one of the two submitted messages), then the adversary
simply calls the encryption oracle for one of the two candidate messages. If the response ciphertext of the oracle is identical to the challenge ciphertext,
the adversary knows that the message submitted to the oracle is in the challenge ciphertext, and the other one otherwise. By turning textbook RSA in a probabilistic scheme, e.g., by using OAEP, RSA can be made IND-CPA secure and this attack is no longer possible. It satisifies even the strongest notion of security, i.e., IND-CCA2 (see below).

In context of public key encryption schemes, the weakest notion of security considered today is IND-CPA (which is equivalent to the above mentioned eavesdropping) and the common stronger notions are indistinguishability under chosen ciphertext attacks (IND-CCA1) and a indistinguishability under adaptively chosen ciphertext attacks (IND-CCA2). In the latter two security games the adversary has additionally access to a decryption oracle during the security game (only before seeing the challenge in IND-CCA1 and also after seeing the challenge in IND-CCA2).


Is this really the correct way to do an IND-CPA test? In a description of IND-CPA (indistinguishability under the chosen plaintext attack), I have been reading the following, simple test:

  The adversary can generate as many messages as he wants. Then, he chooses two messages $m0$ and $m1$, those messages are encrypted, and one of the ciphertexts is sent back to him. The adversary should not be able to guess which message was used to generate that ciphertext.

Is that really the correct way to do an IND-CPA test?

I would imagine that — if I were the adversary and you the crypto-guru — I would pick and send you a one-liner saying "Hello world" and a copy of the front page of a news-paper article consisting of at least 100 words. Whatever you'll send me back encrypted will allow me to differ and identify the ciphertext as the average encryption won't pad that one-liner to the same length as the news-paper article. There's a pretty good chance that the newspaper article's cryptotext will be bigger than the one-liner's cryptotext.

Following that logic, it would mean that most (if not all) crypto currently used would fail that IND-CPA test.

Is that quoted test wrong or missing something?

That sounds like an overly succinct description of the 'Find then Guess' (FTG) notion of security, described in the paper "A Concrete Security Treatment of Symmetric Enryption".

And you are correct, there is something the test is missing: the two 'challenge' plaintexts must be the same length ($|m_0| = |m_1|$).  Also, the description is so succinct I can't tell whether they meant to give this impression, but it sounds like a 'non-adaptive' approach to FTG-CPA, in that the Adversary only has access to the encryption oracle prior to getting the challenge.  In the 'adaptive' FTG-CPA (the version described in the linked paper), the Adversary continues to be able to query the encryption oracle after receiving the challenge (and prior to making its guess).

By the way, the FTG notion is only one variant of IND-CPA.  There is also the Left Or Right (LOR) notion, and the Real OR Random (ROR) notions.  LOR and ROR are somewhat stronger than FTG, in that there is a tight reduction from a LOR or ROR advantage-bound to a FTG advantage-bound, but the reduction is not as tight going the other way around.  So if you prove in the FTG game that any opponent has at most an advantage of $\epsilon$, you can only say that any opponent in the LOR game has an advantage of at most $q_e\epsilon$, where $q_e$ is the number of queries made to the encryption oracle (so opponents might have much larger advantage in the LOR game if there were a lot of queries).


Multiple users getting access to same (secret) encryption key on a single computer? I am developing an application for Desktop PCs (Mac primarily, Windows later) that uses an encrypted SQLite database. I want to give multiple authenticated users access to this "main" database. I like to make this as secure as possible.
My constraints are:

Everything happens on a single computer. No server involved (I plan to change that, as well as introduce the use of SmartCards, but that's quite the challenge on OS X).
I roll my own user authentication (I don't want to use something complex like Kerberos or whatever else is out there as I don't have the time to dig into and manage that all as well. I'm a single fighter and need this all as simple as possible).
I understand the risk that a hacker will be able to infiltrate the system and then grab the encryption key as soon as a user logs in. I also understand the risk that a running computer may still have the encryption key lingering in memory, so a system memory dump may be a viable attack. I have to live with that for now.
My main goal is to protect the database against someone simply breaking in and stealing the computer, or copying files off it, then trying to gain access to the database.

Currently, I envision this to work as follows:

The DB encryption key is stored with another ("secondary") password using symmetric encryption (not sure what to use here, I've used Blowfish before, is that good?). That lets me change the DB encryption key centrally if needed.

That secondary password is stored in a separate "users" database, protected by the user's password, e.g. using a cypher or whatever is appropriate (I need help here).
So, when a user logs in, I simply look up the value from the users database, decrypt it using the entered password, and then use that to decrypt the DB key, and use that DB key to open the main SQLite database. If that opens the database, the user's entered password was valid.

Is that reasonable and sound, or am I missing something? Can it be improved to make it more secure or is that the best I can do under the mentioned constraints?

It is a no-no to use SHA-512 alone as entropy-stretching key derivation function protecting a password: that would leave dangerously vulnerable to brute force password search, even if salt is mixed. Other than that, the principle outlined in the question is sound, though slightly more complex than needed; also, I'd replace PBKDF2 by a better substitute like bcrypt, scrypt, or Argon2.

Sharing the main database key among many users each having a login/password can be achieved with a single level of a PDKDF2 (or better) rather than two, and nothing more complex than comparison and XOR (the later being used as the currently unspecified encryption method for the main database key).

Recall that an entropy-stretching key derivation function like PBKDF2 produces a bytestring of desired size, from

key (the password)
salt (typically at least concatenation of an application-specific constant and user id)
desired output size (not available for stock bcrypt, see note)
difficulty parameter(s), including at least an iteration count (set as high as tolerable), and for modern entropy-stretching key derivation functions (scrypt and later) maximum CPU count, and size of memory to use.

We can make the output size parameter say 48 bytes: 16 bytes for password verification purpose, and 32 bytes for the main database key. What's stored in the password database for each user includes its user id (the search entry, as plaintext), and the 48-byte output of the password entropy stretching key derivation function, with the 32-byte portion combined using XOR with the 32-byte database key. The user's record can additionally contain security parameters currently used for the entry, extra random salt, and other details like when the password was last changed.

On login we fetch the (alleged) user's record from the login/password database, compute the entropy-stretching key derivation function with the given password, and combine the result with the above 48-byte user record using XOR. We allow login only if the 16-byte subfield is all-zero, and then only use the rest as the database key, without need for further verification.

Finding the database key is as hard as finding any user's password (the stated security goal). Changing a user's password only involves changing the corresponding entry in the login/password database.

This leaves unspecified the cryptography used to protect the database by way of its key; that one is a complex issue.

Note per comment: bcrypt has fixed output size 24 bytes. It would be tolerable to halve the fields used for password check and data base key; or we could change bcrypt's OrpheanBeholderScryDoubt string constant to something twice as long, taking care that no 8 byte segment repeats (but then that's no longer bcrypt).


Secure ElGamal with OAEP Is it possible to make ElGamal IND-CCA2 using OAEP or OAEP+? (OAEP+ from: "OAEP Reconsiderd" by Shoup)

The reason I ask is that I recently answered this question and it came to my mind that OAEP or OAEP+ might be possible solutions.

Note this isn't a practical question at all. There's no intention in implementation, I'm just asking if it would be secure if I would implement it.

After some thought, I think the answer is in fact NO, even for IND-1-CCA* and even for Shoup's OAEP+.

RSA-OAEP/OAEP+ work by taking a message $m$, producing a padding $p(m,r)$ and then encrypting this, so $c = f(p(m,r))$ where $f$ is RSA encryption, and $f(u) = u^e \pmod{N}$ is deterministic. In fact, the whole point of OAEP(+) is to inject some entropy into ciphertexts which is required for IND-CPA and higher security.

ElGamal encryption is already randomised. If we try ElGamal-OAEP(+) we get $c = (g^r, y^r \cdot p(m, r'))$ where $y$ is the public key. Since ElGamal is homomorphic, this is obviously not even CCA1: consider an adversary who picks $m_0, m_1$, asks for a challenge ciphertext $c = (u, v)$ and then sets $c' = (u \cdot g^s, v \cdot y^s)$ for randomly chosen $s$. This is still a valid OAEP(+) ciphertext whatever the padding $p$ is (since we're only changing the "outer" randomness $r \mapsto r + s$) so the IND-1-CCA game will happily decrypt this and return $m_0$ or $m_1$ as desired.

This is assuming of course that you can map your padding function's range into the group over which you're doing ElGamal --- for ECC, this should be fine, for $\mathbb Z^\times_p$ groups it's harder. As an alternative one could consider hashed ElGamal-OAEP+ with $c = (g^r, H(y^r) \oplus p(m, r'))$ where $H$ is independent of the hash functions used in the OAEP+ padding $p$. My intuition is that this is still not CCA1, even though it doesn't have the homomorphic property anymore. Certainly if $H$ has some homomorphic properties itself then one should be able to do something like the above counterexample.

IND-1-CCA: Is standard IND-CCA2 where you only get 1 decryption query after seeing the challenge ciphertext instead of polynomially many.


Designing a secure IM protocol I haven't been programming much lately, so I figured I would make an encrypted instant-messaging program (read: Skype clone) with groups to hone my skills. That's not important though, I can do that. The problem is that I know almost nothing about cryptography, so I figured I'd ask here so I don't discover down the road that my way of doing crypto is all wrong and I have to remake everything.

Here's my plan:

When a client connects, it generates a keypair (or loads one from disk) and sends the public key off to the server.
The server broadcasts the public keys of everyone in a group chat to everyone else.
When a client sends a message, it encrypts (with NaCl's crypto_box) the message many times, once with each public key. Then it sends all of them off to the server, including information about which encrypted message goes to which client.
The server simply forwards the messages to the recipients, and the recipient decrypts it with his own private key and the sender's public key (again with NaCl's crypto_box).

There will of course be authentication, so someone can't just send their public key to the server, pretending to be someone else.

I have no idea how secure that method is, or if it can even work. If this is not optimal, how would you do it?

I think the very first question before diving into designing the protocol would be to ask yourself what kind of secure communication do you want? Namely, there are two options to consider when it comes to communication between the IM users:

For the client-server secure communication, there are two directions to consider:

From “sender to server”, you would have to encrypt the message with the public key of the server (assuming using public key encryption).
From “sender to recipients”, the server would encrypt each message with the respective recipients' public key (assuming using public key encryption). However, if you are consider using symmetric encryption, a good reference for protocol would be the SSL/TLS protocol that is used widely.

For the end-to-end secure communication, it would be difficult to implement for group message but simpler for individual message. It means that the sender will encrypt the message with a predefined encryption key, and only people who know the encryption key is able to decrypt the message. Sharing the predefined encryption with a group might compromise on the overall security.

Once decided on the framework type, you can add additional information to the payload (i.e. message) to ensure there is authentication, non-repudiation, data integrity, etc. A good reference would be the SSL/TLS protocol.


What is the general justification for the hardness of finding preimages for cryptographic hash functions? Since most cryptographic hash functions are simple, compact constructions does this simplicity impose a limit on the complexity and the size of a function that can generate preimages? That is, given a cryptographic hash function, H of some length and complexity can we lower or upper bound the complexity/size of a function that finds preimages of H. If not, why not?

If the upper bound on the size of a function that efficiently finds a preimage of H is smaller than the output size of H and then this has implications for the strength of the hash function. How can we justify that such an efficient preimage finding function must be larger than the output size?

The general justification is several years of cryptographic research in trying to "break" hash functions. As far as I know there is no "proof" that finding pre-images of a hash are hard. It is just assumed to be hard based on the history of effort trying to invert it.
A hash function considered secure today may well turn out to be weak tomorrow.

This paper (ONE-WAY FUNCTIONS AND CIRCUIT COMPLEXITY) might be of help in understanding the relationship between circuit complexity and one-way functions.


Implementing the Mceliece Encryption - making the Generator Matrix I am working on an implementation of the Mceliece Encryption system (MCE) and the Niederreiter encryption system. I have been through the basics of finite fields, polynomial arithmetic and some coding theory to understand it.

In brief given MCE parameters $n, k, t$, such that it is over $GF(2^m)$, $n = 2^m$, $k = n - mt$ is the dimension of the linear code and $t$ is the no. of errors the code will correct, the public key is $X = S.G.P$, where $S$ is a $k$ x $k$ non-singular matrix, $G$ is the $k$ x $n$ generator matrix for the linear code and $P$ is a $n$ x $n$ permutation matrix.

Figuring out how to get $G$ is the reason for the question. I'd like to better understand how the generator matrix is built such that its elements are only $0$ or $1$, once we have the irreducible polynomial of degree $t$, support $L$ and parity check matrix $H$. $L$ & $H$ are composed of the elements of $GF(2^m)$ represented as polynomials in binary form, e.g. $x^4 + x^2 + 1$ is represented as $10101$.

I understand there are many methods of getting to the generator matrix but found limited information online. I'd welcome a simplified explanation of the maths/algorithm or any pointers to sites/books which would help out on this.

I'm going to assume you are using binary Goppa codes. That means, that you take a support $\mathbf{L} \in \mathbb{F}_{2^m}$, a Goppa polynomial $\Gamma$ of degree t with coefficients in $\mathbb{F}_{2^m}$ and build all codewords of a GRS code, and then intersect these with $\mathbb{F}_2^n$, resulting in a code that is actually a subset of $\mathbb{F}_2^n$ (and not of $\mathbb{F}_{2^m}^n$). This is the classical definition used by McEliece in his original proposition.

As you might have already read, the binary Goppa code has a check matrix (there is an error in the Wikipedia article, this one is correct):
$$H_{grs} = \begin{pmatrix} 1 & \dots & 1 \\
L_0 & \dots & L_{n-1}\\
L_0^2 & \dots & L_{n-1}^2\\
\vdots & & \vdots\\
L_0^{t-1} & \dots & L_{n-1}^{t-1}\end{pmatrix}
\begin{pmatrix}
\frac{1}{\Gamma(L_0)} & & \\
& \ddots & \\
& & \frac{1}{\Gamma(L_{n-1})}
\end{pmatrix}$$

Now, are you are well aware, this is a $t \times n$ matrix in $\mathbb{F}_{2^m}$ and will thus give you codewords in $\mathbb{F}_{2^m}^n$. But we are interesed in code words only in $\mathbb{F}_{2}^n$. One can get a check matrix that gives only codewords in $\mathbb{F}_2$ by expanding every entry in the matrix in a basis of $\mathbb{F}_{2^m}$.

This means, if your entry of the matrix is represented as as vector $0101$ in $\mathbb{F}_2^4$ (for $m=4$), you would expand this entry as four entries and write them in four rows: 0, 1, 0, 1.

Example:
Let one of your rows of your check matrix $H_{grs}$ be
$$\begin{pmatrix}0101& 1010 &0001& 1000\end{pmatrix}$$
then you would write this as
$$\begin{pmatrix}
0 & 1 & 0 & 1\\
1 & 0 & 0 & 0\\
0 & 1 & 0 & 0\\
1 & 0 & 1 & 0\end{pmatrix}$$
You do this for all your rows and you will end up with a check matrix $H$ of size $mt \times n$, since you are expanding every row by $m$ rows. From now on, you only work over $\mathbb{F}_2$; using this check matrix, you'll get code words in $\mathbb{F}_2^n$. Note: You will have to do Gauss elimination at this point to get rid of rows that give the same equation. This will reduce your row number and give you a reduced check matrix of size $(n-k) \times n$, where k is the dimension of your binary code.

Now, to get a generator matrix $G$ for that code, you look for a full-rank matrix with $H^\top G=0$. There are many ways to achieve this, and you should find enough material on this. For example: http://en.wikipedia.org/wiki/Parity-check_matrix. Keep in mind, that if $H$ is a check matrix for $G$, then $G$ is a check matrix for $H$. So you build $G$ by pretending $H$ is a generator and you want to find a check matrix for that code.

I hope this is what you asked for.


What is this called: encrypt $X$ with key $E$, decrypt $X$ with key $D$? I am a software developer interested in developing an application with cryptography. I can explain what I want to accomplish, but I do not know the technical terms for the cryptographic functions I am seeking.  Many Google searches have not helped me. Could someone please help me with the proper cryptographic terms for what I am seeking, so I know what to search for in my research?

Here is what I am looking for:

Encrypt large amounts of data quickly with key $E$.
Encryption is currently unbreakable and is expected to remain so as far as is
known.
The encrypted data cannot be decrypted with key $E$.
The encrypted data can only be decrypted with key $D$.
Key $E$ is created by passing key $D$ into an algorithm/function.
It is preferred that key $D$ can be less than 20 characters and can be
typed from what is visible on the keys of an ordinary computer
keyboard. (AKA...a password)

Thank you!

As correctly pointed out in the comments: The term is asymmetric cryptography, also known as public-key cryptography.

How do we know that it's asymmetric encryption?

In symmetric encryption the encryption key and decryption key are identical, meaning you can decrypt data with the same key that it has been encrypted with.

On the other hand, in asymmetric encryption the encryption key and decryption key are different from one another ($K_{Enc} \ne K_{Dec}$) and in your example it's stated:

  The encrypted data cannot be decrypted with key $E$.

How to create $E$ from $D$

This can be achieved with the following procedure:

Create a key $K$ with a key derivation function by using your password. You can think of this function as a key-stretching-function. KDFs can be used to stretch keys into longer keys or to obtain keys of a required format. This is important to get an input which is "random enough" for step 2.

PBKDF2 is a noteworthy here. To increase the difficulty of a potential attack a cryptographic salt is added to the password.

You can now use this created key $K$ as a seed for a PRNG (pseudo random number generator). Important here is the word pseudo, which means that given the same seed it will always return the same created number.
The PRNG is used for a key-pair-generation-algorithm, which then returns the public-key $K_{Public}$ (in your example $E$ for encryption) and the private-key $K_{Private}$ (in your example $D$ for decryption).
You can now use this generated keys for any asymmetric cryptography methods, some well known examples are:

ECDH (Elliptic-Curve-Diffie-Hellman).
RSA

Important: I left out that you would have to use different key-pair-generation-algorithms, depending on which asymmetric cryptographic scheme you would use.

This procedure would work theoretically, but is very expensive from a computational view as you're only using asymmetric encryption. In practice this problem is solved by implementing a hybrid cryptosystem:

  A hybrid cryptosystem is one which combines the convenience of a public-key cryptosystem with the efficiency of a symmetric-key cryptosystem.

A noteworthy example of this would be ECIES (Elliptic Curve Integrated Encryption Scheme), where the security is based on the Diffie–Hellman problem. This scheme allows two parties to create a (random) session key, which allows symmetric encryption.


SIM security for two messages Here SIM means the simulation based security

Consider a two message encryption scheme:$$Enc:K \times M \times M \rightarrow C \times C$$

and $Enc(K, m, m')=(K \oplus m, K \oplus m')$,
In the real world experiment, the adversary $Eve$ gets $(K \oplus m, K \oplus m')$ as ciphertext, and thus, the information leaked to $Eve$ is $(K\oplus m)\oplus(K \oplus m')=m \oplus m'$, now how should I modify the original ideal world experiment so that in the ideal world, the adversary $Eve$ also gets $m \oplus m'$?

I would highlight Thomas's last point; not only is leaking $m \oplus m'$ failing to provide perfect secrecy, it is often practically insecure.

Exactly how bad this is depends on what those messages actually are (and how they are encoded), but it can be bad indeed.  As one example, in my experience, recovering two ASCII English texts from their xor is about as difficult as solving a newspaper cryptogram.


zendo data size restrictions zendo is a new mobile phone app which encrypts messages using a one-time pad:

http://techcrunch.com/2015/03/24/one-time-pads-ride-again/

users have to meet in person and exchange a key via a qr code. the one-time pad data is then initialized on both phones using this key to make a secure transfer. however, according to the article, only 0.5MB of pad data is exchanged:

  The process takes a few seconds for 0.5MB of pad to be exchanged —
  which is enough for “thousands” of messages between the two users.
  More than 3,000 based on a conservative estimate of average text
  message length, according to Newbold. You can also exchange multiple
  pads to stockpile more megabytes for even more future missives. (To be
  clear, if users run out of pad, the app defaults to AES encryption so
  messages are never sent unencrypted — it just steps down to industry
  standard levels of security.)

  Pictures can also be sent via Zendo, and those are encrypted with a
  single use AES 256bit key and an HMAC key (for authentication), which
  are then sent using One-time pad encryption, so the photos are secured
  via OTP without needing to use up too much of the pad to send them.
  The same method will be used to encrypt and send videos, audio and
  documents/attachments — file transfer features which will be coming in
  future updates to the app.

it was my understanding that a one-time pad must be as long as the plaintext being transferred, so 0.5MB of pad would enable no more than 0.5MB of plaintext to be transmitted with perfect secrecy.

however the above excerpt makes it sound like the pad can be shorter than the plaintext while still maintaining the complete security of a one-time pad:

  so the photos are secured via OTP without needing to use up too much of the pad to send them

i'm just wondering if this is some cryptographic technique that i have not heard of, or if the article is wrong to imply that the cyphertext will have the same security (entropy) as the pad, for data that is longer than the 0.5MB pad (as most photos and videos are)?

edit

my problem was actually with the wording of the article. i was reading the above quote as:

  Pictures can also be sent via Zendo, and those are encrypted with a
  single use AES 256bit key and an HMAC key (for authentication), [the
  pictures] are then sent using One-time pad encryption, so the photos are
  secured via OTP without needing to use up too much of the pad to send them.

but actually i think the article means to say:

  Pictures can also be sent via Zendo, and those are encrypted with a
  single use AES 256bit key and an HMAC key (for authentication), [the aes
  key and hmac key, but not the pictures] are then sent using One-time pad
  encryption, so the photos are secured via OTP without needing to use up too
  much of the pad to send them.

and this makes a lot more sense.

sorry this turned out to be more of a reading comprehension question than a cryptography question in the end :p

i don't want to add another question now as that would be unfair to those who have already given answers addressing my first misunderstanding-question. thanks.

The system described in the quoted article depends on the security of AES with random keys (not only on the theoretical unbreakability of the OTP) for at least two things:

the encryption of large files, as apparent in the quotes of the question;
the initial establishment of the OTP, as shown by this other quote

  The first step is always optical, and that is an exchange of an AES 256bit key, plus an authentication key, and so those are the keys to encrypt the One-time pad as it’s being transferred wirelessly via Multipeer [or Wi-Fi Direct]… with a symmetrical AES key that was exchanged optically.

Claims that a practical system base its security directly on the OTP are typically misleading, on purpose as a marketing point or by incompetence, often both.

Addition per comment: the technique used for photos seems to be using 256 bits from the pad as an AES key enciphering the photo. This is not as secure as the OTP from an information-theoretic standpoint, yet this is believed practically secure when done properly.


Encrypt your ECDSA signature with NTRU to make them quantum secure, does that work? I have a general question about quantum security. ECDSA is suppose to be broken by quantum computers. Whilst something like NTRU is suppose to be secure.

My question is: if we sign with ECDSA and encrypt the signature NTRU. Does that make the signature safe? Because I can expose both ECDSA and NTRU public keys but if either of them is compromised it shouldn't compromise.

Is this a correct statement or am I missing something?

So you want to encrypt the message's ECDSA signature with NTRU.

Firstly, if the NTRU is secure against the quantum computers, then anything under NTRU encryption is secure against the quantum computers.

Secondly, NTRU has also digital signature, instead of ECDSA use NTRUSign.

Depending on different mathematical and computational problems are not considered a good practice.

update: by the comments of Maarten Bodewes

Remember that, public key encryption and signature require two separate keys; public key and private key. In your case;

the public encryption keys generated by the receiver as $PK_{rec},SK_{rec}$
the digital signature keys are generated by the signer as $PK_{sign},PK_{sign}$.

As a result, the two public keys, $PK_{rec}$ and $PK_{sign}$, are generated by different people.


How do you create a large PRP from a small one? How can you efficiently create a pseudorandom permutation with a large domain given a PRP with a small domain? Meaning: given an $n$-bit PRP, how can I create an $n k$-bit PRP?

I'm only interested in security up to $C 2^{\frac{n}{2}}$ messages, when $C$ is a reasonably-sized constant. For a power-of-2 $k$, the Luby-Rackoff construction essentially achieves this, although it requires $k^2$ calls to the PRF.

The cascade construction extends a PRF (in particular, a PRP) with fixed input length to a PRF with an arbitrarily large input length.  If you want a PRP with large input length, you can use the Luby-Rackoff/Feistel transformation on the large-input PRF obtained from the cascade.

The cascade construction is analogous to the Merkle-Damgard paradigm for extending a fixed-input-length compression function to a hash function with arbitrary input length, except that cascade uses a secret-key primitive (the given PRP) in place of the compression function.  The secret keys for the small- and large-input PRFs are exactly the same size, and the number of invocations of the small-input PRF is the ratio of the input lengths (large divided by small).  Both of these efficiency measures are about the best one could hope for.

Let $F \colon \{0,1\}^k \times \{0,1\}^\ell \to \{0,1\}^k$ be the given PRF, where the first input denotes the "key," and denote $F_y(\cdot) = F(y,\cdot)$.  Note that the PRF output and key lengths must be equal.  If $F$ is a PRP, then $\ell=k$.

For a secret key $y \in \{0,1\}^k$ and an input $x = x_1 x_2 \cdots x_n$ where each $x_i$ is a block of length $k$ (the input length of the original PRF $F$), we compute the cascade iteratively as: $y_0 = y$, and $y_i = F_{y_{i-1}}(x_i)$ for $i=1,\ldots,n$; the final output is $y_n$. In words, the output on block $x_i$ becomes the key for the next invocation, on $x_{i+1}$.

Bellare, Canetti, and Krawczyk analyzed the cascade construction in
http://cseweb.ucsd.edu/~mihir/papers/cascade.html .  They proved that as long as the large inputs $x$ are encoded in a prefix-free manner (in particular, if all inputs have the same length), then the cascade construction yields a secure PRF.  Concrete bounds may be found in the paper.


Verifying encrypted addition Alice has two secret numbers, a and b. She publishes c1=E(a), c2=E(b) and c3=E(a+b). Is there an encryption system E such that anyone would be able to prove that the c3 as published by Alice is actually E(a+b)?

EDIT: Modified the question to use "anyone" instead of "Bob".

Note that this is different from homomorphic encryption. In case of homomorphic encryption Bob is able to compute E(a+b) himself, but he is not necessarily able to prove that E(a+b) as computed by Alice is correct. What's needed here is a system where Bob is not necessarily able to compute E(a+b) but is able to prove Alice's result.

One example of such a system is ElGamal over a group $G$ generated by $g$. The public key is $y$ and an encryption $(x,w)$ of a message $m$ is of the form $(g^r, y^r m)$ for some integer $r$.

You have three ciphertexts $(x_1, w_1)$, $(x_2, w_2)$ and $(x_3, w_3)$ which are encryptions of $m_1$, $m_2$ and $m_1m_2$, respectively. The random integers used is $r_1$, $r_2$ and $r_3$, respectively. Note that $r_3$ isn't $r_1+r_2$, it is a random number. You want to produce a proof that the encryptions are correct.

The idea is to observe that the ciphertext $(x_1x_2/x_3, w_1 w_2 / w_3)$ is an encryption of $1$. As such, you only need to prove that it is an encryption of $1$. This amounts to proving that the logarithm of $x_1x_2/x_3$ to the base $g$ equals the logarithm of $w_1w_2/w_3$ to the base $y$, which is done using a standard proof of equality of discrete logarithms.

You asked about additively homomorphic cryptosystems, and above I outlined a solution using multiplicative ElGamal. However, the approach works just as well for an additive variant of ElGamal or Paillier.


How are messages from server secured when using SSL certificate In case of using SSL the certificate server has a primary key and a public key that is published to all clients - as far as I understood. So in this case when message is encrypted by public key (on client side) only the owner of private key (which is the server in this case) has ability to decrypt it.

But I do not understand how this works the other way, I mean when the message is encrypted by private key then does it mean that whoever has the public key can decrypt it? That would mean that only the messages toward the server are secured and messages which come from the server can be read by anybody with public the key.

Update:
in my case I have web server in DMZ hosts multiple web services (WCF), the clients are non-server application (they are standalone .NET application) reaching these web services via internet using https protocol.

My server has SSL certificate issued by Versign, the point is that my client do not have any type of credential and any machine with that application (or similar app) should be able to consume the services, the point is that the information passing between client machine and server must be encrypted and signed, so this is my question is having the certificate and using the transport security enough to make sure that nobody can read the messages passing between client and server or do I have to somehow come up with some kind of ad hoc client credential and add message security.
This link describes that SSL is good for Intranet and for internet message security is suggested why? what does happen if I only use SSL and no message security for the internet scenario?

You are missing the entire TLS protocol. The TLS protocol first establishes session keys. These can be randomly created at the client and send encrypted to the server. After that the session keys can be used to protect the data for confidentiality, integrity and authenticity. Encryption and authentication is performed in both directions.

The TLS protocol is however gravitating towards authenticated ephemeral Diffie-Hellman, which is a key agreement protocol. Ephemeral DH provides forward security, meaning that the session keys (and thus the data) stay secret even if the private key gets factored afterwards. In that case the private key is only used for signature generation to perform authentication.


NTRU Euclidean algorithm the inverse of f modulo p I am very new to the world of cryptography and have just began my research in the post quantum cryptography sector. I have been reading and trying to understand NTRU key generation and am struggling to understand how to practically do the inverse of f. I know that this is solved using the Euclidean algorithm, but I am unable to figure out what the steps would be. I was hoping someone would be able to show the steps to solve the example shown on the NTRUEncrypt wiki page shown below (fp or fq), or a smaller polynomial that gets the point across. I am more interested in the practical steps then the theory behind it, as I have found many resources for that.
Thank you!

I'll try to follow a similar notation to the example on wikipedia
Our initial inputs are $p(x) = x^{11}-1$ which defines the ring and $a(x)=-x^{10}+x^9+x^6-x^4+x^2-1$ and working mod 3 rather than the mod 2 example on wikipedia.
For step 1 we have quotient $q_1(x)=2x+2$ and remainder $r_1(x)=x^9+x^7+x^6+2x^5+2x^4+x^3+2x^2+1$ so that $t_1=x+1$.
For step 2 we have quotient $q_2=2x+1$ and remainder $r_2=x^8+2x^6+x^4+x^3+2x^2+2x+1$ and $t_2=x^2$.
For step 3 we have quotient $q_3=x$ and remainder $r_3=2x^7+x^6+x^7+x^4+2x^3+2x+1$ and $t_2=x^3+x+1$.
For step 4 we have quotient $q_4=2x+2$ and remainder $r_4=x^6+2x^5+x^4+x^2+2x+2$ and $t_4=2x^4+2x^3+2x^2+2x+1$.
For step 5 we have quotient $q_5=2x$ and remainder $r_5=2x^5+x^4+2x^2+x+1$ and $t_5=2x^5+2x^4+x^3+2x^2+2x+1$.
For step 6 we have quotient $q_6=2x$ and remainder $r_6=x^4+2x^3+2x^2+2$ and $t_6=x2x^6+2x^5+x^3+x^2+1$.
For step 7 we have quotient $q_7=2x$ and remainder $r_7=2x^3+2x^2+1$ and $t_7=x2x^7+2x^6+2x^5+2x^3+2x^2+1$.
For step 8 we have quotient $q_8=2x+2$ and remainder $r_8=x^2+x$ and $t_9=2x^9+x^8+2*x^7+x^5+2x^4+2x^3+2x+1$.
For step 9 we have quotient $q_9=2x$ and remainder $r_9=1$ and $t_9=2x^9+x^8+2x^7+x^5+2x^4+2x^3+x+2$, which is the required inverse.
I'll leave the mod 32 example as an exercise (sagemath is your friend).


What are the problems with Diffie-Hellman groups 3 and 4 (RFC 2409 + RFC 2412)? In RFC 2409 and RFC 2412 Diffie-Hellman groups 3 and 4 were defined.
These are groups over elliptic curves based on Galois Fields with   and  elements respectively.

I know that these sizes are considered as too small for modern cryptography.

But anyway, there is very little info about these groups on the internet. Are there other reasons besides the fields' sizes for not using these groups?

There is a relatively obscure attack, named the GHS attack after its authors Gaudry-Hess-Smart, that applies to binary curves where the exponent is not prime. In this case $155 = 5\cdot 31$ and $185 = 5\cdot 37$.

The main idea of the GHS attack is to map the discrete logarithm from an elliptic curve over, say,  $\mathbb{F}_{2^{155}}$ to a hyperelliptic curve of genus $16$ over $\mathbb{F}_{31}$.

Unlike elliptic curves, hyperelliptic curves of high enough genus have better-than-generic algorithms for computing discrete logarithms, and therefore the security of many curves over $\mathbb{F}_{2^{155}}$ and $\mathbb{F}_{2^{185}}$ is going to be smaller than you would expect from a proper strong curve. There are a few papers analyzing the $\mathbb{F}_{2^{155}}$ and $\mathbb{F}_{2^{185}}$ cases, and they largely conclude that such fields—that is, binary fields of composite degree—should not be used for elliptic curve cryptography.


Append text to file without decrypting & encrypting again Is it possible to add a line to a file which is encrypted symmetrically or asymmetrically (private key refers to readkey below, public key refers to append key then) without decrypting it?

I was thinking about s.th. like:

msg1="hello"
msg2="world"
appendkey=...
readkey=...
file=touch(...)
addLine(msg1, file, appendkey)
addLine(msg2, file, appendkey)
ERROR=decrypt(file, appendkey)
WORKS=decrypt(file, privkey)

Then the WORKS equals to:

hello
world

The idea is, that various number of people can add s.th. to a file without seeing its content. Only the owner of the file can decrypt it once to see all lines (he/she should not decrypt all the lines individually for performance reasons). For me this scenario typically sounds asymmetrically, thats the reason why I thought that there could be a mechanism to use the public key to append s.th...

There may be a relatively straightforward answer, depending on your requirements: could you use a multipart MIME message with separate MIME sections, one for each user's encrypted contents?

If you're looking instead for an asymmetric cryptosystem that supports appends, then maybe you can update your question to make that clear.


Organizational Internal Man In The Middle Scenario Question. I'm a software developer. I design and write secured systems for my customer. My customer recently downward directed that all traffic to/from my server be routed through a new appliance. I have no idea what the appliance is. All I was told was that it would impact routing and client certificates. I was given the name of a person to work with and off we went. We use client certificates for authentication and all traffic to/from the server is encrypted. Here is where things get weird. Previously, my server had it's own SSL certificate issued to it's current host name. Now when I hit the site, I see a host name of the new appliance for the site's SSL certificate, not my server's host name. Also. When a client certificate arrives at my server, it is no longer reading as having been issued by who I know to be the original issuer. But there are no negotiation errors during the handshake. Everything is green in the browser.

The only thing that makes any sense is that this appliance is decrypting the traffic from the client before it gets to my server so that it can be logged and inspected, before re-encrypting it and sending it along to my server. Then, when it gets the reply from the server, it likewise decrypts, logs, inspects the data, before re-encrypting it and the forwards the data.

Is my understanding of asymmetric and symmetric cryptography serving me correctly here? Mostly I stick to the logic of my applications and have sufficient understand of cryptography to be able to do what I need to do and ensure my systems remain secure. But I am not intimately familiar with the ins and outs of how it always functions. Seems like my organization just installed an internal man in the middle device for monitoring purposes and didn't tell me what was really going on.

Is this plausible?

Yes, your understanding is correct.

This is a TLS (or any other secure transport protocol) capable proxy. What it does is that it generates site certificates on the fly. You connect to a site through the proxy with your client and it performs a man-in-the-middle, as the TLS connection is setup before anything else.

First it will connect with the remote site, and create a connection with it using the normal server certificate. Hopefully it completely verifies and validates that computer's certificate. So that's taken care of the connection with the remote server.

Now to spoof your connection the proxy must have a certificate for a specific hostname (as Common Name in the certificate). It probably first looks up the certificate in the cache and uses that together with the private key. If it cannot find the certificate it generates a key pair and signs a temporary certificate for it. Then it sets up the connection with your client.

Once it has both TLS sessions running it can act as a normal proxy. Now it can (deep) inspect any data send through the connection in either direction.

Alternatively, it can send a redirect to the client so that it connects to a different hostname. That way it can use a single, long term server / device certificate. Of course your client will have to accept this redirection for the scheme to work.

Of course it is not that easy, as a random certificate will be rejected by your client - there is no certificate chain to a trusted certificate. Basically this can be solved by injecting a trusted CA certificate in your trust store. This can be a Windows trust store, or the trust store of the client application that you're using (e.g. a firefox browser). Usually the certificate is simply pushed using the Windows group policy together with some script for the most common browsers.

The proxy will now act as its own Certificate Authority, signing any certificate it generates using the private key with it's own CA certificate. Once the certificate chain is trusted your client will lite up "green" as it cannot see the difference with any other chain.

Alternatively, the proxy could use a broken (or otherwise controlled) CA, like Iran did with the DigiNotar CA, when it requested certificates for Google.

Of course even deep packet inspection will not be capable of detecting all possible covert channels, so I'll leave it up to you to hack out of the system (with the possible repercussions that come with it).


Homomorphic Encryption and Semantic Security using Lattices? I've been reading Brakerski and Vaikuntanathan's "Efficient Fully Homomorphic Encryption from (Standard) LWE" and I'm still digesting pieces at a time.

Under section 1.1, "Re-Linearization: Somewhat Homomorphic Encryption without Ideals", they state they mask the plain text with noise. The noise is created with multiplications and additions of the plain text, and the result is cipher text:

  To encrypt a bit $m$ in $\{0, 1\}$ using secret key $\mathbf{s}$ in $\mathbb{Z}_q^n$, we choose a
  random vector $\mathbf{a}$ in $\mathbb{Z}_q^n$ and a "noise" e and output the cipher text

  $c = (\mathbf{a},b = \langle \mathbf{a},\mathbf{s} \rangle + 2e + m)$

  The key observation in decryption is that the two “masks” – namely,
  the secret mask $\langle \mathbf{a},\mathbf{s} \rangle$ and the "even mask" $2e$ – do not interfere with
  each other. That is, one can decrypt this cipher text by annihilating
  the two masks, one after the other: The decryption algorithm first
  re-computes the mask $\langle \mathbf{a},\mathbf{s} \rangle$ and subtracts it from $b$, resulting in $2e + m \pmod{q}$.
  Since $e \ll q$, then $2e + m \pmod{q} = 2e + m$.

How can this be semantically secure if the same mask $\langle \mathbf{a},\mathbf{s} \rangle$ is being used on messages? That is, two different encryptions of the same value (say "10") would produce the same cipher texts.

If I added two numbers (say "10" and "100"), wouldn't they need to be masked with the same $\langle \mathbf{a},\mathbf{s} \rangle$?
Or does this scheme require additional accounting somewhere to allow for different $\langle \mathbf{a},\mathbf{s} \rangle$ masks?

The LWE assumption

I think we should start from the LWE assumption.
Let $n$ and $q$ be integers and let $\chi$ be a distribution over $\mathbb{Z}_q$. We often take $\chi$ as a Gaussian with small variance. (We take an error $e$ from this distribution $\chi$ and assume that $|e| \ll q$.)

The LWE assumption states that any efficient adversary cannot distinguish two oracles if a vector $\mathbf{s} \in \mathbb{Z}_q^n$ is chosen uniformly at random;

one is the random oracle that returns $(\mathbf{a},b) \in \mathbb{Z}_q^n \times \mathbb{Z}_q$ chosen uniformly at random
the other is the LWE oracle that returns $(\mathbf{a},b) \in \mathbb{Z}_q^n \times \mathbb{Z}_q$, where $\mathbf{a} \gets \mathbb{Z}_q^n$, $e \gets \chi$, and $b = \langle \mathbf{a},\mathbf{s} \rangle + 2e$.
(Note: I replace $e$ with $2e$ from the correct definition. This is a minor problem.)

The LWE-based Symmetric-key Encryption

Keeping the assumption in mind, we next review the symmetric-key encryption scheme appeared in your quotation.

$\mathsf{Gen}(n,q)$: Choose $\mathbf{s} \in \mathbb{Z}_q^n$ uniformly at random. The secret key is $\mathbf{s}$.
$\mathsf{Enc}(\mathbf{s},m \in \{0,1\})$:

Choose $\mathbf{a} \in \mathbb{Z}_q^n$ uniformly at random.
Take a sample $e$ from $\chi$.
Compute $b = \langle \mathbf{a},\mathbf{s} \rangle + 2e + m \in \mathbb{Z}_q$.
Output a ciphertext $c = (\mathbf{a},b)$.

This encryption scheme is apparently IND-CPA.
In the IND-CPA game, denoted by $G$, the adversary has an encryption oracle which has a secret key $\mathbf{s}$.
Let us replace the encryption oracle with the random oracle and call this game as $G'$.
It is easy to show that $G$ and $G'$ are indistinguishable under the LWE assumption.

Answer

  How can this be semantically secure if the same mask $\langle \mathbf{a},\mathbf{s} \rangle$ is being used on messages? That is, two different encryptions of the same value (say "10") would produce the same cipher texts.
  If I added two numbers (say "10" and "100"), wouldn't they need to be masked with the same $\langle \mathbf{a},\mathbf{s} \rangle$?
  Or does this scheme require additional accounting somewhere to allow for different $\langle \mathbf{a},\mathbf{s} \rangle$ masks?

By this definition, two ciphertexts $c_1, c_2$ of plaintexts $m_1, m_2 \in \{0,1\}$ under the secret key $\mathbf{s}$ are written as

$c_1 = (\mathbf{a}_1, b_1) = (\mathbf{a}_1,\langle \mathbf{a}_1,\mathbf{s} \rangle + 2e_1 + m_1)$ and
$c_2 = (\mathbf{a}_2, b_2) = (\mathbf{a}_2, \langle \mathbf{a}_2,\mathbf{s} \rangle + 2e_2 + m_2)$.

If we can obtain two ciphertexts with the same mask, that is, two ciphertexts with the same randomness $\mathbf{a}$, they are not IND-CPA secure.
We have

$c_1 = (\mathbf{a}, b_1) = (\mathbf{a},\langle \mathbf{a},\mathbf{s} \rangle + 2e_1 + m_1)$ and
$c_2 = (\mathbf{a}, b_2) = (\mathbf{a}, \langle \mathbf{a},\mathbf{s} \rangle + 2e_2 + m_2)$.

It is easy to check the relation $m_1 - m_2 \bmod{2}$ by
the relation $b_1 - b_2 \equiv 2e_1 + m_1 - (2e_2 + m_2) \bmod{q}$.
Since $e_1, e_2, m_1, m_2$ is "small", $b_1 - b_2 \bmod{q} = 2(e_1 - e_2) + m_1 - m_2 \in [-q/2,q/2]$. Therefore, the difference $b_1 - b_2 \bmod{q}$ reveals the relation $m_1 - m_2 \bmod{2}$.

Finally, I mention that the scheme is additively homomorphic.
Suppose that we have two ciphertexts

$c_1 = (\mathbf{a}_1, b_1) = (\mathbf{a}_1,\langle \mathbf{a}_1,\mathbf{s} \rangle + 2e_1 + m_1)$
$c_2 = (\mathbf{a}_2, b_2) = (\mathbf{a}_2, \langle \mathbf{a}_2,\mathbf{s} \rangle + 2e_2 + m_2)$.

Consider $c_1 + c_2 \in \mathbb{Z}_q^n \times \mathbb{Z}_q$.

$c_1 + c_2 = (\mathbf{a}',b')$
$ = (\mathbf{a}_1 + \mathbf{a}_2, \langle \mathbf{a}_1 + \mathbf{a}_2, \mathbf{s} \rangle + 2(e_1 + e_2 + (m_1 + m_2 \mathbin{\mathrm{div}} 2)) + (m_1 + m_2 \bmod{2}))$.

Multiplication is tricky. I recommend to read the BGV paper, which employs "tensor" to make notation simpler than the BV paper.


How are one-time pads distributed? It seems that OTP encryption is unbreakable. I have read some articles (Wikipedia, Blogpost, etc.), but I could not find any information about how they are used.

If I wanted to create a messenger service, how would I distribute the OTP keys? Both the sender and the receiver need this key before the message is sent, right?

And how do I make sure no one else gets these keys?

If you perform the distribution digitally (using networks) then you have a problem. Unless you use another one time pad you lose the perfect confidentiality as the distribution itself won't deliver perfect security. But using another one time pad is pointless: you would lose exactly as many key bits as you are distributing, while you are only protecting the data for confidentiality, not integrity and authenticity.

So basically you'll probably have to physically distribute the keys. That kind of burden is probably not very useful. Hence we mostly treat the one time pad as a theoretical cipher. One very big reason for this is that - although not proven secure - there are many (stream) ciphers that are thought to be secure. There is simply no need for a one time pad.

So the key management / key distribution is extremely awkward for one-time-pads not just because of the size, but also because anything you do with the key breaks the perfect secrecy you are trying to achieve.


Disjunction of several instances of sigma protocol Assume there exists zero-knowledge interactive protocol for a language $L \in NP$ i.e., if an instance $x \in L$ then prover can convince the verifier, that $x \in L$ with high probability without any other information.
A zero-knowledge interactive protocol is said to sigma protocol if it satisfies following conditions

Three move protocol: In the protocol, prover first sends a message
$m_1$ to verifier, verifier upon receiving $m_1$ send a $t \in
   \{0,1\}^k$ to prover. Prover based on $t$, compute and send message
$m_2$ to verifier. Verifier outputs valid ot invalid based on input
$x$ and the transcript $(m_1,t,m_2)$
Completeness: If $x \in L$, verifier returns valid
Special Soundness: For any $x$, if there are two accepting transcript
$(m_1,t,m_2)$ and $(m_1,t^\prime,m_2^\prime)$ where $t \neq
   t^\prime$, one can extract witness for $x$.
Zero-knowledgeness: There exists a polynomial-time simulator $M$, which on input $x$ and
a random $t$, outputs an accepting conversation of the form     $(m_1,t,m_2)$, with the same probability distribution as conversations between the honest $(P,V)$ on input $x$

Assume, there exists a sigma protocol for language $L$ and consider $n$ instances $(x_1,x_2,x_3,.....x_n) \in L$.  Consider, prover has $n$ instances of $(x_1,x_2,x_3,.....x_n) \in L$ and witness $w_i$ for only one  $x_i \in L$. Can we construct a sigma protocol to prove that that atleast one $x_i \in L$ out of $n$ instances?

There is a truly elegant solution to this problem by Cramer, Damgard and Schoenmakers from CRYPTO'94. You can also read about it in Section 4 of the survey on $\Sigma$ protocols by Damgard.


Does stronger cryptographic hashes also imply being better at verifying integrity? What I know so far
Fact 1) I know that all cryptographic hash functions have the following properties

They are many-to-one in nature

They produce fixed size outputs

Given an output x it is infeasible to find the original message m such that H(m) = x

Fact 2) I know that certain cryptographic hash functions are "stronger", but more "expensive" to compute than others - in the sense that trying to overcome their (Property 3) is a lot harder and time consuming/resource intensive.

sha512(m) is harder to crack than sha256(m) which is in turn harder to crack than sha224(m)

Fact 3) I also know that certain cryptographic hash functions perform worse on verifying a message's integrity than a simple CRC checksum. (According to the following stackexchange post)

A cryptographic hash truncated to 32 bits can easily collide with two inputs that differ in only one or two bits, whereas a CRC won't. The CRC is geared towards reliably detecting error patterns that commonly occur in transit, so it will do better on those kinds of errors and worse on others. The short hash does optimally over all inputs, and as a result does worse than CRC on the inputs CRC is good at dealing with.

What I want to know
Question 1) What common hash functions are worse than CRC checksums, and which are better than them in verifying integrity? (e.g. file corruption/changes).
Question 2) Is it the case that the stronger the cryptographic hash function, the better it is at verifying integrity? (e.g. sha512 will be able to detect file changes better than sha256).

1) All common cryptographic hash functions are better than CRC, even MD5. This is due to the fact that they are designed to detect malicious tampering, whereas CRC is not. MD5 is still crackable, but CRC can be trivially manipulated.

2) hash function collision resistance determines how "good" they are at integrity verification, as there are more possible unique outputs, bigger is better, however even 64-bit collision resistance is enough to detect non-malicious data corruption in most cases unless you are dealing with large files. SHA256 has 128-bit collision resistance, which is a lot, that is 340 billion billion billion billion, which is more atoms than contained in all of the human beings on the planet combined. The collision resistance of a 512-bit function such as SHA512 is just nuts, almost matching the amount of atoms in the entire universe.


Conditioning Component in Entropy Source Given a sample of random bytes, how to determine if Entropy Source (source of random bytes) includes a Conditioning Component or not, with respect to NIST SP 800-90 B)?

Thanks

The Ways Things Should Be is that when one tests data, one knows (independently of the data) from what this data came from, and therefore if the origin of the data is the output of a Conditioning Component (including, a source with Conditioning Component), or not (source with Raw data output).

There is no reliable way to determine that from the data. If any correct standard entropy test consistently fails (low p-value), then the data is not from the output of a properly functioning Conditioning Component. I do not see that anything else can be safely asserted (save contraposition).

In particular, if in the following model the Noise source detects particles from a radioactive source; Digitization outputs 1 for event and 0 for no event, sampling at fixed rate several times above the average disintegration period; and Post-processing computes delays between pairs of events (in periods of the sampling), with output 0, 1 or nothing based on comparing the delays (with nothing for equality); then it is practically impossible to distinguish presence or absence of a properly functioning Conditioning final stage.

Entropy source per NIST SP 800-90B 2nd draft:


How does Python's pycrypto library generate primes? The pycrypto library in Python can generate random n-bit prime numbers. The syntax I use is as follows:
from Crypto.Util import number
number.getPrime(2048)

The above function has a very impressive performance and returns primes with a very small delay. What is the process used to generate such large primes in such short time periods in this function?

The documentation is not directly telling the implemented algorithm. One can check from the source code. getPrime uses isPrime and that calls the Rabin-Miller Primality test.

getPrime generates a random odd number $\texttt{N}$ and calls isPrime

number=getRandomNBitInteger(N, randfunc) | 1
     while (not isPrime(number, randfunc=randfunc)):
         number=number+2

isPrime first checks for evenness and for pre-calculated Sieve primes, that list is the first 10000 primes. It may be a prime in the Sieve or divisible by one of them. If none of the cases, then the Rabin-Miller test is performed.

The Probability: The returned value of getPrime, if a probable prime, then the probability is given by
$$ 1 - \frac{1}{4^k}$$ where $k$ is the number of iterations.

The Number of iterations: The Library defines

false_positive_prob=1e-6

calculates the $k$ by

k = int(math.ceil(-math.log(false_positive_prob)/math.log(4)))

and from this, the number of iteration in the library is $k=10$.

Note that In my undergraduate, we used $k=20$. That makes false positive in the worst case 1e-12 where the library has 1e-6.

The Complexity: If modular exponentiation by repeated squaring is used then the complexity is $\mathcal{O}(k \log^3 n)$ where $k$ is the number of iterations to test that determines the probability.


Are those two distributions indistinguishable? The Decision composite residuosity problem problem states that is impossible to distinguish between those two ensembles:
$\{x^N \mod {N^2} | x \in \mathbb{Z^*_{N{^2}}}\}$ and $\{r  \in \mathbb{Z^*_{N{^2}}}\}$

Can we assume the same for these:
$\{x-1+x^N \mod {N^2} | x \in \mathbb{Z^*_{N{^2}}}\}$ and $\{r  \in \mathbb{Z^*_{N{^2}}}\}$

I see no reason to expect $x-1+x^N \bmod N^2$ to be indistinguishable from $r$, at least not based upon the assumption you give.  The map $f(x)= x^N \bmod N^2$ is a very different map from the map $g(x) = x-1+x^N \bmod N^2$.  The range of $f$ is a subgroup of size $\varphi(N)$; that's not true of $g$ (for instance, the range of $g$ can potentially be the entire group of integers modulo $N^2$).  The map $f$ is a $N$-regular map; I don't see any reason to expect $g$ to be $N$-regular in general, and maybe not even regular.  As a third difference, $f(x+kN) = f(x)$, but $g(x+kN) = g(x)+kN$.  For these reasons, I don't expect to find a simple reduction between these two indistinguishability statements.