Is it possible to encrypt a process? Imagine a hypothetical system as follows:

A distributed algorithm running on a Local Area Network (LAN) that allows real-time addition and removal of processors.
The addition of a processor is considered trustless until proven otherwise (guilty until proven innocent).
Each processor in the system is given some process instructions, and a data stream to run said process instructions on over time.
An intruder (Eve) can add or remove hardware at any point, listen into any communications link between processors, and modify any signals coming from a compromised processor.

How to protect the system from Eve, without sacrificing too much computational power?

The biggest mystery to me is the hot-swappable processors, as communications between processors can be safeguarded with a myriad of well-known standard encryption methods. However, the security issue seems to go right down to "don't even let the processor know what its processing". Is there a way of encrypting both the process instructions and the data, whilst being able to perform useful computation still? If so, what are such processes called? Where can I learn more about them? Thanks in advance.

- EDIT - In the interest of clarity:

A process instruction is what is performed on a processor.
The task to be completed is a distributed algorithm. Aka, it is to be performed across multiple processors (all processors + LAN collectively), but those processors should not know what it is that they are trying to do so as to prevent Eve from knowing.
Processors are trusted to execute instructions given. However, it is assumed that Eve can replace the processor with one that leaks information regarding both data and process instructions.
Validation of process instructions received by a processor can occur. However, Eve can replace unprotected code without issue, so such validations may be skipped under such circumstances.

EDIT 2 - Answering fgrieu's questions:

A) The question's title asks if one can "encrypt a process" when the (updated) question does not define a process per se.

The "encrypt a process" is a sort of tl;dr of the question, summarising to the core aspect of the problem from my perspective.

B) "Process instructions" is defined as "what is performed on a processor"; is that a processor's instructions, data, or both?

Both a processor's instructions and the data being processed.

C) What should encryption protect: the processor's instructions, or/and some other data?

Both a processor's instructions and the data being processed.

D) In academic cryptography, encryption aims at confidentiality only; is integrity immaterial? More generally, what are Eve's goals?

Eve's primary goal is to determine the processor instructions (of which the data can be used to infer these instructions as well).
Eve's secondary goal is manipulate the program to perform self-destructive tasks.

E) Are processors trusted to hold a secret (key, or data they manipulate) and only use it per instructions they execute?

No. If a processor has been compromised, then it is expected that any and all information that processor receives and computes will be passed to Eve.
If both data and processor instructions are securely encrypted, then processors can be trusted due to an inability to decrypt said information.

F) Are processors trusted to not execute instructions given by Eve (perhaps, by checking a digital signature of instructions given to them before executing these?), in particular instructions that make use of a secret/private key they hold?

No. Any compromised processor is assumed to perform any function Eve has installed on them.

The conventional ways to tackle similar problems involve trusted processors. That is, trusting that non-compromised processors

Can keep secret the data they manipulate (including instructions, keys)
Work without error, neither miss-executing instructions, nor correctly executing instructions which have been incorrectly designed.
Authenticate ingoing data (including instructions) as coming from non-adversaries and non-compromised processors. This is performed with Message Authentication Codes or Digital Signatures.
Can exchange data in encrypted form.
Initially contain at least an appropriate secret adversaries do not know, a set of authentic instructions, and perhaps a unique identifier.

Note: from an academic standpoint, authentication and encryption are separate functions: the later aims at confidentiality only. However authenticated encryption can provide data confidentiality and integrity, and a fragment of the question makes senses only for encrypted implying integrity too:

  if both data and processor instructions are securely encrypted, then processors can be trusted due to an inability to decrypt said information.

With the above assumptions, it is at least theoretically possible, with conventional networking and distributed computing techniques, to come out with instructions that will perform a computation in a distributed manner, and resist all adversarial attempts to produce an incorrect result that pass an authentication. Adversaries, and compromised processors (without the appropriate secrets) can't produce anything that non-compromised processors and users will accept. In theory, the worse an adversary can do is remove enough processors and suppress enough messages that no result will ever come out. It might even be possible to prove that a correct result will eventually come out if enough non-compromised processors (and their communication links) remain. In practice that is uneasy (in particular errors tend to creep in all but tiny list of instructions).

Ensuring confidentiality of instructions and data is even harder, including in theory. In particular, encryption of everything manipulated is not enough, because traffic analysis (measuring time of transmission and length of encrypted data exchanged) has the potential to leak what is performed, including data.

Despite these difficulties, modern distributed computing systems use trusted processors and achieve some level of security. One important technique that helps is layered security, where the practically inevitable security failure of a processor or set of instructions (due to bugs) is isolated as much as possible. That's a reason to use asymmetric cryptography (which aims to insure that compromise of a processor does not compromise the keys of other devices), and operating systems which attempt to isolate processes (with a useful level of success).

If on the other hand we make lesser hypothesis on the processors, we are moving into poorly charted territory.

As pointed in comment, potentially homomorphic encryption can ensure that non-trusted processors perform some computation but can't leak what they compute. It is also theoretically possible to ensure that if a rogue processor manages to alter the computation, the result fails an integrity check, as with trusted processors.

However homomorphic encryption tends to come at extremely high computational overhead, even without integrity thrown in. Making it feasible at all for simple common tasks is a research topic, and has been for long enough that many IT architects are tired. And I don't know if distributing homomorphically encrypted computation with some quantified level of tolerance to adversarial fault is even a research topic yet.


Calculating symmetric key bit strength 16 byte key where each byte is in range 0-255, generated using cryptograhic PRNG will be believed to have 128 bit strength.
What would be a bit strength of a key generated using same quality PRNG, also of 16 byte length, if each byte instead of being one of 256 random values, would be one of 16 hexadecimal characters?
Would that be calculated as (128 x 16) / 256 = 8 bit?

One hexadecimal digit is equivalent to 4 bits, so 16 of them would be 16 * 4 = 64 bits.
Intuitively, since one hexadecimal digit takes up exactly half an octet, your bit strength compared to using the full octet is also halved, so 128 / 2 = 64.


ECDH Public Key Recovery - Determine if valid key exists from just signature and message If I have just the (r,s,v) values of the signature and the message hash, what is the most efficient way to determine if a valid public key exists?

I do not need to know the public key, just that the signature and message hash recover to a public key.

Lets say with the notation:

, are the values from the signature.
ℎ is the hash of the message being verified
 is the public key
 is the group generator
|| is the x-coordinate of the point
{,′} are the two curve points with x-coordinate

The recovery would be:

$$P \ \overset{?}{=} r^{-1}s\{R, R'\} - r^{-1}hG$$

My question is if there is a fast way of determining whether P exists, without doing the full expensive calculations to determine P.

"My question is if there is a fast way of determining whether P exists, without doing the full expensive calculations to determine P."

I believe that you could check whether $r$ is a valid nonzero $x$ coordinate; that is, whether it is a part of a solution to curve equation (e.g. if your curve is in Weierstrass form with characteristic > 3, you'd check whether $x^3 + ax + b$ is a Quadratic Residue).

If it is (and if it is nonzero), then yes, you could perform the operations to recover $P$, and it would come up with two valid points, and so that's your answer.


What do the security definitions of SHA-3 mean, quantitatively? In the SHA-3 standard (page 31) the security of SHA-3 is defined quantitatively, for example, they are saying SHA3-256 provides 256 bits of preimage resistance. How is this number of bits to be interpreted?

The definition of preimage resistance that I know doesn't speak of bits, but of a running time $t$ (and a success probability $\epsilon$).

Intuitively, I'd interpret it like this: An attacker can only find a preimage (with a decent probability) after running $t = 2^{256} \cdot t_H$, where $t_H$ is the time required to calculate one hash. Is that correct?

Bonus: Is there a (citable) source for this? The SHA-3 standard has shockingly few references, and the Keccak reference doesn't speak about preimage resistance at all.

Aleph's comment and pointer to the Keccak reference goes a very long way to answering this question (p. 9):

The key words here are "workload equivalent to $N$ calls to $\mathrm{Keccak-}f[r + c]$ or its inverse."  Invocations of the Keccak permutation are being used as the unit of time.  Your intuitive take that it's hash function invocations isn't very far off from this, but note that a single SHA-3 call may result in one or more permutation calls, so Claim 1 is more stringent.

In a more abstract setting, where we're talking about the sponge construction in general and not a concrete implementation like Keccak, we talk about the permutation (and its inverse) as an oracle that the adversary can freely call (often people say "query") as they see fit.  Then the security of the construction is expressed in terms of how many queries the adversary makes.  The oracle calls are treated as outputting the result of a random permutation in constant time.

See also: the Keccak team's more generic treatment of sponge functions.


Does this computation lead to solving DL? Imagine we have $g^x$, $a$ and $g^b \in \mathbb{Z}_p$. Is it realistic to compute $g^{(a+x)b}$ without knowing $x$ and $b$? Or is it equivalent to solving the Discrete Logarithm problem?

No.
Assuming that uniformly random sampling for $x,b$ is applied, this (let's call it E-CDH) is actually equivalent (in terms of hardness) to the Computational Diffie-Hellman Problem (CDH). Which states: Given a finite group $G$, sample $a,b\in G$ uniformly at random and provide $g^a,g^b$. The problem is solved if you can find $g^{ab}$.

Proof:

CDH is at most as hard as E-CDH ($\Rightarrow$). Suppose we have an oracle $\mathcal O(g^b,a,g^x)$ that returns $g^{(a+x)b}$ (i.e. an oracle that solves E-CDH). We can now solve any given CDH instance $g^a,g^b$ as the result of $\mathcal O(g^a,0,g^b)=g^{(a+0)b}=g^{ab}$.

E-CDH is at most as hard as CDH ($\Leftarrow$). Suppose we have an oracle $\mathcal O(g^a,g^b)$that returns $g^{ab}$, ie solves the CDH problem. Now suppose we are given the instance $g^x,a,g^b$, we now compute $g^a$ and $g^x\cdot g^a=g^{x+a}$. Finally we return $\mathcal O(g^{x+a},g^b)=g^{(x+a)b}$ and thus solve the instance.

Small assumption: We need to actually know $g$ and the relevant group.


What happens at this part in the key schedule of a Speck...? I am trying to figure out the process behind the Speck block cipher.
I understand how XOR works (Exclusive-or) when you take 2 strings of bits and you want to XOR them together.

However, in the key schedule of the cipher, there is a point where XOR takes place but I don t understand what is being XORed.

Link: https://en.wikipedia.org/wiki/Speck_(cipher)#/media/File:Speck_block_cipher_0_indexing.svg

For example, in the key schedule in the link, the result of the binary addition is being XOR d with 0?

Can someone explain what this means?
Thanks.

For example, in the key schedule in the link, the result of the binary addition is being XOR d with 0?

It's very simple: In the key schedule, the exclusive-or step after the addition is done with the round counter, and the round counter starts at $0$ rather than $1$.

So for round number $0$, the first exclusive-or is done with the value $0$. In the next round, the exclusive-or is done with the value $1$, and so forth.

The supplied reference code might be easier to read than the block diagram, depending on your programming skills.


How to correctly (good practice) generate gpg keys in batch mode (unattended) WITH a passphrase I'm writing a web interface in PHP to generate keys. I'm familiar with gpg's command line options, particularly --batch. I'm also familiar with PHP's GnuPG API.
I can't find a way to safely pass the user's password from the web interface to the gpg command line because gpg uses a pinentry program? PHP's GnuPG functions don't include an API to generate keys.
What other way is there to generate keys, unattended, other than creating a batch file with the passphrase in that file like so:
Key-Type: default
Subkey-Type: default
Name-Real: Bob
Name-Email: bob@gmail.com
Expire-Date: 2021-12-25
Passphrase: mysecretpassphrase
%commit

Note: putting the passphrase on the command line with --passphrase is not wise.
Thanks!

I finally found the answer by reading the whole manual.
$ man gpg says around line 1944:
--passphrase-fd n
Read  the passphrase from file descriptor n.
and
--passphrase-file file
Read the passphrase from the file.


Store hashed email and compare hash values I have a number of different systems sending me email addresses, but I don't actually need the underlying email, just a hash of the email address. I know I can compare hash values to find matches across the senders, which is all I want to do, but what if each sending system uses a different salt or hash method.  Is there some way to compare the resulting hash values I have?

Eg. Sender 1 sends me emails using sha1 and no salt.
Sender 2 sends me email addresses using md5 and a salt (which they also send)

Can I take md5(sha1) and sha1(md5) and compare that hash output? Or do I need to specify that all emails should be hashed using the same method? Is there a better way that will allow each sender to select the hash method they want to use but still allow me to compare email addresses across senders?

With normal cryptographic hash functions, two different ones, or the same hash function with different salts (which in effect are different hash functions too, for each salt) are supposed to be independent of each other, i.e. there should be no way (other than brute-forcing the message) to know from the results if they have the same input.

There are some special constructions of "different" hash functions which do not quite behave that way, but when there are independent salts, you even then have no chance.

As you used the homomorphic-encryption tag on your question, this might be a way to go. For example, with modular exponentiation modulo a prime (or analogously in a elliptic curve group), each sender would have to convert the mail address to a number $x$ (everyone using the same method for this), then calculate $f_i(x) = g_i^x$, where $g_i = g^i$ is a number assigned to each sender (and you know the $i$).

To compare the results $f_i(x)$ and $f_j(y)$, you calculate $f_i(x)^j$ and $f_j(y)^i$. If they match, then we have $(g_i^x)^j = (g_j^y)^i$, i.e. $(g^x)^{i·j} = (g^y)^{i·j}$, which usually means that $x = y$.  (This is a variation of the Diffie-Hellman key exchange.)

The $i$ works as a kind of salt here, so for listeners who don't know $i$, the mail addresses of different systems are not comparable. But I don't see how we could incorporate some kind of sender-chosen random salt for each message.


Hashing high entropy key into AES format If I have a high entropy key (ECDHE shared secret), what type of hash should I use to format this into an AES-256 key? Is Sha256 or Sha3_256 sufficient to maintain entropy or do I need to use a KDF (Scrypt / Argon2) and exchange the salt during the handshake??

I seem to recall that shared secret keys should be hashed before using as encryption keys (some brief discussion here).

If your key is already high-entropy, then hashing with SHA256 is fine. If you plan to generate several keys (ie, encryption and HMAC) from the original shared secret, then HKDF is a good option. This is a key-based KDF.

Scrypt and Argon2 are password-based KDFs and are not appropriate - they're designed for low-entropy input (such as passwords).


Recovering state of modified RC4 key scheduling algorithm Consider this algorithm:

def ksa(k):
    L = length(k)
    j = 0
    for i from 0 to L: #[0..L-1] (non inclusive "to")
            j = (j + k[k[i] % L])%L
            swap(k[i], k[j])

k is an array of integers $0 \leq x < 256$. The questions is how to enumerate all possible arrays k resulting in an array with given prefix $P$. In other words if k'=ksa(k), and if $P=[1,2,3]$, then how to generate all k, so that $prefix(k',length(P))=P$? Enumeration would be best, but constructing just one such k is good too. Solution for a variant with for i from 0 to C where $C \leq L$ would be interesting too.

This is a variation of the key schedule for encryption algorithm RC4.

The algorithm you describe seems to have a class of special states (similar to the Finney states of RC4) consisting of the states such that $i = j$ and $k_x \bmod L = 1$, where $x := k_i \bmod L$.

If we are at a state that belongs to this class at the beginning of the loop, the effect of the loop will be simply to swap $k_i$ and $k_{i+1}$ and to increment both $i$ and $j$ by one.  Thus, as long as we also have $x \notin \{k, k+1\}$, the state at the next iteration of the loop will also belong to this class of special states.

In particular, consider what happens if, before the algorithm, we have $k_0 = L-1$ and $k_{L-1} = 1$.  Then the initial state $i = j = 0$ belongs to the special class described above, and this will continue to hold almost to the end of the algorithm.  The second to last iteration, where $i = L-2$, does take us out of the class, leaving us with $i = j = x = k_x = L-1$, but this just causes the last two elements of the array $k$ to be swapped a second time on the last iteration, leaving us with $k_{L-2} = L-1$ and $k_{L-1} = 1$.

Meanwhile, all the other elements of the array, between the $L-1$ at the beginning and the $1$ at the end, just get shifted down by one position as the $L-1$ element bubbles up past them.  Thus, from an initial array $$(L-1, a, b, c, \dotsc, y, z, 1) \tag{1}$$ we end up with the final state $$(a, b, c, \dotsc, y, z, L-1, 1) \tag{2}$$ regardless of the values of the unknown elements $a, b, c, \dotsc, y, z$.  Conversely, to end up in any final state of the form given in $(2)$ above, it suffices to start with the corresponding initial state $(1)$.

(The same trick works also for loops terminating at some $i = C < L-1$, except that the initial $L-1$ element then ends up at $k_{C+1}$ rather than at $k_{L-2}$.)

In fact, I just wrote a little program to test this.  Here's a sample run with $L = 10$, one line per iteration, starting with eight random values bracketed between $L-1 = 9$ and $1$:

k = (9, 144, 165, 42, 43, 56, 231, 72, 53, 1), i = 0, j = 0
k = (144, 9, 165, 42, 43, 56, 231, 72, 53, 1), i = 1, j = 1
k = (144, 165, 9, 42, 43, 56, 231, 72, 53, 1), i = 2, j = 2
k = (144, 165, 42, 9, 43, 56, 231, 72, 53, 1), i = 3, j = 3
k = (144, 165, 42, 43, 9, 56, 231, 72, 53, 1), i = 4, j = 4
k = (144, 165, 42, 43, 56, 9, 231, 72, 53, 1), i = 5, j = 5
k = (144, 165, 42, 43, 56, 231, 9, 72, 53, 1), i = 6, j = 6
k = (144, 165, 42, 43, 56, 231, 72, 9, 53, 1), i = 7, j = 7
k = (144, 165, 42, 43, 56, 231, 72, 53, 9, 1), i = 8, j = 8
k = (144, 165, 42, 43, 56, 231, 72, 53, 1, 9), i = 9, j = 9
k = (144, 165, 42, 43, 56, 231, 72, 53, 9, 1), j = 8, end of loop


Is a nonce considered 'secret' enough for HMAC? We're implementing a mobile application which communicates with a web service, and on first install the user sends its deviceid to the web service (over TLS, unauthenticated at this point) - which determines if the user's device is known to our system. If the device is not known, the user must authenticate with a username and password to associate the device. When the web service responds to the mobile application requesting a username and password, the response includes a nonce, valid for that request and response only.

Once the Username/Password is requested, the client generates a cnonce and a HMAC:

hash_hmac(sha256, nonce || deviceid || cnonce, nonce)

using the nonce supplied previously as the key. When the response is received by the web service, the supplied nonce is invalidated.

As this mobile app is considered to be on a hostile device, we don't want to be storing a secret key in the app which can be recovered.

Is it safe to use the nonce as the key for the hmac in the above example?

No, the nonce is not fit to be a HMAC key, because anybody can view the nonce in transit. If - on the other hand - the TLS connection does deliver enough security then you would not need the HMAC.

It's fine to use the nonce as one time code, but you don't need the HMAC for that. If an attacker can obtain nonce's send to clients than the attacker can always replace the original nonce with another one by redoing the HMAC calculations.

Note that your solution space may be empty if you cannot trust the client application. That sounds a lot like trying to implement a DRM scheme.


Do hash functions need to "look random"? I've noticed that looking random is not often listed as a requirement for a good hash function in the same way that preimage or collision resistance is.

Do we need hash functions to look random?

Specifically, suppose $s$ is a seed, and consider the PRNG that outputs $$H(s \|0)  \| H(s \|1 ) \| H(s \|2) \| ...$$

Do we need this to be indistinguishable from random?
Will any protocols be weakened if it wasn't?

The answer is most certainly not! Well, I sort of lied, since it depends on what you are doing. I'll explain.

The basic property of hash functions is collision resistance, and this requires nothing beyond that. The output doesn't have to look random in any form, and this suffices for anywhere that you need collision resistance.

However, in many cases, because most hash functions in practice do look sort of random (completely undefined), they are used for other things. For example, HMAC assumes that the compression function (with one part of the input being the key) is essentially a pseudorandom function. More extreme, but very common examples, are the modeling of the hash function as a "random oracle". This is used for OEAP encryption padding, in most cases in practice for signatures, and more. You also somewhat assume this property for hashing passwords. (Note that for any hash function $H$, if you define $H'(x) = x|_n\|H(x)$ where $x|_n$ is the first $n$ bits of $x$, then $H'$ is collision resistant if $H$ is collision resistant. However $H'$ would be a very poor choice for password hashing.)


Asmuth-Bloom Secret Sharing $m_0$ public? i am trying to figure out how Asmuth-Bloom secret sharing works and followed the example on wikipedia and replaced it with own numbers.

Namely, i used:
$S=3$
$k=3$
$n=4$
$m_0 = 13, m_1=45, m_2=46, m_3=47, m_4=49$

I've been able to construct the shares

$s_1 = (17, 45), s_2 = (2, 46), s_3 = (34, 47), s_4=(6,49)$

I then result in $x \equiv 692 \mod 46*47*48$ which is correct, since $S = 692 \equiv 3 \mod 13$ which is my secret.

However, i wonder where $m_0 = 13$ is coming from for the final secret reconstruction, it seems like it is not explained anywhere. The only thing i could find is this stating it would be "kept secret by the dealer unless stated otherwise".

Is $m_0$ just either a public parameter? Or do i need the dealer to store it "secretly" (which would require the dealer to reconstruct the secret)?

According to Dragan&Tiplea,On the Asymptotic Idealness of the
Asmuth-Bloom Threshold Secret Sharing Scheme $m_0$ is a public parameter.
The scheme itself does not require $m_0$ to be kept secret. However, by keeping it secret you could eliminiate the possibility to get a probabilistic distribution of secrets as explained here but if $m_0$ for some reason is lost, the secret is not recoverable, which kind of defeats the purpose (or parts of it) of a secret sharing scheme.


Are there parts of a SHA-512 hash that occur more often then others? Suppose I have a 'begin' password that I can remember.

I calculate it's SHA-512 hash, transform it to base-64 and check if it has a least 1 lowercase, 1 number, 1 capital, and 1 sign.

If this is not the case I repeat this procedure (but now use the previous hash as input) until I have a hash that fills these requirements.

I will now use this final hash as the 'final' real password.

Will every possible combination of bits be (approximately) equally likely?
(If I ignore the first lowercase, number, capital and sign in the password and only look at the other chars)

In short: Will every possible 'final' password be equally likely?

In short: Will every possible 'final' password be equally likely?

Yes, we expect that they equally likely. Cryptographic hash functions expected to have a well-distributed output. If you find any bias, you can convert this into an attack. Even there is a tiny bias then that can be used to attack for the hash function.

You seem like you are going to use the SHA-512 hash function as a password generator. Your scheme's weak point will be your master password. One can still write a password cracker for your construction. And Cryptographic hash functions are not designed to be slow, they are designed to be fast. That is why we use iteration on Key Derivation Functions. A better solution using PBKDF2 or Argon2, and use their output. You can use the iteration number as the next try if not occur. So first look at, 100000 then 100001, etc.


Is $(a,g^{ab})$ computationally indistinguishable from $(a, g^c)$? From wikipedia, the DDH assumption says，given a cyclic group $G$ of order $q$ with generator $g$, $(g^a, g^b, g^{ab})$ looks like $(g^a, g^b, g^c)$ where $a,b,c$ are randomly and independently chosen from $\mathbb{Z}_q$.

Then what I wonder is, whether $(a,(g^a)^b )$ looks like $(a, g^c)$, where $a,b,c$ are randomly and independently chosen from $\mathbb{Z}_q$? Further, in which kind of group does this `assumption' hold?

Their statistical distance is less than $\: (q\hspace{-0.04 in}-$$\phi$$(q))\hspace{.02 in}/q\:$, $\:$ since

$\:$ if $a$ is relatively prime to $q$ then $(\hspace{.02 in}g^a)^b$ and $g^c$ are

$\:$ each uniformly distributed and independent of $a$
$\;\;\;\;$ and
$\:$ even if $a$ isn't relatively prime to $q$, $(\hspace{.02 in}g^a)^b$ and $g^c$ each

$\:$ have a positive probability of being the identity element

.
Therefore, if $q$ has no small factors then they are in fact statistically indistinguishable.


Is Porticor's "homomorphic" key encryption something that can really be done or is it just marketing hype? Porticor has an interesting file encryption offering for encrypting and decrypting files in an MySQL database quickly.

They are an Amazon AWS (Amazon Web Service) Partner Network technology partner and their product is available in the AWS Marketplace.

It seems similar to Gazzang's zNcrypt.

Porticor has been touting for a while that it will be offering homomorphic key management. That sounds very interesting and appealing, but it seems to be taking them a long time to roll it out.

Is it theoretically feasible for them to implement this, or is it just marketing hype? I'm beginning to wonder.

The details are very sparse as to what they are actually doing. So, I'll speculate. Below are some claims and what I think they are doing.

  The master key (in its plain unencrypted form) will be literally nowhere in the cloud, yet completely usable for split-key encryption.

Typically this is done using some sort of secret sharing, which doesn't necessarily mean homomorphic encryption (HE). That said, there are some advantages with using HE. Under typical secret sharing, the secret must be reconstructed at some point. With HE, that is no longer the case. Encryption and Decryption can be done homomorphically (see this and this). Timing results of both are promising and could be considered practical, especially for the first link.

  we only have an encrypted form of the master keys. In more technical words, the Porticor product will perform split-key encryption with a partially homomorphically encrypted master key.

This leads me to believe they are doing something similar to the two links above. They store an encrypted version of the master key and their management key (similar to the safe deposit box they describe), and use those to encrypt/decrypt data. Most likely they are doing something similar to the first link as the result of that encryption/decryption is plaintext where the result of the 2nd link is not plaintext but the plaintext encrypted with the homomorphic key.

Assuming I am correct (who knows though as they don't publish the details yet), I would say it is practical. Look at the timing results in that paper. At the same time, it is somewhat marketing hype. Sure "The master key (in its plain unencrypted form) will be literally nowhere in the cloud, yet completely usable for split-key encryption" but the data must be decrypted at some point and can be stolen at that point in time. Also, I'm not sure I'd trust my data being protected by such new techniques yet. The field of homomorphic encryption is such an unstable field right now.


Diffie-Hellmann generator As far as I understand, there isn't an easy algorithm to find the generator of a cyclic group used in DH Key exchange. Is it true?
Given a large prime number like, e.g. 0x614423aaf0d10001f7d7, how can a generator of its group be computed (and checked that's true)?

As far as I understand, there isn't an easy algorithm to find the generator of a cyclic group used in DH Key exchange. Is it true?

No, it is easy, as long as you know the factorization of $p-1$.

A value $1 < g < p$ will be a generator to a prime $p$ iff for every prime factor $q$ of $p-1$, we have $g^{(p-1)/q} \not\equiv 1 \pmod p$

And, there will be enough generators (specifically, $\phi(p-1)$ of them) that just randomly selecting $g$ randomly, and then testing them by the above process is quite doable.

So, isn't factoring $p-1$ a hard problem?  Well, it wouldn't be for the 79 bit value you picked, but that's far too small to be used in a Diffie-Hellman exchange, it is generally accepted that you need at least a 2048 bit prime.  So, for a value $p-1$ that size, how do we factor it?

Well, what we don't do is select a large random prime $p$ and try to factor it; instead, we build a value $p-1$ with a known factorization, and check that $p$ happens to be prime.  One common way of doing this is to search for $p$ such that $(p-1)/2$ is also prime (this is known as a "Sophie Germain prime") and hence $p-1$ has a known factorization.

That said, you said you were doing this for Diffie-Hellman; generally, for DH, you don't want $g$ to be a true generator (as that'll leak, at the very least, the lsbit of your private exponent); instead, we more usually select $g$ such that the order $q$ is a large prime factor of $p-1$; if we know the size of the subgroup we want, we can stir that into the factorization of $p-1$ when we build it; either by:

Using a Sophie Germain prime (and so $p-1 = 2q$), if $p \equiv 7 \bmod 8$, then $g=2$ will generate the size $q$ subgroup.
Or by picking a prime $q$ perhaps 256 bits long, and then searching for a (possibly composite) value $r$ such that $p = 2rq + 1$ is also prime; we can find our generator by selecting an arbitrary $h$ and setting $g = h^{2r} \bmod p$; if $g \ne 1$, then that's our generator.

All that said, I expect that you don't know enough number theory to go through that yourself.  For decent DH parameters, I send people to this document for precomputed groups; I would recommend the "2048-bit MODP Group" settings.


Pseudo preimage for a hash made from a cipher Consider the Miyaguchi–Preneel construction:

$H_0 = E(0,m_0) \oplus m_0$  (0 here means a vector filled with zeros)

$H_1 = E(H_0,m_1) \oplus H_0 \oplus m_1$

where $E(K,M)$ is a block cipher (for example AES), $m_0, m_1$ are messages.
What's the best way to find messages $m_0$, $m_1$, such that $H_1$ will have a given prefix? $prefix(H_1, len(P)) = P$? Is there a faster way than birthday paradox?

This problem reduces to a standard preimage attack: if the solution can be found faster than with  $2^l$ trials, then a full preimage can be found faster than $2^n$. The latter problem is considered difficult for iterated hash functions based on the Miyaguchi-Preneel construction, as the latter is difficult even when the IV is not fixed.


Homomorphic cryptosystems in RSA Hopefully, Crypto can help me understand homomorphic cryptosystems.

I'm designing a high score server for a game I made, and because of facets in the language I'm using, the player would be able to look through the code and execute functions in my game. So, I'm trying to encrypt the score when it is sent to the server. The suggestion was made on Stack Overflow that I try and use a Homomorphic cryptosystem, which would allow the client's game to add or change the value given by the server, then the server retrieves that value and decrypts it as a highscore. Anyway, what I'm having trouble with is the "homomorphic property", or as Wikipedia describes it:

  If the RSA public key is modulus $m$ and exponent $e$, then the encryption of a message $x$ is given by $\epsilon(x)={x}^{e} \bmod m$. The homomorphic property is then
  $$
\epsilon(x_1)\cdot\epsilon(x_2) = x_1^ex_2^e \bmod m=(x_1x_2)^e \bmod m=\epsilon(x_1\cdot x_2)
$$

Now I understand the arithmetic fine, but don't understand this. Is the homomorphic property showing that the encryption is malleable?

That you can perform operations on two unknown (encrypted) ciphertexts, $\epsilon(x_1)$ and $\epsilon(x_2)$, and recieve the result, $\epsilon(x_1\cdot x_2)$ by preforming $x_1^ex_2^e\bmod m$? Or is it just showing that $\epsilon(x_1)\cdot \epsilon(x_2)$ is the same as   $x_1^ex_2^e\bmod m$?

And subsequently, to decrypt it, you use the RSA private key?

Yes, homomorphic encryption operations are malleable by definition. The definition of "malleable" is something along the lines of "can be intelligently modified", which is what homomorphic encryption allows you to do.

  That you can preform operations on two unknown (encrypted) ciphertexts, $\epsilon(x_1)$ and $\epsilon(x_2)$, and recieve the result, $\epsilon(x_1\cdot x_2)$ by preforming $x_1^ex_2^e\bmod m$? Or is it just showing that $\epsilon(x_1)\cdot \epsilon(x_2)$ is the same as   $x_1^ex_2^e\bmod m$?

Those are the same thing by definition. The encryption operation will allow for the multiplication of two ciphertexts to equal the encryption of the multiplication of the two plaintexts (mod $m$, in your case).

And yes, you would use the RSA private key for decryption. The public key would contain the exponent e in your equation.

Edit, for completeness:

Note that textbook RSA usage (aka, simply taking the plaintext to an exponent) is not secure for several reasons. When security is necessary, we apply a padding scheme to the plaintext before encrypting it (aka, $m$ becomes $p(m)$ for some padding function $p$). But doing so causes the homomorphic usage to multiply the formatted plaintexts instead of the actual original plaintexts (aka, you wind up encrypting $p(m_1) * p(m_2)$ instead of $m_1 * m_2$), which won't yield the desired results. The padding schemes will completely mess up the ability to use homomorphic properties, since multiplying formatted texts yields garbage.

You mention this is for a game, so security may not be of utmost importance (it depends on what the stakes are and what data is involved), but take care before using RSA without any padding; if you do use it, investigate ways to mitigate at least some of the weaknesses of textbook RSA.


How to correctly use RSA for digital signature with hashing? I am trying to understand RSA digital signature algorithm. I am planning to follow these steps:

Sign algorithm:

Take some message $m$
Create digital signature using my private key $[d,n]$: $s = S_a(m) = m^d \bmod n$
Pass my message and signature $[m,s]$

Verification algorithm:

Accept $[m,s]$
Take public key $[e,n]$
Retrieve message: $m' = P_a(s) = s^e \bmod n$
Check authenticity of signature and message immutability by comparing $m$ and $m'$

But I also want to use hashing. I plan to sign not the message $m$, but its hash: $m_{\rm hashed}$. Sign algorithm will probably be changed to:

Sign algorithm (with hashing):

Take some message $m$
Generate hash of message: $m_{\rm hashed}$
Create digital signature using my private key $[d,n]$: $s = S_a(m_{\rm hashed}) = m_{\rm hashed}^d \bmod n$
Pass my message and signature $[m,s]$

I have question about verification steps. Specifically about checking message authenticity in step 4.

Verification algorithm (with hashing):

Accept $[m,s]$
Take public key $[e,n]$
Retrieve message: $m' = P_a(s) = s^e \bmod n$
Check authenticity of signature and message immutability by comparing $m$ and $m'$ ???

Before using hashing we could check authenticity and immutability by comparing $m$ and $m'$. But in this case after step 3, we will get $m'$ as a hashed version (not as original message). How can we compare $m$ and $m'$ if $m$ is original message and $m'$ is hashed version (taking into account that hashing is irreversible and there is no way to decrypt hash back)?

My question: what is the correct algorithm? How to correctly use RSA for digital signature with hashing?

You're missing two things:

First off, we don't try to retrieve the message from the hash; as you correctly point out, that's impossible.  Instead, what we do is (using your notation):

Accept $[m,s]$
Take public key $[e,n]$
Retrieve the hashed message: $m'_{hashed} = P_a(s) = s^e \bmod(n)$
Generate the hash of the message being verified $m_{hashed} = Hash(m)$
Check authenticity of signature and message immutability by comparing $m_{hashed}$ and $m'_{hashed}$

If we assume that the hash function is collision resistant, that is, it is infeasible to find two distinct messages $M_a, M_b$ with $Hash(M_a) = Hash(M_b)$, then if $m_{hashed} = m'_{hashed}$, then either we've demonstrated a hash collision (which we assume is difficult), or $m = m'$.

The other thing you are missing is padding.  We (should) never take output of a hash function, interpret it as an integer, and hand it off to the RSA function; if we do that, then an attacker could potentially take advantage of the homomorphic property of RSA, namely, $a^e \bmod n \times b^e \bmod n \equiv (ab)^e \bmod n$, look through a pile of signatures for hashes that happen to have common factors, and cobble together a signature to a new message (whose hash is made up of those common factors).  Instead, we always apply a padding function to the hash output to turn it into a large (nearly as large as $n$) integer, and then apply the RSA function to that.

There are a number of padding methods known that are believed to be secure, including PSS and RSASSA-PKCS1-v1_5; the reference I gave you short get you started.


Query sensitivity of time series under differential privacy I stumbled upon a paper that proposes local DP around this argument:

A user $u_i$ generates a sequence $s_{i}$ of observations at certain timestamps:

$$
s = ((t_1, x_1), (t_2, x_2), \dots, (t_n, x_n))
$$

The authors apply $(\varepsilon/n, 0)$-DP to each sequence by adding Laplacian noise
As widely known, Laplacian must be of scale $b = \frac{\Delta f}{ \text{budget}}$

The authors propose budget of $\varepsilon / n$, which is IMO correct. But they also define $\Delta f$, aka the sensitivity of the query, as simply the range of any value at any timestamp, $\text{max}(x) - \text{min}(x)$.
I'm not convinced that this is the true sensitivity. To my understanding, the query output is (ignoring the timestamps) not a single value $\mathbb{R}$ but rather the vector of outputs $\mathbb{R}^n$, so per definition of sensitivity $\ell_1$-sensitivity of a function $f : \mathbb{N}^{|\mathcal{X}|} \rightarrow \mathbb{R}^k$:
$$
\Delta f = \max_{x, y \in \mathbb{N}; \| x - y\|_1 = 1} \| f(x) - f(y) \|_1
$$
and properly computing the $\ell_1$ norm as $\| x - y\|_1 = \sum_{i = 1}^{k} | x_i - y_i |$, the sensitivity should be
$$(\text{max}(x) - \text{min}(x))^n$$
Is my reasoning correct (and the paper's DP potentially wrong), or am I missing something? (I don't reveal the paper on purpose.)

Update: Claryfing context of the time series.

The health data stream each user is represented as a sequence $s = ((t_1, x_1), (t_2, x_2), \dots, (t_n, x_n))$

Here, $(t_d, x_d)$ represents the $d$-th point in the stream where $x_d$ denotes the value measured by the wearable health device at timestamp $t_d$.

We further assume that $x_d$, which is measured by the specific sensor in a wearable health device, is within the predefined range $[x_{min}, x_{max}]$.

Their particular use-case is collecting heart rate ($x$) over time ($t$).

I think you should explain what is $x_i$ in this time series. I would recommend linking the paper. I think without a strong context we could answer wrongly because maybe you could have understood something wrong as it has happened to me sometimes. Some points:

Query output could be $\mathbb{R}$ or $\mathbb{R}^n$, depends what kind of query you are defining and using.

You are right, I suspect they are defining a global sensitivity because maybe is easier to compute. But this depends on the kind of query they are defining on the paper, is a linear query, an only-one query  or a non-linear query


Why must curve25519 shared secret be hashed? When using the curve25519 DH function, D.J. Bernstein recommends hashing the shared secret before using it as a session key for a symmetric block cipher. Why is that?

Hashing won't increase the entropy. Do the shared secrets from a curve25519 have some non-random properties that could be exploited if the shared secret isn't hashed?

I am puzzled...

Shared secret resulting from the Diffie-Hellman step is a mathematical object; namely, the X coordinate of a curve point. It is a value in a non-binary range; moreover, it is indistinguishable from randomness only up to the security against discrete logarithm, i.e. about 128 bits. Thus, it is at least debatable that parts of the key might be guessable from the public DH values.

In other words, there are at least 128 bits of entropy ("entropy" here used as a loose meaning for "resistance to guessing attacks") in the 256-bit output of the DH, but you don't know really where. If you extract, for instance, the first 128 bits with basic truncation, then you don't know if you got your 128 entropy bits, or less, possibly much less.

No exploitable bias is really known at that point, but we know enough to be wary. Hashing the DH output is a simple and safe way to gather all the entropy and spread it around as needed, hence the recommendation.


Why should a signature use PSS padding in RSA? Suppose I send a message using AES (private keys already negotiated securely) and I send a hash of this message using RSA (encrypted with private key) with OAEP to verify the authenticity and integrity of the message.

I can decrypt the hash with the public key (authentication) and compare the decrypted hash with a hash I generate from the message (integrity).

Why is it wrong to use OAEP for padding?

RSA-OAEP is an encryption scheme that is CCA secure in the random oracle model (http://en.wikipedia.org/wiki/Optimal_asymmetric_encryption_padding).

You are talking about encrypting/decrypting hashes with some private/public key, but I don't think you're actually talking about encryption schemes. What you probably mean are digital signature schemes (http://en.wikipedia.org/wiki/Digital_signature). RSA-PSS is not an encryption, but a signature scheme and therefore you use that to sign the message.
Signatures and encryptions have different security requirements.

Since you are using a private key encryption scheme it seems that the authenticity of your communication partner might already be ensured (since you already established a common private key). In this case a message authentication code (http://en.wikipedia.org/wiki/Message_authentication_code), which provides integrity guarantees could be sufficient for you.


Homomorphic & Functional encryption: Mapping unencrypted outputs to encrypted outputs using existing data Let's assume I have datapiece A which, after being put through a model or neural network, has a known output X in the unencrypted space. When I move datapiece A into an encrypted space, and put it through an encrypted model, it becomes datapiece e-A. Now, it has output e-X. In this way, I am using a known (unencrypted) data to map X into the encrypted space (e-X).

The model in the unencrypted space has only two possible outputs: X and Y. When I encrypt this model, I'd like there to still be only two possible outputs: e-X and e-Y.

When someone else sends me an encrypted input data, datapiece e-Unknown, I plug it into the function, and I also get output e-X. Since datapiece e-unknown produces e-X in the encrypted space, can it be assumed that datapiece-Unknown also produces output X in the unencrypted space? In other words, does the map from the first paragraph enable deciphering outputs for the anonymized input datapiece-Unknown? Assume datapiece unknown and datapiece A are different (i.e. not exactly the same).

Eval(Enc(f),Enc(dA))=Eval(Enc(f),Enc(dU))⇒f(dA)=f(dU)

where Eval(f,c) stands to "apply f homomorphically to the ciphertext c" .... "f" is the model, "dA" is datapiece-A, "dU" is datapiece-unknown.

If this can be done without encrypting the model, that would also work.

Eval(f,Enc(dA))=Eval(f,Enc(dU))⇒f(dA)=f(dU)

For an unusual use case, I want this to be true. How can I make it work?

Does this hold true for homomorphic encryption? Since h.e. is probabilistic, are there any tricks to make it hold true for homomorphic encryption (e.g. re-seeding with each new input)? If not, why? I am asking specifically about H.E. because a number of libraries already exist that make it easy to use.

Does this hold true for functional encryption? I have heard it does, but there are not many libraries available for functional encryption.

Actually, what you asked is not unusual, even more, it is always true.

Since $Eval(f, Enc(dA)) = Enc(f(dA))$ and $Eval(f, Enc(dU)) = Enc(f(dU))$, if $Eval(f, Enc(dA)) = Eval(f, Enc(dU))$, then $ Enc(f(dA)) =  Enc(f(dU))$.

Now, if you use the decryption algorithm in both sides, you get $f(dA) = f(dU)$.

The same argument applies if we use $Enc(f)$ instead of $f$.

The point now is whether this information is useful or not, because the probability that $Eval(f, Enc(dA)) = Eval(f, Enc(dU))$ is very small: even if $dA = dU$, you are supposed to have $Enc(dA) \not = Enc(dU)$, therefore, the evaluation algorithm is likely to give you different outputs.

So, you would probably never see this event and, consequently, you would not be able to use the conclusion (the right side of the implication).


How exactly is "true randomness" defined in the realms of cryptography? Especially in relation to stream ciphers, I frequently read about (sometimes theoretical, sometimes practical) attacks that are able to "distinguish a ciphertext from a truly random stream".

What's logical to me is that - just because a ciphertext looks random, it isn't necessarily random. Looking around, the general consensus is that "ciphertext needs to be indistinguishable from a stream of truly random bits".

This got me thinking: what exactly is "true randomness"? According to (cryptographically related) definitions I found, "true randomness is unpredictable". So far, so good... but that's also marks the exact point where I've lost it.

"Unpredictable" would practically mean that we have nothing to compare the ciphertext with, because we can not predict what output "true randomness" might produce. Also, there is a (minimal) chance that "true randomness" might output the exact same series of bits as a ciphertext. Meaning: a ciphertext might read 63F1t49X43 and there's a (minimal) chance "true randomness" might produce exactly the same output 63F1t49X43. No one can tell, because "true randomness is unpredictable".

Not being able to predict any true randomness, how can we compare, distinguish, or even claim that a ciphertext is not truly random? Obviously not by comparing it with "true randomness" as that would be impossible due to "true randomness being unpredictable".

Now, I'm pretty sure cryptography is not philosophy and — as a result — I'm absolutely sure I'm missing something obvious in relation to the cryptographic meaning of "true randomness". I'm guessing the details are to be found in the cryptographic definition of "true randomness", which leads to my question:

How exactly is "true randomness" defined in the realms of cryptography?

Practically, I guess you could say that I'm not really sure I correctly understand how someone can provide (cryptographically sound) proof to the claim that a series of bits is truly random when "true randomness" is considered to be unpredictable. So, if you think it's not the definition that might be confusing me here, please feel invited to set my head straight by pointing me to whatever I might be interpreting incorrectly.

EDIT

To avoid misunderstandings: when talking about "true randomness", I'm thinking along the lines of "True Random Number Generators" and not "Pseudo Random Number Generators". That's why I'm asking about "true randomness" and not pseudo-randomness.

Randomness is not a property of strings of bits (or characters of any sort).  Rather it is a property of the process that generates those strings.  However, it is convenient to conflate the string with the thing that produced the string, and thus to speak about strings being “random” or “not random”.

The string 00000, for example, is random if it was the outcome of “random process”, such as a coin being tossed five times and landing on tails five times in a row.  Similarly, the string 1,2,3,4,5,6 is random if it was the outcome from rolling a die six times.  Note, the random process does not need to be “fair” to be random, though processes that deviate substantially from the uniform distribution are not as useful for cryptographic purposes.

What is a “random process”?  As I think about it, a random process is either an indeterministic process (if any actually exist), or a deterministic process for which the entropy of what we don't know (that is germane to the outcome) is greater than the entropy of the generated string.  There is a lot we don't know (and can never know, given the Uncertainty Principle) about the state of the flipped coin – e.g. the exact position and momentum of every particle in the coin, the air around it, and the hand that flips it (all of which are germane, in that we presumably would need to know them to accurately predict the outcome of the flip).

If the string 00000 was the outcome of a number-generating algorithm, where the entropy of what was unknown and germane about the algorithm was less than 5 bits (e.g. we knew the algorithm and all but four bits of information about the seed), then the string would be “not-random”. At best it could be “pseudorandom”, meaning computationally difficult to distinguish from random.


Are PBKDF2 derived keys related if only the number of iterations is changed? I'd like to encrypt my disk with a password.
To generate a nice key from a password, I used PBKDF2, which applies a hash function $k$ times to a cleartext and outputs the final result.
When I modify that encrypted data, I decrypt it, modify it, and re-encrypt it.
When I re-encrypt, I plan to use a different key by increasing the number of PBKDF2 iterations during the key derivation (described soon), i.e., $k$ in the previous description, so that the encryption key differs from those in previous encryptions.
I derive the keys as follows.

$\mathsf{K}_\mathsf{derived} = \mathsf{PBKDF2}(\mathsf{password}, \mathsf{random\_salt})$, which constructs a key from the user-input password.
$\mathsf{K}_\mathsf{master} = \mathsf{HKDF\text{-}Extract}(\mathsf{K}_\mathsf{derived},\texttt{''no salt''})$, which derives a master key with an empty salt.
$\mathsf{K}_\mathsf{data} = \mathsf{HKDF\text{-}Expand}(\mathsf{K}_\mathsf{master}, \texttt{''AES-KEY''})$, which derives a symmetric key for AES encrypting the disk data. The derivation uses the salt $\texttt{''AES-KEY''}$.

where the PBKDF2 uses SHA-256, HKDF-HMAC function is HMAC-SHA256.
I set the parameter of PBKDF2 such that the following two conditions are satisfied:

The initial number of PBKDF2 iterations is large enough, such that the key derivation takes at least 1 second.

The number of PBKDF2 iterations is increased by at least 1 each time the message is re-encrypted.

My question is:

Are keys derived from the same password, but with different numbers of rounds in PBKDF2, computationally related?

If it matters, I use AES-CBC to encrypt, the data is not longer than 1 GB, and I'm only interested in keeping the data confidential.
P.S. I'm not serious about rolling my own crypto, I'm just looking to see if my hunch that this is safe is right or not.

Leave the iterations the same, they should be determined by the CPU time.

Instead provide a different random salt to PBKDF2 on each encryption, you can just concatenate the salt to the encrypted data, it does not need to be secret.

Of course for CBC you also need a new random IV for each encryption, it too can be concatenate to the encrypted.

You should also MAC the encrypted data so that you can determine ion the decryption succeeds, that is the correct key is used.


Using the OTP and RSA compared to only using the OTP itself To use the OTP with RSA, I implemented the one-time pad first for only one time, and then I used the RSA algorithm to encrypt the message.
For the RSA algorithm, I pick $p$ = 2143 and $q$ = 3257, values which do not share any common factors and generate a random value between 1 and $(p-1)(q-1)$. Then generate a public key and private key for RSA encryption and decryption.
My question is: Is it more secure than only using the one-time pad to encrypt the message?

It depends on what you would use the RSA algorithm for since a one-time pad (assuming you implement it correctly) should achieve perfect secrecy, which means its ciphertext cannot be cracked. RSA is one of the first public-key cryptosystems that can also be considered as secure when you are using large enough primes.

So to answer your question, it cannot be more secure than using OTP only since it simply provides the perfect secrecy. But OTP does have its limitations and that's why we have other encryption schemes and algorithms so that we can choose the most suitable one in different situations.


Attacking CBC with predictable but encrypted IV Let P be a secure block cipher, eg AES-128.

Let's say a server has a CBC encryption oracle which uses an attacker-selected yet unique nonce to generate the IV for each message = P(key, nonce). The same key is used to generate the IV from the nonce as to encrypt the message.

This system is not semantically secure against an attacker who can choose plaintexts and nonces (with the stipulation that all nonces must be unique).

A similar system with predictable (but unencrypted) IV has the vulnerability where an attacker can make a guess as to the contents of a target ciphertext.

Is there a comparable attack on this system?

Does this attack still hold if the nonce is merely predictable (ie a counter) instead of attacker selected?

Can this attack work if there is a restriction against sending blocks containing zero-vectors to the oracle?

Generating the IV for CBC mode by encrypting a counter is one of the IV generation methods recommended in NIST SP 800-38A, Appendix C:

  "There are two recommended methods for generating unpredictable IVs.  The first method is to apply the forward cipher function, under the same key that is used for the encryption of the plaintext, to a nonce.  The nonce must be a data block that is unique to each execution of the encryption operation.  For example, the nonce may be a counter, as described in Appendix B, or  a message number.   The second method is to generate a random data block using a FIPS-approved random number generator."

This scheme is also endorsed by the classic paper by Bellare et al., "A Concrete Security Treatment of Symmetric Encryption" (2000):

  "To make a proper counter version of CBC, one can let the initialization vector be $y_0 = f(ctr)$ and increment $ctr$ by one following every encryption.  The scheme is capable of encrypting at most $2^l$ messages.  An analog to Theorem 17 is then possible.  The result is easiest (following as a corollary to Theorem 17) if the key used to determine $y_0$ is separate from the key used for the rest of the CBC encryption."

Alas, their proof is somewhat hard to follow for the casual reader, and frankly, the alternative proof given by Wooding in "New proofs for old modes" (2008) is not much better.1  At least the author is kind enough to summarize their conclusions:

  "We prove that CBC mode is still secure if an encrypted counter is used in place of a random string as the IV for each message."

Indeed, for a reasonably readable proof sketch, you could do worse than take a look at this answer by Seth right here on crypto.SE.

All of these proofs, however, assume that the counter sequence is predetermined.  If the attacker can choose counter values, things fall apart.

In particular, given a known plaintext/ciphertext pair $(P = P_1 P_2 \dots P_n, C = C_1 C_2 \dots C_n)$, an attacker can force the IV to equal any ciphertext block $C_i$ (for $i \ge 2$) by choosing $C_{i-1} \oplus P_i$ as the nonce.

Among other things, this allows the attacker to check whether a ciphertext block $c_j$ (and the preceding block $c_{j-1}$) in another message corresponds to a guessed plaintext $p_j$ by submitting the message $c_{j-1} \oplus p_j \oplus C_i$ for encryption, using the nonce $C_{i-1} \oplus P_i$, and checking whether the first block of the resulting ciphertext equals $c_j$.  This is exactly analogous to the attack based on predictable IVs that you refer to in your question.

1) Actually, the main issue with the Wooding paper is a profusion of notation.  If you can remember what all the variables and functions stand for, it's actually fairly clear.  Still, I'd like to know who (besides, obviously, the author) considered something like "$\scriptstyle \mathcal E\text-CBCH^{\mathcal P^\ell,c,V_0}_{n_L,0,n_E}$" a reasonable notation for an encryption scheme.


Please help me understand this k-out-of-n oblivious transfer protocol I'm having the following protocol specification of a k-out-of-n oblivious transfer (as part of some E-Voting protocol) and it's bugging me that I fail to understand it with my basic knowledge of cryptography.

This particular implementation looks totally different from the usual 1-out-of-n "the receiver generates multiple public keys but only one is valid" examples I can find in the Internet.

Is this OT somehow based on the ElGamal encryption scheme? Especially the exponentiation within a prime order group remind me of it, but I don't see what the PK and SK are?
In order for it to be working, and according to the the final equation $m_{sj} = c_{sj} \oplus k_j$ I'm expecting to get $m_j$ from simplyfing $c_{sj} \oplus k_j$.

$m_j = k\oplus c\\
m_j = H(b\cdot g^{-sr}) \oplus c\\
m_j = H((\Gamma(s_j)\cdot g^{r})^s \cdot g^{-sr}) \oplus c\\
m_j = H(\Gamma(s_j)^s \cdot g^{sr} \cdot g^{-sr}) \oplus c\\
m_j = H(\Gamma(s_j)^s) \oplus c\\
m_j = H(\Gamma(s_j)^s) \oplus (m\oplus k)\\
m_j = H(\Gamma(s_j)^s) \oplus (m\oplus H(\Gamma(i)^s))$

So, $H(\Gamma(s_j)^s)$ must be equal to $H(\Gamma(i)^s)$

How can that be? How can some counter $i$ be equal to the senders query $s_j$? Is the selection $s$ basically the index of $m$ that he wants to receive.

Recall the ElGamal encryption scheme: The secret key is some random $r \in \mathbb{Z}_q$, the public key is $h := g^r$ , together with the group order $q$ and the generator $g$ of the group $\mathcal{G}$. To encrypt a message $m \in \mathcal{G}$, one chooses a random $s \in \mathbb{Z}_q$ and computes the ciphertext $(c_1, c_2) := (g^s, m \cdot g^{rs})$. To decrypt the ciphertext, one computes $c_2 \cdot (c_1)^{-r} = c_2 \cdot (g^s)^{-r} = m$.
In case of your OT scheme, $g$ and $q$ are assumed to be known and are therefore not part of the public key. Now, instead of sending $g^{r_j}$, the receiver sends $\Gamma(s_j) \cdot g^{r_j}$. When the sender raises this to the power of $s$, this results in $\Gamma(s_j)^s \cdot g^{r_j s}$. Hence, the $d = g^s$ and $b_j = \Gamma(s_j)^s \cdot g^{r_j s}$ sent by the sender correspond to an encryption of $\Gamma(s_j)^{s}$. This is then used by the receiver to obtain $H_{\ell}(\Gamma(s_j)^s)$, which was in turn used to (one-time pad) encrypt the actual message. The trick here is to allow the sender to encrypt $\Gamma(s_j)^s$ without knowing $\Gamma(s_j)$.

Yes, the selection $s_j$ corresponds to the $j$th index the receiver wants to receive.


Signature for Identity Verificaton on "offline" P2P network In my scenario i have a very simple P2P network usually working "offline" (i mean that the P2P rely on a detached from internet network).
Each peer on the network is a IoT device bheave automatically, and the first thing it does is present itself to the P2P network trying to join it.
There is no central infrastructure on the network on which i can rely on, so my question is, how can i verfy if a peer that try to join the network is a leggitimate ones and not an attacker?

I have thought to use a private key to identify "me" the network owner (and not shared with the peer) to sign the public key of each peer (different for each peer) that i will relase in the environment (not in a single release).
So when a peer need to present itself to the network other peers (with the public key that identify "me") can see if the peer public key is well signed or not.
But a problem remain, how prevent an attacker with phisical access to a peer to copy its keys (the public with my sign and the private ones) and then impersonate that peer for evil pourpose ?
(how said before each peer on the network is a IoT device easilly accessibile by an attacher and not supervised at all)

If an attacker has full access to the peer then you cannot expect security to be kept. However, you assume that if an attacker has access to a device that it is full under his control.

This assumption is not true in practice if you embed a secure element. A secure element is a device such as a smart card chip that can keep one of more secret values and perform actions on it, for instance signing so it can authenticate itself to the network.

So a secure element can be used to keep your problem from occurring. It is however impossible for a secure element to make a system moderately secure on its own. However, describing such a system is beyond what you can expect from a Q/A site.


What is a "freestart collision"? In their work on SHA-1 collisions (cf. the EUROCRYPT-2016 paper “Freestart collision on full SHA-1” by Stevens, Karpman, and Peyrin) Stevens et al show that they are able to generate "freestart collisions" on SHA-1. They say:

  Even though freestart collisions do not directly lead to actual collisions for SHA-1, in our case, the experimental data we obtained in the process enable significantly more accurate projections on the real-world cost of actual collisions for SHA-1, compared to previous projections.

What is a "freestart collision" on a hash function?

Definition
In the Damgard-Merkle construction for hash functions the compression function takes as input:

a message block and
a chaining value.

For the very first block there is not previous "chaining value". Instead a particular value, called an initialisation vector (IV) is given.
A freestart collision is a collision where the attacker can choose the IV.
In particular in their paper (page 3, Table 2-1), authors found two, slightly, different IVs (only two bits are different):

$IV_1:$ 50 6b 01 78 ff 6d 18 90 20 22 91 fd 3a de 38 71 b2 c6 65 ea
$IV_2:$ 50 6b 01 78 ff 6d 18 91 a0 22 91 fd 3a de 38 71 b2 c6 65 ea

Their attack, as they claim in their work, is the first one to break the whole 80 rounds of the SHA-1 compression function.
Effect
Even if a freestart collision does not immediately give a standard collision, it could be used in multiblock collision search. The chaining value indeed is the compression function output of the previous block.
It is not clear (or at least not to me) how easy the path from a freestart collision to a standard collision is.
As an example: It took 8 years for MD5. The first freestart collision for MD5 was found in 1996 (Dobbertin, Eurocrypt Rump Session) but the first standard collision on MD5 was published only in 2004.
Future work [Next step (from a freestart collision to a full collision)]
Finding out a freestart collision on an hash function does not break completely the function but shows a great weakness. With a freestart collision researchers exhibit the second half of two colliding messages. One could say that we now know how the path leading to the collision but we do not know, yet, where it starts.
Last step left to research is find out a block message $m_0$ which $SHA$-$1(m_0)$ is equal to the freestart IV.
When such message is found, the collision is served. It has to been said that finding out a message that is hashed into a given value is infeasible (it is still an hard problem for the broken MD5 hash function).
UPDATE: The full collision has been found: https://shattered.it/


What is the one-time signature scheme with shortest signature size known? There are several one-time signature schemes. The original one - Lamport - has very big signature sizes (several kbs). Is there an one-time signature scheme on which relies only on simple assumptions (one-way functions and random oracle), and on which signatures are no larger than a few bytes?

Well, if we assume a 128 bit hash function (and arrange things such that we assume only (second) preimage resistance), and use a Winternitz scheme with W=65536 (signing/verifying will be expensive), that'll get you down to about 168 bytes (assuming you insert an 8 byte randomizer into the initial hash, needed if we assume that the attacker can choose the message to be signed).

If we are even more aggressive (80 bit hash; may be good enough assuming it doesn't have to be TLA-proof), and W=$2^{29}$ (so Winternitz needs only a single check digit; signing/verifying will be real expensive), and a 4 byte randomizer, that gets you down to 44 bytes; but you had to make a lot of sacrifices to get to that level.


Curve25519 Endianness According to the original paper form Bernstein public/private keys and the shared symmetric key are stored in little-endian. However, the WolfSSL of WolfSSL supports both, little-endian and big-endian. What is the reason for this? May there be any security issues?

We want to answer "How many wolves are coming to attack?" by "twenty one" (big-endian), not "one twenty" (little-endian). That can be a matter of life and death, and perhaps natural selection of memes¹ made that the convention in many languages (German is an important exception). Big-endian is thus used in most human positional numeral systems.
When it comes to algorithms for exact addition of large integers, it's much easier to start with the low-order digits. Little-endian thus makes sense in some areas of computing, including making a desktop calculator, which was a motivating application of early microprocessors, and got Intel started in that business. That's why little-endian is sometime called the Intel convention.
In network routing according to packet destination address, the low-order bits of a destination address typically does not participate in the routing, and comes last is the destination address field. That could² me made even so slightly advantageous: having the high-order bits first allows to find the destination earlier. That's how I remember big-endian is called "network order".
In computing, the farther away from hardware, the more big-endian. Because predators.
In crypto, both still coexist, but there's a perceptible trend towards big-endianness. MD5 is little-endian (that made the very first collision exhibited wrong), SHA-1 and later hashes are big-endian. That's the NIST order. And ASN.1 integers are big-endian, thus it has won for many practical purposes.
Bernstein has an history of being a skilled low-level programmer of Intel-compatible CPUs (even recommending some), and generally opposes NIST. That's how I remember Curve25519 is nominally little-endian. OTOH, that's a mere convention that should be without cryptographic significance. When adding Curve25519 to something existing, it's possible to get it big endian (by accident or design), and keep/have that as an option.

¹ I know no evidence big-endianness went genetic!
² The tale of traders making special network equipment to crush the last nanoseconds of latency could use that. I can't pinpoint any network equipment, much less a modern one, that does. But I like the idea, and still hope something (a supercomputer cluster maybe) would use it.


How exploitable are cache timing attacks? So there's a recent PHP package that has been written to protect against cache timing attacks, which can be seen here
.

My question is...  just how exploitable are cache timing attacks?

My overall impression is that they're extremely difficult to exploit and attempting to protect against them is rather like using a 1MB two-prime RSA key instead of a 2KB two-prime RSA key to protect against factorization - that it is unnecessary and impractical

An important article from last month on ZDNet shows that cache timing attacks can be very exploitable.

Researchers at Vrije University in Amsterdam announced a new side-channel attack on Intel CPUs called NetCAT.  From the article on ZDNet:

  Named NetCAT, this is a vulnerability in all Intel chips that support
  the Data-Direct I/O Technology (Intel DDIO) and Remote Direct Memory
  Access (RDMA) features.

  When these two features are enabled, academics have shown that they
  can launch an attack on remote, networked computers, and infer certain
  types of data that is being processed inside the CPU's cache.

To emphasize: the attacker does not need physical access to the device.

  VUSec academics have shown that sending carefully crafted network
  packets to a DDIO-capable CPU allows an attacker to keep an eye on
  what else is being processed in the CPU.

In short, NetCAT allows keylogging, and the attacker can even predict the words that will be typed from an SSH session.


Is there a group where CDH is easy but DLog is hard? The question is quite simple:

Is there a group where solving the CDH problem can be shown to be easy but solving the discrete logarithm problem is assumed to be hard?

Refresher on the problems:

CDH: Let $\mathbb G=(G,+,0,p)$ be a public cyclic group of order $p$. Given any $g\in G$ and $g^a,g^b$ with $a,b\stackrel{\$}{\gets}\{0,\ldots,p-1\}$, that is with uniformly random exponents, find $g^{ab}$.
DLog: Let $\mathbb G=(G,+,0,p)$ be a public cyclic group of order $p$. Given any $g\in G$ and $g^a$ with $a\stackrel{\$}{\gets}\{0,\ldots,p-1\}$, that is with a uniformly random exponent, find $a$.

Here is something that is close but not exactly what you're asking for. But it may be enough for what you have in mind.

This paper uses indistinguishability obfuscation to construct a group with self-bilinear map -- i.e., a map $e : G \times G \to G$ (same source & target groups).

  Yamakawa et al., Self-bilinear Map on Unknown Order Groups from Indistinguishability Obfuscation and Its Applications, CRYPTO 2014.

Although I don't completely understand their hardness assumption, and they don't explicitly talk about discrete log, the fact that the "obvious" generalization of Diffie-Hellman gives secure multi-party non-interactive key agreement suggests that discrete log must be hard.

Unfortunately, having a self-bilinear map $e : G \times G \to G$ is not quite the same as a CDH solution! Indeed, their construction uses $e(g^x, g^y) = g^{2xy}$ which is bilinear, but they are in (a subgroup of) an RSA group $\mathbb{Z}_{pq}$ where computing square roots is hard. They explicitly still want CDH to be hard in the group!


Subtracting a point in elliptic curve cryptography? I've had lots of practice adding points for my crypto class. However I've run into a situation where I need to subtract two points for decryption:

Pm + kPb - nb(kG) = Pm

Where Pm is the plaintext, Pb is participant b's public key, nb is participant b's private key, G is a base point in the elliptic group Ep(a,b), and k is a random positive integer chosen by participant a.

I am able to compute nb(kG) and kPb, but I'm unsure how to subtract the two. How is this done?

The inverse of a point $P = (x_P,y_P)$ is its reflexion across the $x$-axis : $P' = (x_P,-y_P)$.

If you want to compute $Q-P$, just replace $y_P$ by $-y_P$ in the usual formula for point addition.


Chosen Ciphertext Attack textbook RSA I'm trying to perform a chosen-ciphertext attack against an RSA oracle.
I have $c$ as the ciphertext I want to decrypt, $e$ and $n$.
I already know that I could choose a number $r$, compute $r^e \cdot c$, make the oracle decrypt, and return $r\cdot m$.
The problem is that this particular oracle checks if $m \bmod mo = 0$ where $m$ is the decrypted ciphertext I sent and $mo$ is the original message which I'm trying to get. If it's equal to $0$ (like $rn$) it won't print $m$ so I can't use that attack.
I don't really know what to do.
$n$ is pretty big (1024bit) so I can't factorize it. Maybe there is a small adjustment to the mentioned attack, but I'm really stuck. If anybody could give me a hint I would really love it.

Thanks to the help of @kelalaka i found a solution.
The idea
My exploit was based on the fact (I don't really know if it's always true) that if $r \cdot mo < n$ the oracle won't print anything, otherwise it will print some number, which unfortunate is not $r \cdot mo$.
So, $\lfloor \frac{n}{mo} \rfloor^e \cdot (mo^e \mod n)$ would produce no answer ($\lfloor \frac{n}{mo} \rfloor \cdot mo < n$) while $\lfloor \frac{n}{mo} + 1\rfloor^e \cdot (mo^e \mod n)$ would produce an answer, even if uncorrect.
The solution
First I choose a number $r$ smaller than the original message $mo$. Then, until the oracle responds i keep sending $r\cdot 2^i$ increasing $i$ by $1$ each step.
When the oracle respond it means that I found a number $s = r\cdot 2^{i-1}$ such that

$s < mo$
$2s > mo$

Let $k:=\frac{s}{2}$. I iterate the following process until $k > 0$:

I send $s+k$.

If the oracle responds it means $s+k > mo,$ so I assign $k:=\lfloor k/2 \rfloor$
If the oracle doesn't respond it means $s+k < mo,$ so I assign $s:=s+k$

In the end $s$ should be exactly $mo$.
The "algorithm" (it's a bit confused, I'm sorry) I proposed should get $mo$ in $O(\log_2 n)$ so it's tractable.


Make AES more secure by randomising the blocks in an encrypted file I am developing a software with hybrid encryption (RSA-4096 and AES-256-CBC).
The iv and key of an AES encrypted file will be RSA encrypted end exchanged through a different way than the encrypted file. Thats ok for me to this point.

I am thinking about where it is most easy to break the encryption of my own files and always come to the point where a key and iv guessing would take ages but is theoretically easy. It just takes time with the computing power we have today.

In my application the transfer of the encrypted file will not be possible if there are bits lost in any case.

Version 1:
Since CBC is always based on the the pre block, why do I not just change the order of the blocks in the file and write a map together with the key and iv into the RSA part? Is this a stupid idea?

Version 2:
Why do I not just replace a random character in each AES block with its "value" + 1 or so and write into my RSA a map of the chawed characters?

In my opinion in Version 1 the "guessing power" would be the "AES blockcount"*"time for a single file" and after that the order would sill be wrong. I have no idea what effort it would take to get the right order...

In the second Version it would be even to hard for me to calculate. It could be any bit in a block with a wrong value and a guessing of iv and key per block.

Does that make sense? Who knows about the computing power we will have in a few years. And I also don't want people to read the files in a few years ;-)

TL,DR: No, don't do it. Use a standard protocol and don't write your own implementation. If you're thinking at the level of AES, CBC and RSA, you're doing it wrong. I recommend crypto_box.

  I am developing a software with hybrid encryption (RSA-4096

RSA-4096 is ok if done right. Done right means OAEP or RSA-KEM. PKCS#1v1.5 is theoretically possible to get right, but very difficult because it is prone to oracle attacks. A lack of padding or homegrown padding is plain broken. ECIES gives you as much or better security at much better performance, and typically fewer risks of getting it wrong due to insecure parameters.

  and AES-256-CBC).

Unauthenticated modes are dangerous because they are prone to oracle attacks. Even PGP got it wrong. Don't use unauthenticated modes. And especially don't use CBC, which has padding, which allows even more oracle attacks.

You might think you don't care about authentication, but you're probably wrong. If someone can send fake messages, that does help them obtain the content of confidential messages. The efail attack on PGP works by piecing parts of legitimate messages into fake messages and having the fake messages (attempt to be) decrypted. Use GCM or CCM instead (or use ChaCha20_Poly1305 instead of AES-GCM or AES-CCM). (But as I said earlier, what you should really be using is something like crypto_box.)

Also note that using authenticated encryption prevents oracle attacks at the level of the symmetric cryptography, but it doesn't prevent similar attacks at a higher level, since an attacker can make up their own symmetric key and send whatever they want by encrypting their own symmetric key with the public key. You should sign messages (sign (a hash of) the plaintext) with a separate set of asymmetric keys, where the sender holds the private key and the recipient knows the sender's public key (or can get it from a reliable source).

  The iv and key of an AES encrypted file will be RSA encrypted end exchanged through a different way than the encrypted file.

You can, and typically should send the IV with the file. The IV doesn't need to be confidential. The AES key is encrypted with RSA (that's how hybrid encryption works) and the encrypted AES key is typically sent with the file. The RSA private key is typically never transmitted at all: that's the point of asymmetric cryptography.

You do need to take care of transmitting the public RSA key separately, but that's a whole different issue which I won't go into here.

  I am thinking about where it is most easy to break the encryption of my own files and always come to the point where a key and iv guessing would take ages but is theoretically easy. It just takes time with the computing power we have today.

No, guessing the key is the hardest way to break the encryption. Nobody can break AES by guessing the key. It's theoretically easy, but practically impossible because it takes far, far more time than you have. If you took all the existing computing power on Earth now (yes, including NSA's) and ran it for the current age of the universe, you would still not stand a good chance of guessing an AES-128 key.

The way cryptography gets broken in the real world is not because the building blocks are weak, but because people take strong building blocks and assemble them badly.

  Version 1: Since CBC is always based on the the pre block, why do I not just change the order of the blocks in the file and write a map together with the key and iv into the RSA part? Is this a stupid idea?

You can only send a limited amount of extra data in the RSA part, so that would limit the size of the message. For a very short message (up to about 15–20 blocks — $\log_2(15!) \approx 40$, $\log_2(20!) \approx 61$), all possible permutations can easily be enumerated, so you have no security gain. For longer messages, what do you gain? The attacker has undecipherable blocks in some unspecified order. They're undecipherable anyway. The attacker can't even distinguish between the blocks.

So maybe you have extra security in case something else is broken? Think again. If the permutation gives extra security, it can only be because the attacker cannot distinguish between the blocks: otherwise that means the attacker can reconstruct the permutation. And if something else is broken, broken means that the attacker does have extra knowledge about the blocks. This extra knowledge isn't absolutely guaranteed to let the attacker know which order to put them in, but it's likely to help.

So the offshoot is that no, you're very unlikely to gain anything. What do you have to lose? Well, once again, where cryptography gets broken is because the building blocks are misused. Every extra complexity that you add increases the attack surface of both your protocol, and your implementation. Doing extra stuff makes your protocol less secure, not more.

  Version 2: Why do I not just replace a random character in each AES block with its "value" + 1 or so and write into my RSA a map of the chawed characters?

For pretty much the same reasons as version 1, this has a cost and no advantage. You'd just be increasing the attack surface to make indistinguishable blocks indistinguishable.

  Who knows about the computing power we will have in a few years.

To be resistant to quantum computers in case they actually become useful to break cryptography, use AES-256. Quantum computers basically halve the effective key size of symmetric algorithms. AES-128 is good against classical computing but fails to a quantum computer that's able to perform about $2^{64}$ (a few billion billions) operations.

The asymmetric part is more problematic. We don't have a widely accepted asymmetric encryption algorithm that would resist quantum computers.

But by far, the biggest risk in what you want to do is design and implementation mistakes. The worst thing you can do is to devise your own protocol. What you should do is:

Use an existing, vetted implementation of an existing, vetted protocol. To encrypt some data with an asymmetric key scheme, crypto_box has a good reputation.
Be agile: prepare to upgrade your protocol if it gets broken.


Reversed Fibonacci LFSR taps In the classic "Applied Cryptography" (20th anniversary edition) book from Bruce Schneier, there is an illustration of a maximal-length LFSR:

According to the book, this LSFR uses the tap sequence from the polynomial $x^{32}+x^7+x^5+x^3+x^2+x+1$ which is maximal-length.
However, most examples I found online (e.g. Wikipedia) increment the numbering of the shift register bits from the input to the output (left to right)—which could just be a different convention—but the taps are also reversed. On this figure that would translate to taps on $\{b_1,b_{26},b_{28},b_{30},b_{31},b_{32}\}$.
I would normally tend to trust more a reference book rather than random online sources but I found an alarming amount of counter examples. Are the taps placed correctly on the above figure?

Are the taps placed correctly on the above figure?

No. That's acknowledged in the errata to the second edition, on the section for page 375 (AFAIK the 20th anniversary edition is essentially the second edition with a little extra at the beginning).
My preferred method to determine the hardware implementation for a Fibonacci LFSR from the polynomial:

Use a shift register with as many bits as the degree of the polynomial.
Number shift register state bits (the output of the internal D gates) from $0$ for the output, to $n-1$; with thus $n$ the input of the shift register.
XOR the bits $i$ from $0$ to $n-1$ of the shift register that has their term $x^i$ present in the polynomial¹ ($x^0$ is the term $1$ of the polynomial).
For an LFSR in scrambler configuration, additionally XOR the input of the scrambler.
Feed the result of the XORs to the input of the shift register.

Depending on convention, the taps shown are for polynomial $x^{32}+x^{31}+x^6+x^4+x^2+x+1$ or it's reflected polynomial $x^{32}+x^{31}+x^{30}+x^{28}+x^{26}+x+1$. These are not primitive², and accordingly, the sequence for the LFSR shown is not maximal-length.
LFSRs and CRCs are an area where there are many errors in literature and implementations, and several justifiable conventions around, especially for Fibonacci LFSRs:

There is no universal agreement that the low-order coefficient of the polynomial is on the output of the LFSR. Using the other convention¹ causes a reflection in time of the order of the bits in the generated sequence, for the reflected initial state.
The most common convention for an isolated LFSR is that the output of the LFSR is the output of the shift register, so that the first bits to the output match the initial state of the shift register. But the common convention for LFSR-based scramblers is that the output is the input of the shift register, which reduces latency in telecom applications. That offsets the generated sequence.
There is no universal agreement on numbering bits of the shift register/initial state from output to input. This is best IMHO since it matches the order in which output bits appear, and people agree on numbering these incrementally with time.
There is no agreement on numbering shift register bits starting from 0 (as in the above method) or from 1 (as in the question's figure). The same issue for output bits in the generated sequence, and I've seen the conventions differ.

Lots of theoretical work, high-speed hardware, and software use Galois LFSRs. There's relative agreement that if their $n$-bit polynomial is $P(x)$, then their state $S(x)$ is a polynomial of degree (at most) $n-1$ with state bits numbered from $0$ to $n-1$ according to rank in $S$. The state changes from $S(x)$ to $x^k\,S(x)\bmod P(x)$ after $k$ steps. Good luck for the rest.
Galois LFSRs are easily implemented in hardware and software:
s = (s<<1)^(p&-(s>>(n-1)));   // Galois LFSR, assuming s an unsigned exactly n-bit
s = (s>>1)^(q&-(s&1));        // Galois LFSR, reflected, assuming s at least n-bit

Note: p is the polynomial evaluated without it's high-order term in $\mathbb Z$ for $x=2$. q is the polynomial reflected, then evaluated without it's high-order term in $\mathbb Z$ for $x=2$.
The output sequence of a Fibonacci LFSR with term $1$ present in it's polynomial matches that of a Galois LFSR with the reflected polynomial (using the conventions above), and an appropriate adaptation of the initial state (which depends on conventions about where the output sequence is extracted from).

¹ Another possibility is to XOR the bits $i$ that have their term $x^{(n-i)}$ present. That works only if the term $1=x^0$ is present in the polynomial, which is true for all polynomials used in practice, all irreducible polynomials, and thus all primitive polynomials (which are those generating a maximal-length sequence when starting from a non-zero initial state, and input at $0$ if in scrambler configuration). The sequence generated is generally not the same.
² Proof: every primitive polynomial is irreducible, and $x^{32}+x^{31}+x^6+x^4+x^2+x+1$ is not, since it's divisible by $x^{14}+x^{13}+x^{12}+x^{11}+x^{10}+x^9+x^4+x^3+1$. A polynomial and its reflection have the same status w.r.t. primitiveness and irreducibility.


What is the "artificial abort" technique? In the security proof of Brent Waters's paper Efficient Identity-Based Encryption Without
Random Oracles, he uses a novel “artificial abort” step on page 6.

  At this point the simulator is still unable to use the output from the adversary. An adversary’s probability of success could be correlated with the probability that the simulator needs to abort. This stems from the fact that two different sets of $q$ private key queries may cause the simulator to abort with different probabilities.

What is the purpose of this step?  Also, I am confused by the first sentence above.  What goes wrong if I just use the output from the adversary without this artificial abort step?

The problem that arises in the security proof is that the adversary who may win the real game with some probability may however cause the simulation to nearly always abort (by issuing a private key query that requires the simulation to abort) and the probability of an abort may be different for different sets of private key queries.

So, the problem is that the reduction may not be able to use the adversary as the simulation may arbitrarily fail (the success probability of the reduction is conditioned on the adversary not causing an abort) and thus the proof does not go trough. The problem is not to "just use the output", the problem is that you would not be able to get the security proof done without any additional measures.

Now, if the upper and lower bound on the probability that the adversary causes an abort are closely related, the adversary can be used in the reduction as you know that the simulation will always abort with the same probability and then the proof goes through. Note that this introduces a loss in the tightness of the reduction.

Waters therefore cleverly introduced artificial aborts, which basically means that the reduction at the end of a successful simulation (one that did not abort) estimates the probability of abort for hypothetical simulations with the adversary for the same set of private key queries. The reduction then artificially aborts with some probability related to the probability computed before. This is quite counter intuitive as the reduction after a successful run aborts, but this allows to prove the closeness of lower and upper bound on the probability of abort and makes the reduction work and the proof go trough.

There is a paper from EUROCRYPT 2009 which shows how to eliminate the requirement of artificial aborts and thus complicated security proofs for the Waters scheme.


Can I use a one time pad key twice with random plaintext? I understand the basics of OTP: $|\text{key space}| = |\text{plaintext space}|$ implies perfect security, key reuse destroys this.

Cryptanalysis on the $N$-Time Pad for $N > 1$ involves finding patterns in the ciphertext; this, however, all seems based on the premise that patterns exist in the plaintext (e.g. English language).

My question is: if $m_1$ and $m_2$ are two truly random strings, and they are both encrypted with the same OTP key to yield $c_1$ and $c_2$, is it possible to recover $m_1$ and $m_2$ from $c_1$ and $c_2$?

In other words: while "perfect security" (aka perfect indistinguishability) is obviously lost (constructing a distinguisher for two messages is trivial), is the plaintext still safe?

Yes, encrypting two different random "plain texts" with the same "pad" is indistinguishable from using two different random one time pads for encrypting the same plain text. You get perfect secrecy in the latter case, so you will get corresponding secrecy in the former case as well.

However, usually there is a functional difference between the key and the plain text that the above argument doesn't account for. More precisely, the recipient will usually "do things" with the plain text once decrypted, and in that respect the above argument might fail.

For instance, if the random messages are symmetric encryption keys for a cipher that is vulnerable to a related key attack, it is obviously not safe to transport those messages encrypted with a reused pad.


AES-ECB Reverse attack CTF We have a key representing an SHA-256 hash in HEX, and we have the key in AES-ECB. We also have a file with plaintext to cipher messages that were encrypted with our key. How could we find this key?
8cb78d34edfec9db1fa4a044f14c06cd5d9aa8a4fece263c439c5fa62dd1fedadf757d79fa6a28069ddcba4ca624c9694559483254896625392f70bf7df4dd66

The above is the flag encrypted in AES-ECB, we know that the flag is a hex representation of an SHA-256 hash:
79621ca63d052e64 --> ca5b6fdb77e3b1ec39b6c4e1a4b69ba5

55191c3c4eeb107e --> ded63de07b250d83f842d7bc860db40c

We have a whole list with plaintext that was encrypted with our key (flag).

ECB is weak because a given 128 bit input block maps to the same encrypted output block. The only thing you can do is look for matches between blocks of the encrypted flag and outputs in the known plaintext ciphertext pairs file.
Essentially for each 128 bit chunk of ASCII text in the flag E(plaintext)=ciphertext. The known plaintext ciphertext pair file is essentially a big table of E(plaintext)=ciphertext for a bunch of plaintext ciphertext pairs. If you find one of the encrypted flag blocks in that file:
8cb78d34edfec9db1fa4a044f14c06cd
5d9aa8a4fece263c439c5fa62dd1feda
df757d79fa6a28069ddcba4ca624c969
4559483254896625392f70bf7df4dd66

You have the decryption for that block. Just ctrl-f for these values and assemble the decrypted chunks to find the unencrypted flag. They have to be there for the CTF to be solveable.


Modular equation system I have $N=p\cdot q$ and the following system where I know $A,B,C,D, k$:
$$A = B \cdot q^k \pmod N$$
and
$$C = D \cdot p^k \pmod N$$
Is there an easy way to recover $p$ and $q$?

Is there an easy way to recover $p$ and $q$?

Yes (in all cases except for $B, D$ are both multiples of $N$, or $k=0$, and assuming that $p, q$ are distinct primes)
Let us assume that $B$ is not a multiple of $N=pq$; then:

If $B$ is not a multiple of $p$, then $\gcd(A, N) = q$ (because $A=Bq^k$ is a multiple of $q$ but not $p$); simple division also recovers $p$

If $B$ is a multiple of $p$, then it is not a multiple of $q$ (by assumption); in that case $\gcd(B, N) = p$


The Secp256k1 curve is used in cryptocurrency. Can someone generate a private key with a different curve? Many cryptocurrencies use Secp256k1.

Every cryptocurrency library comes with its own redundant implementation of Secp256k1, ECDSA, RIPEMD160, and SHA256. So, there can be some inconsistencies across implementations.

What if some library generates a private key using a different curve than Secp256k1? For example, one with less security, or even a backdoor. Choosing different points, etc.

Then they share only the public key with blockchain, of course. Is it possible that such a thing would work? Can some public key appear valid for Secp256k1, but in fact use another elliptic curve?

I just came across many open source cryptocurrency libraries where they generate private keys and everyone is using custom implementations of these. So I should at least compare source code and look for some specific set of constants.

The Bitcoin network expects secp256k1 when adding something to its blockchain. If you use another curve, it naturally will not produce a valid secp256k1 public key capable of validating the secp256k1 signatures and will be rejected by the network. If some client uses a bugged or even backdoored version of the curve, the client will simply not be able to add anything to the blockchain. This would only become a risk if a significant portion of the network ended up using this same bad library, effectively resulting in a fork of the core client and an entirely new, separate protocol.


Needing to encrypt plain sight information Okay here are my requirements.

I need a solution that can do the following.

Lets say I have an encrypted piece of text with the value "20".

and I have UserA and UserB

I give UserA the Keys (/5 and /2), meaning divide by 5 and divide by 2.
I give UserB the Key (/10 and /1) meaning divide by 10 and divide by 1.

using both operations, both UserA and UserB can arrive at the same result the un-encrypted text of "2".

The first operation could be their "SessionID, the second could be a corresponding key for the Session".  Two different users, using two different "Keys" can decrypt the ciphertext using two different but equal operations.

Is there something similar in cryptography where you can provide different keys or functions and arrive at the same result and is cryptographically secure.

The answer in the comments from dchest is probably the most standard. Encrypt the page with a single, random key. Then encrypt that key for each user using the shared secret that you hold with that user.

It is unclear whether this meets your needs as it is unclear exactly what your needs are.

With that in mind, a fairly advanced way you could get the functionality you require is with Ciphertext-Policy Attribute Based Encryption. It is very complex and would require a lot to describe in this answer (and I don't even know if it meets your needs as they seem to not be fully defined at this point).