The security proof for Key Policy Attribute Based Encryption My question relates to the original KP-ABE paper:

http://research.microsoft.com/en-us/um/people/vipul/abe.pdf

I'm having trouble understanding the proof (pages 10–13) that the scheme is secure in the Selective Set Model:

  Proof: Suppose there exists a polynomial-time adversary A, that can attack our scheme
  in the Selective-Set model with advantage $\epsilon$. We build a simulator B that can play the Decisional BDH game with advantage $\epsilon/2$. The simulation proceeds as follows:

  We first let the challenger set the groups G1 and G2 with an efficient bilinear map, e
  and generator g. The challenger fips a fair binary coin $\mu$, outside of B's view. If $\mu = 0$, the challenger sets $(A, B, C, Z) = (g^a,g^b,g^c,e(g,g)^{abc})$, otherwise it sets $(A, B, C, Z) =(g^a, g^b, g^c, e(g,g)^z)$ for random $a, b, c, z$. We assume the universe, U is defined.

  ...

  Phase 1 A adaptively makes requests for the keys corresponding to any access structures T such that the challenge set $\gamma$ does not satisfy T . Suppose A makes a request for the secret key for an access structure T where $T(\gamma) = 0$. To generate the secret key, B needs to assign a polynomial $Q_x$ of degree $d_x$ for every node in the access tree T .

  We first define the following two procedures: PolySat and PolyUnsat.

  PolySat$(T_x,\gamma,{\lambda_x})$ : ....

  PolyUnsat$(T_x,\gamma, g^{\lambda_x})$: This procedure sets up the polynomials for the nodes of an access tree with unsatisfied root node, that is, $T_x(\gamma) = 0$. The procedure takes an access tree $T_x$ (with root node x) as input along with a set of attributes $\gamma$ and an element $g^{\lambda_x} \in G1$ (where $\lambda_x \in Z_p$).
  It first defines a polynomial $q_x$ of degree $d_x$ for the root node $x$ such that $q_x(0) = \lambda_x$. Because $T_x(\gamma) = 0$, no more than $d_x$ children of $x$ are satisfied. Let $h_x \leq d_x$ be the number of satisfied children of $x$. For each satisfied child $x'$ of $x$, the procedure chooses a random point $\lambda_{x'} \in Z_p$ and sets $q_x(index(x')) = \lambda_{x'}$. It then fixes the remaining $d_x - h_x$ points of $q_x$ randomly to completely define $q_x$.

  ...

  To give keys for access structure $T$, simulator first run PolyUnsat$(T,\gamma,A)$ to define a polynomial $q_x$ for each node $x$ of $T$.

  ...

My question is relating to the last (bold) paragraph: How is it possible to define such $q_x$, since the simulator cannot learn $\lambda_{x}$ from $g^{\lambda_x}$ unless he can compute discrete log?

Because the simulator picked   $\gamma$ to generate $g^\gamma$.  He acts as an ABE authority for an attacker who breaks the Selective Set Model security game so he can use the attacker to solve the   Decisional Bilinear Diffie-Hellman problem .

As a result of being  the ABE authority, the simulator  knows  the master secrets and all other secrets created by the ABE authority. Remember, that for normal ABE, the authority knows everything, including user's private keys (attributes).

  Proof: Suppose there exists a polynomial-time adversary A, that can attack our scheme
  in the Selective-Set model with advantage $\epsilon$. We build a simulator B that can play the Decisional BDH game with advantage $\frac{\epsilon}{2}$. The simulation proceeds as follows:

  We first let the challenger set the groups G1 and G2 with an efcient bilinear map, e
  and generator g. The challenger flips a fair binary coin $\mu$, outside of B's view. If $\mu$ = 0,
  the challenger sets $(A; B; C; Z) = (g^a, g^b, g^c, e(g, g)^{abc} )$ otherwise it sets
  $(A; B, C,Z) =
(g^a, g^b,g^c, e(g, g)^z)$
   for random $a, b, c, z$. We assume the universe, $U$ is defined.

The simulator, then, gets to set up an ABE system so he can use the attacker

  The simulator B runs A. A chooses the set of attributes $\gamma$ it wishes to be challenged upon

$\gamma$ has nothing to do with the DBLDH assumption.


How can I validate generated session keys in SRP-6a protocol I have genereted two equal session keys on client and server successfully. But I couldn't understand how each other should validate that they have same session keys.

On the client I generated a SHA1 hash with equation p = SHA1(A | B | S) where A and B are public keys of client and server and S is the SHA1 hash of the session key. Then I sent this hash without any encryption to the server.

Server then calculates p with its own hash of session key and compare with the incoming one.

Is that the supposed way of validating keys in SRP ?

And while client is connecting to other server in cluster, what is the best way to authenticate connection ?

Nimbus or Thinbus are two popular SRP implementations in Java and Javascript compute the proof of password as you describe H(A|B|S) where you can supply your own hash functions such as SHA1 or SHA256 or stronger.

The actual protocol design document states H(H(N) xor H(g), H(I), s, A, B, K) where K=H(S) so that expands to H(H(N) xor H(g)|H(I)|s|A|B|H(S)). The longer approach includes N, g, s which is the safe prime, it's generator and I the user identity and s the users salt. Those are not secret. The secret is S and adding more bits into the hash is done to protect leaking information about that secret. The secret is also the only component which is derived from the password if you are talking to an attacking server so needs to be well hashed. So both approaches involve A which is the secure random chosen by the client to conceal the secret.

In the protocol design document the server then responds with H(A|p|K) which expands to H(A|p|H(S)). The p is the value used to check the client holds the password which has already computed to check the client.

Once again all the proofs, including the server proof, include A which is the random chosen by the client. If that is a secure random it provides protection against a fake server attacker which may be supplying a not random B and a bad salt as part of an attack.

So why would Nimbus and Thinbus go with H(A|B|S) rather than the more complex password proof using more bits from the public values? (Nimbus will actually let you plugin your own proof function but that is the default). The original SRP RFC was using SHA1 which is now considered weak one can see why it might throw more bytes into the hash and also double hash the S to better protect it. With Nimbus and Thinbus the recommended hash function is SHA256 or higher. So the random numbers used to generate A and B will be that many bits. The choice of a more secure hash algorithm and larger random numbers is considered enough to protect from leaking information about S which may leak information about the password.


Perform ENT / Dieharder on raw entropy or on whitenened entropy? In this question about hardware random number generator, a discussion about the following question has been started: In order to test RNG's and entropy's quality, should test suites like ENT and Dieharder be applied on raw entropy or on whitened entropy?

It depends on the goal of performing the test:

If the goal is to test for a problem in the whitening, then the test should be run on the whitened output, of course. If the test fails (more often than predicted by the P-value), the whitening is demonstrated bad. If the test pass, we can deduce nothing cryptographically useful (the source or the whitening could be badly defective, or/and the tested output could be totally predictable by who knows how it was generated). The test is slightly less pointless if the source is replaced with a very low entropy source during the test.
If the goal is to test for a problem in the noise source, then the test should be run on the noise source before whitening. If the test fails (more often than predicted by the P-value), then the noise source is demonstrated not good enough to be used for cryptographic purposes without whitening (but it might still be excellent and perfectly usable with whitening; many if not most good truly raw sources fail Dieharder, some fail ENT). If the test pass, we can deduce nothing cryptographically useful without knowledge of how the noise source is actually operating, and of how the test works.
If the goal is to pass a conformance test, then the rule it to perform things as satisfies the person with the rubber stamp. If s/he does not care, the easy route is to use the whitened output, so that a good whitening is a sufficient way to pass the test, irrespective of the source. I guess that happened (for FIPS 140-1 and -2 conformance, some tests where mandatory and too stringent for most practical sources; reason prevailed and the tests have been removed, yet the tests remain what some suppliers of RNGs brag about).

There is no other rational goal met by solely performing a RNG test on a sequence, when it passes. Repeating the first bullet: if the test is a blackbox test on the whitened output of a source, then a pass indicates nothing cryptographically useful about the source, the whitening, or the combination.

I have assumed the test is at least correct (and in particular, fails with likelihood comparable to its stated P-value when given truly random input), and correctly used. That's more often than not disproved by repeatedly applying the test to the output of a known-good CSPRNG. The test should pass (with occasional failures per its P-value) regardless of the CSPRNG's input (as long as it is arbitrary rather than tailored to the test being tested).

Note: ENT is a terrible test from a cryptographic standpoint, especially for a whitened source. For example, a PRNG that 90% of the time outputs a byte equal to one more (modulo 256) than the previous one, and is random the other 10%, is still considered perfectly OK.

Note: Temperature or process variations, EMI, aging, adversarial influence, or Murphy's law, can ruin a noise source. In cryptographic devices it is thus critical that the proper operation of the noise source is continuously monitored. A technically valid security certification process aims at checking source, whitening, and that monitoring puts the whole device in a safe state (as a minimum: squelches the whitened output) on detection of failure. This goal is antagonist to field reliability, and it is hard to get both.


How can I validate my implementation of Ansi 9.19? I implemented an Ansi 9.19 mac generator in java, but now I don't know how to validate its functionality. I couldn't find any sample of a {plain text,key,mac} on the internet, and I want to know if there is a good way to test my implementation.

Bouncy Castle has an ISO 9797/ANSI 9.19 Mac implementation with a test vector.

Botan also has an implementation and test vectors, which cross-verify with Bouncy Castle (at least the 128 bit key ones anyway).

From the looks, official test vectors appear to be scarce (unless you want to pay for a copy of the standard and chance one being in there), and it's less than clear that the BC/Botan vectors are official, so cross testing with existing implementations might be the best you can manage.


Formal verification in cryptography I have seen in some places that people use formal verification and/or computer-aided verification for cryptography (tools like ProVerif, CryptoVerif, etc.).

How do these approaches work?

Disclaimer: I use Coq on daily basis...

  I have seen in some places that people use formal verification and/or computer-aided verification for cryptography.

To my knowledge, there aren't that many places that do such a thing.

First, let's define our concepts:

Formal Verification: The act of proving the correctness of algorithms with respect to a certain formal specification or property, using formal methods of mathematics.

Computer-assisted proof: A proof that has been at least partially generated by computer.

Some examples (in cryptography):

Verification of a Cryptographic Primitive: SHA-256 (paper)
Formal certification of game-based cryptographic proofs (PHD)

And some reading:

A gentle introduction to formal verification of computer systems by abstract interpretation (paper)
A Foundational Proof Framework for Cryptography (PHD)
Computer Verification in Cryptography (paper)
Probabilistic Relational Verification for Cryptographic Implementations (paper)

How does it work?

In formal methods (whatever the domain) there are two approaches:

Specification $\rightarrow$ Software
Specification $\wedge$ Software $\rightarrow$ Prove the software's correctness.

In most cases, the first method is the one used. Why? Because it is easier to start with a formal specification and then, incrementally, through proven steps, eventually get to the software (which is therefore proven). As an example, this certified compiler:

For example in the Method B, the process is the following:
$$DEFINE\ /\ SPECIFY \rightarrow PROVE \rightarrow  REFINE \rightarrow PROVE \rightarrow  \ldots \rightarrow IMPLEMENT$$

Formal verification uses the Hoare logic, a set of rules that allows us to reason about programs. It is based on sequent calculus and natural deduction. It relies on the Hoare triple:
$$\{P\}\ C\ \{Q\}$$
When the precondition $\{P\}$ is met, the execution of the command $C$ establish the postcondition $\{Q\}$. If the command $C$ goes from a state $s$ to a state $s'$.
$$C: s \rightarrow s'$$
Then you will have to prove:
$$\forall\ s\ s', P[s] \implies C : s \rightarrow s' \implies Q[s']$$
But we prefer the Hoare triple notation (lighter).

As an example, this is the rule for $SKIP$ (aka do nothing):
$$\frac{}{\{P\}\ SKIP\ \{P\}}$$

And this is the rule for the sequence :
$$\frac{\{P\}\ C_1\ \{Q\}\ \ \ \ \ \ \ \{Q\}\ C_2\ \{R\}}{\{P\}\ C_1 ; C_2\ \{R\}}$$
This notation is read as :
"If $\{P\}\ C_1\ \{Q\}$ (is $\text{True}$) and if $\{Q\}\ C_2\ \{R\}$, I can infer $\{P\}\ C_1 ; C_2\ \{R\}$.

A proof is therefore built from bottom to top : if you want to prove $\{P\}\ C_1 ; C_2\ \{R\}$, you will need to prove there is $Q$ such as $\{P\}\ C_1\ \{Q\}$ and $\{Q\}\ C_2\ \{R\}$.

Some readings on Hoare logic:

Background reading on Hoare logic (course)
Handout C2: Reasoning About Code (Hoare Logic) (course)
Software Foundation (self study course, highly recommended if you want to get into the domain).

The tools

In formal methods, there are two kinds of tools:

the fully-automated prover
the proof assistants

The first are mainly based on SMT (satisfiability modulo theories) such as Atelier B and Alt-Ergo.

The second ones are based on pure logic. You provide it with lemmas (helping theorems), and this will make sure that every step you do in your proof is right. It is a very thorough process, quite slow. But at the end you know how your proof works and that it is correct because you did not miss a hypothesis. The process, which can be frustrating, will make sure that the proof works.
The main proof assistants are the following: Coq,
Isabelle, Agda, Fstar and HOL.

The tools you mentioned (ProVerif, CryptoVerif) are not dedicated to cryptographic primitives, but protocol verification. I do not know them, so I will not comment. Other tools on the same subject do exist. For example:

CertiCrypt
EasyCrypt (tutorial)

And yes, they are based on Coq.

In C, in order to be able to verify your code matches your specification (such as what has been done for $\text{SHA-}256$), one need to extract the semantic from the code. This could be done using the Verifiable Tool Chain or Why3. The first one will provide you a Coq file from which you will be able to start your proofs. The second one, given C ASCL instrumented code, will use frama-c and try to prove the properties with the SMT provers named above. On failure, it generates goals and asks you to prove them with Coq.

In Cryptography (and Mathematics)

I already mentioned the idea of proving protocols (cf EasyCrypt et al.), for cryptographic proofs, the idea is basically the same. Specify using logic properties.

Coq example (trivial to prove by hand for a undergrad student):
$$\forall\ f g, f \text{ is injective} \implies g \text{ is injective} \implies g \circ f \text{ is injective}$$

Require Import Coq.Sets.Image.

Theorem injective_trans:
forall A B C (f: A -> B) (g:B -> C) (h:A -> C),
(forall x, h x = g (f x)) -> injective A B f -> injective B C g -> injective A C h.
Proof.
intros A B C f g h H_h_equal_g_f H_f_injective H_g_injective.
unfold injective in *.
intros x y H_h_x_y.
apply H_f_injective.
apply H_g_injective.
rewrite <- H_h_equal_g_f.
rewrite <- H_h_equal_g_f.
apply H_h_x_y.
Qed.

Here is a list of famous proven theorem in Coq.

Final words

Security bounds in Keccak has been proven with the aid of a computer. But their process was different: they exhaustively generated the trails and showed the properties. Thus it was computer aided, but not verified.

And finally, a recent paper from FSE 2016: Verifiable side-channel security of cryptographic implementations: constant-time MEE-CBC

As SEJPM pointed out, this paper is also another kind of approach (more game based). They created an analyzer that generated a cipher scheme that satisfied the AE scheme. However, I don't know whether they have proven their properties by hand or used a proof assistant (which might be possible given that they used Ocaml to code their analyzer).

You might also be interested in the course Gilles Barthe (EasyCrypt team) has done here.

I do not know if my answer has been helpful. I know it is not mainly focused on cryptography, but I hope it will give you a some idea of how things work.


Verify ECDSA signature without data With RSA PKCS#1 v1.5 it is possible to verify that the signature was generated by the correct private key without actually having access to the data. You just perform the modular exponentiation with the public key to retrieve the padded hash. Then it is possible to verify that the message was padded correctly. Moreover, you retrieve the hash value which can be used to try and guess the input (Internet search, DB lookup, guessing using dictionaries, brute force etc.).

Is there something similar possible with ECDSA? Is it at least possible to verify that the signature was created with a particular private key? Personally I don't see it because the value of $r$ is just random, and I don't see any way to reverse $s = k^{-1} (z + rd_A) \bmod n$ without the hash as input. Is there a way to do that or is it possible to prove mathematically that it infeasible to do so?

It is not possible:

Let $d_A, d_B$ be distinct private keys. Then

$$
  s=k^{-1}(z+rd_A)=k^{-1}((z+r\;(d_A-d_B)) + rd_B)
$$

So the pair $(r, s)$ is not only a valid signature for the public key $d_AG$ and the (partial) hash $z$, but also for the public key $d_BG$ and the message hash $z+r\,(d_A-d_B) \pmod n$.

So in many cases (if there are no restrictions on valid values for $z$), every valid signature $(r, s)$ ("valid" for some public key) and every public key $d_AG$ there will be a message $M$ such that $(r, s)$ is a signature for $M$ under $d_AG$.


collision and pre-image difference I'm doing an online free course about cryptography and there's a very confusing question:

Can anyone explain the answer please?

Question for hashing algorithms:
Select one or more than one.

a. It is impossible to break its resistance to collision and preimage
b. It is more difficult to break its resistance to collision than to the preimage
c. It's just as easy to break your resistance to collision than to preimage
d. It is easier to break its resistance to collision than to preimage

I will omit the exact complexities as it is not directly asked, however let me know if you would like me to elaborate on them more.
There are three levels of security for a cryptographic hash function $H$:

Preimage resistance: it is infeasible for an attacker presented with $x$ to find $m$ so that $H(m) = x$.
Second-preimage resistance: it is infeasible for an attacker presented with $m_1$ to find $m_2\neq m_1$ so that $H(m_1) = H(m_2)$.
Collision resistance: it is infeasible for an attacker to find any $m_1$ and $m_2\neq m_1$ so that $H(m_1) = H(m_2)$.

Now to the alternative answers in your quiz:

a. It is impossible to break its resistance to collision and preimage

No, it can not be impossible in theory since an attacker with unlimited resources could brute-force over all possible inputs. The key here is the concept of computational infeasibility.

b. It is more difficult to break its resistance to collision than to the preimage
c. It's just as easy to break your resistance to collision than to preimage
d. It is easier to break its resistance to collision than to preimage

(d.) is the correct answer. Here's why:
For successfully 'breaking' preimage resistance, you get some output hash $x$ and need to find the corresponding input $m$ to that specific $x$. Unless there is a structural flaw in the hash algorithm, the quasi-randomising effect of the hash function dictates that the only way is to brute-force over a lot of different inputs until you find your target input $m$. This is extremely expensive, and intentionally so.
For collisions, you need to find any two distinct inputs $m_1,m_2$ that result in the same output hash. Now again you could choose a brute-force approach and try different inputs until you find a match. However you are not constrained by the fact that your inputs must result in a specific hash, like in both preimage cases. This makes it significantly easier to 'break' collision resistance.


How does a certificate authority issue a digital certificate? I am new to cryptography and I want to know the details of how a Certificate Authority issues a digital certificate.

From what I know (please correct me if I'm wrong at any parts of my explanation):

If Alice wants to request a digital certificate, Alice will send her public key to the Certificate Authority.

The Certificate Authority will then check whether the public key sent by Alice is legitimate, and will generate a digital certificate using the Certificate Authority's private key to sign Alice's public key.

Now, if Bob wants to communicate with Alice, Bob will get Alice's digital certificate to confirm Alice's identity. If Bob confirm the recipient is really Alice, he will then encrypt his message with Alice's digital signature public key and Alice will decrypt the message with her private key.

Three questions came into my mind:

Does Alice sends only her public key to request a certificate
from the Certificate Authority?
How does the Certificate Authority prove that the public key is
legitimate and belongs to Alice, since the Certificate Authority does
not know Alice as well?
What are the things that a Certificate Authority checks for before
issuing a digital certificate to a person?

Great question. I'll answer it in several parts.
Which Keys does Alice send?
There are two cryptographic operations that Alice may want to do: encryption/decryption, and signing/validation. You can either use the same keypair for both, or have two separate pairs of keys.
1 keypair method:
Here Alice would sign outgoing messages, and decrypt incoming messages with the same private key. Bob would validate the signature on her outgoing messages, and encrypt messages for her using the same public key.
2 keypair method:
Here Alice would have a (signing_private_key, validation_public_key) keypair, and a separate (decryption_private_key, encryption_public_key) keypair.
In both cases she only sends the public keys to the Certificate Authority (CA) to be made into certificates. The private keys are private, she never shares them, they never leave her machine, they never become certificates.
How does the Certificate Authority (CA) trust Alice?
There are several trust models that different organizations use. Many large companies / government departments operate their own CAs for internal email, file storage, etc. In these cases when someone is hired they are issued digital certificates along with their ID badge, parking permit, etc. We trust that Alice is who she claims to be because she's sitting right in front of the Security Officer issuing the ID.
For web certificates like SSL establishing trust is little more complicated. The CA/Browser Forum has guidelines for CAs on how to verify the identity of applicants. Here is a long list of guidelines. The common forms that most CAs offer are Domain Validated (DV) and Extended Validation (EV) SSL certificates.
Domain Validated (DV) certs
This basically asks you for an email address and a person's name along with the web domain that you want a cert for. It does a whois lookup on the domain to make sure that the name and email you provided matched the domain's registration information. Additionally they can send a confirmation to the email address to make sure that you control it. DV certs can be completely automated, and in fact, "On November 18, 2014, a group of companies and nonprofit organizations, including the Electronic Frontier Foundation, Mozilla, Cisco, and Akamai, announced "Let's Encrypt", a new nonprofit certificate authority that plans to provide free TLS certificates" (wikipedia).
Extended Validation (EV)
The CA/Browser Forum specifies criteria for issuing EV certs, these all require a human in the loop, and relate to how stringently the identity of the applicant organization is researched. Having a phone call between the CA and the applicant is a basic requirement. Often documents are signed, and a face-to-face meeting can even be required before the CA will issue an EV cert. The level of validation that was performed will be included in the certificate to increase its public trustworthiness, consequently issuing CAs charge more for higher quality EV certs.
Many issuers also offer variations on the SSL cert wich don't fall into either the DV or EV categories. For example GlobalSign also offers Organization Validation (OV) as an intermediate category. Entrust offers many different types of certs depending on the network structure and software systems being used by the applicant.


Difference between Pseudo Mersenne primes and Generalized Mersenne primes The field prime numbers $p$ proposed by the NIST standards are referred to as Generalized Mersenne prime numbers [1] and as Pseudo Mersenne prime numbers [2].

Is there a difference between Pseudo Mersenne and Generalized Mersenne prime numbers? A lot of papers I recently read do claim that the primes proposed by the NIST standards are Pseudo Mersenne primes. However, other papers define them as Generalized Mersenne primes. Since those two prime families have different properties, applied in an ECC system, I am confused.

Section 7.1. NIST Discussion

Comparing Elliptic Curve Cryptography and
RSA on 8-bit CPUs

In the context of the papers you reference, Generalized Mersenne prime numbers and Pseudo-Mersenne prime numbers are indeed two different things.

A Pseudo-Mersenne prime number has the form $2^{\alpha}-\gamma$ for a small integer $\gamma \gt 0$.

The term Generalized Mersenne prime number is defined by example in the referenced paper, and the examples given are the primes used for the NIST prime curves for elliptic curve cryptography. For instance, the P-256 prime can be expressed as $2^{256}–2^{224}+2^{192}+2^{96}–1$. Consequently, a Generalized Mersenne prime number could be defined as a sum $2^{c_n}+(\sum_{i=1}^{n-1}{{-1}^{b_i}2^{c_i}})-1$ for two integer sequences $(b_i)_{i=1}^n$ and $(c_i)_{i=1}^n$ such that $b_i\in \{0,1\}$ and $c_1 \gt 0$ and $c_{i-1} < c_i$ and $c_n \gt n$.

The two definitions, as given here, overlap for (proper) Mersenne numbers $2^{\alpha}-1$, but any Pseudo-Mersenne number might also be expressed as a Generalized Mersenne number. The reverse is not true, unless you apply a very liberal definition of "small" as in small integer $\gamma \gt 0$. Typically, though, the $c_i$ exponents in a Generalized Mersenne number would be chosen as multiples of the word bit size, and $\gamma \gt 0$ would be selected as small possible.


Modifying a [CRC32] checksum protected file I dont want to ask for help without showing how far I came by myself, so this is what I have so far:

The file of interest is an encrypted/obfuscated .bin script, which cotains information on certain weaponstats eg. damage or accuracy. It is part of an older computergame. The raw file containts only hexvalues, which I "converted" to their Characters using extended ASCII. The output wasnt satisfying at all, untill I found out, that it was obfuscated using single byte XOR. Since there are only 256 different possible ways I went manually through all of them and had success with Key 42. This is what the decrypted script looks like:

I made my own small Tool, which decrypts the file hex -> ascii -> xor decrypt and saves the changes with hex <- ascii <- xor encrypt. So right now I am able to manipulate some weaponstats and save the file into its previous format.

When I try to start the game with my manipulated file it appears a CRC checksum error and it wont start. I was aware about this and did some research already, the checksum used is definitely CRC32 and I found out, that you can force a files checksum to any value by appending 4 bytes, but it obviously wont work due to the file format:

The CRC32 checksum is now similar to the untouched file, but the game cant read it and doesnt start and this is where Im stuck.

So what to do now? In theory I should be able to make some changes with getting the same checksum using gaussian elimination, but I really need some help to point me into the right direction.
It would be enough to change 1 hex-value as a first try and see what to change next to get the same CRC checksum. From there I could think about changing stuff, which makes sense in terms of manipulating weapons. So what if I change the very first hex-value in the file "16" to "17", what do I have to change next to get the old checksum back? Is that the right attemp? I am quiet new to all this, but I dont want to give up yet.

This folder contains the original file (items.bin) .txt to show in browser, an at 2 values maniuplated one and the plain text script. Original checksum is '3DD1ECB7'

Thanks in advance.

One fundamental property of CRCs is that if you exclusive-or in the bit representation of the polynomial (which, for standard CRC-32, would be 0x0104C11DB7) anywhere in the message, you don't modify the CRC.

So, the obvious thing for you to try is to exclusive-or that value (and similar, for example, the bit-reversed version of above) and see if that modified version has the same CRC.

Once you have verified the CRC polynomial (and the order in which bits are processed), then it is fairly straight-forward to perform arbitrary changes.


Is it ok to send part of digital signature if we have bandwidth constraints? When creating digital signatures is it ok to send part of it when we have bandwidth constraints?

No, it is generally not OK to send only part of the signature, because then it can no longer be checked; that's unless we remove only very little of the signature; or unless the term signature is used for what really is a symmetric Message Authentication Code (in which case shortening only reduces the security, perhaps acceptably).

For any signature scheme, we can remove a few bits of the signature, say $k$, and define a verification scheme that accepts the signature if any of the possible $2^k$ original signatures matching the truncated signature is acceptable. The risk of forgery is increased by at most $2^k$ but might remain acceptable. The work to verify the signature is increased by at most $2^k$ (including not at all, if we count a deterministic secret-key MAC as a signature scheme, for it is just as easy to verify a truncated such MAC as it is to verify the original MAC).

When there's a single bit to trim from an RSA signature (as is often the case when a signature is enciphered using a different modulus having the same number of bits as the modulus used in the signature), there's a standard trick avoiding a doubling of the verifier's work: if the RSA signature is $S$, send $\widetilde S=\min(S,N-S)$, which saves 1 bits, and let the verifier compute $V={\widetilde S}^e\bmod N$; either $V$ or $N-V$ is the normal padded message representative, the right one being determinable by some characteristic of the padded message representative, like being even or having its few high bits clear.

When there are bandwidth constraints, more radical options are:

Giving up public verification and using a deterministic secret-key MAC, which is king in term of compactness.
Using a signature scheme allowing message recovery, such that (at least some of) the message is embedded in the signature, saving bandwidth. The standard such RSA schemes are defined by ISO/IEC 9796-2 free partial preview, which allows for example to convey any $b$-byte message as a cryptogram of $\min(256, b+22)$ bytes, when using 2048-bit RSA keys and SHA-1 (but beware that scheme 1, common in the Smart Card industry, could be vulnerable to attack in a chosen-message setup, and has no proven security reduction in other setups).
Using schemes designed for short signatures with appendix, such a BLS; unfortunately, this is relatively new, and no international standard has emerged, or even is in the work AFAIK.


Can I still use insecure curves/ciphers for time relevant encryption? Can Ciphers that are known to be insecure because their keysize is considered too small still be used in appliances that have a tight decryption timeframe?
In particular I am looking at ECC2K-130.
ecc-challenge.info states, that they need 2466 PlayStation 3's to carry out the required 2^60.9 iterations per year.
Let's assume I need to encrypt data only for one minute, after that time the data is useless.
Couldn't I still use ECC2K-130 as it would require 525600 times more PlayStations to crack it in a single minute instead of a year?
Or do I have a misunderstanding in the way this works?

Let's assume I need to encrypt data only for one minute, after that time the data is useless. Couldn't I still use ECC2K-130 as it would require 525600 times more PlayStations to crack it in a single minute instead of a year?

!!! NO !!!
Decryption by an unauthorized party could occur within a fraction of a second following the release of the ciphertext.
In ECC encryption (and more generally public-key encryption), the appropriate start time for the attack interval is

NOT the release of the ciphertext to adversaries
NOT the encryption time (even if there's a side channel¹)
is the release of the public key used for encryption to adversaries²
could be the generation of the public/private key, if there's a side channel¹.

At issue is that attackers can start working long before the encryption occurs or the data to encrypt even exists. They can start as soon as they get the public key (or, in 4, side channel data). That's when time of attack starts ticking. It is reset only by a key change.
In the question, the entity making the encryption uses the public key, thus is not the one who generated the keypair. The question suggests that the time considered is from encryption to when knowing the data becomes dull, which would be 2 in the above.

¹ In side-channel attacks, adversaries get information beyond the ciphertext in often unexpected ways, like timing of encryption, electromagnetic or acoustic emissions, leakage from a CPU process to another.
² In symmetric cryptography, that would be when the first ciphertext is obtained by adversaries.


ABE Schemes - Access Structures & Performance I'm reading this article, CP-ABE with constant-size keys for lightweight devices and in the Table 1, are there these access structure: Threshold, Tree, ($n$,$n$)-Threshold, LSSS, AND gates. I have 2 questions.

1) What are the differences between these access structures ?

2) How can i measure the performance of a scheme in a network ? (i.e scalability, number of users (producers and consumers) supported, number of contents supported) [If this question is off topic, i will remove it].

Let's assume that we're talking about monotonic access structures (without negated attributes in the policy).

A Threshold policy was introduced in Sahai, Amit, and Brent Waters. "Fuzzy identity-based encryption." Advances in Cryptology–EUROCRYPT 2005. Springer Berlin Heidelberg, 2005. 457-473. (link)

It means that a user secret key and the ciphertext are both associated with (possibly) different attribute sets. Decryption would only work if the overlap between the two sets is at least as large as the globally defined threshold (during setup). Here we don't distinguish between Key-policy ABE and Ciphertext-policy ABE.

An $(n,n)$-Threshold access structure is the same as AND gates. The later approaches usually use Shamir's Secret Sharing (SSS) with a variable threshold value $t$ as a $(t,n)$-scheme. If we require all shares to be present, then this essentially means that a single AND gates with $n$ attributes was used. Now, the authors chose to call it $(n,n)$-Threshold, because the attributes can be multi-valued (wildcards). This goes into the realm of Hidden Vector Encryption and non-monotonic access structures, even there it's still usually called AND gate.

The Tree approach was first described in Goyal, Vipul, et al. "Attribute-based encryption for fine-grained access control of encrypted data." Proceedings of the 13th ACM conference on Computer and communications security. Acm, 2006. (link)

It is a way of sharing a secret element across the attributes of a policy (KP-ABE or CP-ABE), which can then be reconstructed with Lagrange interpolation. See my answer here for more information. The construction of Goyal et al. permits not only AND and OR gates, but arbitrary threshold gates with SSS for every node of the tree. It is also fairly easy to build up the access tree from a textual representation such as a boolean formula.

Of course, there are other constructions that don't support arbitrary trees. For example Müller, Katzenbeisser and Eckert. "Distributed attribute-based encryption." Information Security and Cryptology–ICISC 2008. Springer Berlin Heidelberg, 2008. 20-36. (link) supports policies only written in a Disjunctive Normal Form (DNF).

A Linear Secret Sharing Scheme (LSSS) works on a matrix, where the rows are labelled with attributes of the policy, to produce shares from a secret element. This should be familiar as the outcome is the same as for the Tree access structure. In fact, when you implement a scheme, most of the time you can exchange an LSSS approach for a Tree approach, but that doesn't mean that it's secure anymore, because the security games and used assumptions may depend on a specific approach and may not work for the other.

If you're looking to convert a boolean formula to an LSSS matrix, then this is getting a little tricky, because it is not immediately apparent how this can be done. You can check with Lewko, Allison, and Brent Waters. "Decentralizing attribute-based encryption." Advances in Cryptology–EUROCRYPT 2011. Springer Berlin Heidelberg, 2011. 568-588. (link) to create an LSSS matrix from a boolean formulas, which use only AND and OR gates. Then Liu, Cao and Wong. "Efficient Generation of Linear Secret Sharing Scheme Matrices from Threshold Access Trees" (link) present a way to use general boolean formulas (with threshold gates).

This was only a small number of access structures. Other notable mentions are Monotone Span Programs (highly related to LSSS), Branching Programs and Circuits (used in Lattice-based ABE constructions).


Can there be two hash functions without common collisions? Is there a way to prove/create (or are there known hash functions) two hash functions that never have the same collision?   I mean, like provable in way that someone who took one cryptography class in university can prove.

For example, I want hash functions $A$ and $B$ such that if hash function $A$ collides on $X$ and $Y$, then $B$ will not collide on these $X$ and $Y$:

$$A(X) = A(Y) \quad \Rightarrow \quad B(X) \neq B(Y) $$

No, in general, there will always be a pair of inputs that will collide for both hash functions.  Specifically, if the hash functions have fixed sized outputs, and both take an arbitrary input which is at least as long as the sum of their outputs, then there will be bitstrings $X$ and $Y$ with $X \neq Y$, $A(X) = A(Y)$ and $B(X) = B(Y)$

Here is a simple demonstration that such a pair must exist: let us assume that $A$ generates an output which is $n$ bits long, while $B$ generates an output which is $m$ bits long, and further assume that $n, m > 0$.

Now, consider the set of all possible bitstrings of length $n+m$, along with the empty bitstring (or, if you don't like that, pick any bitstring shorter than $n+m$).  This set has size $2^{n+m}+1$.  If we apply the hash function $A$ to each member of the set, there are $2^n$ possible outputs, and hence (by the pigeon-hole principle), there must be some output with at least $2^m+1$ preimages.  Let us pick such an output, and call the subset when generates that output subset $W$.

Now, let us consider applying the hash function $B$ to each member of $W$; $W$ has size at least $2^m+1$, and $B$ has $2^m$ possible outputs; hence there must be two elements $X$ and $Y$ of $W$ with the output.

This pair $X$ and $Y$ is a common colliding pair for $A$ and $B$.


Is LibreSSL affected? - Downgrade Attack on TLS 1.3 https://news.ycombinator.com/item?id=19111707

https://www.nccgroup.trust/us/about-us/newsroom-and-events/blog/2019/february/downgrade-attack-on-tls-1.3-and-vulnerabilities-in-major-tls-libraries/

No one knows that LibreSSL is affected by CVE-2018-12404, CVE-2018-19608, CVE-2018-16868, CVE-2018-16869, and CVE-2018-16870 or not.

Does anybody has any info about it?


Frobenius Map on BN Curve sextic twist? I'm new to cryptography and I am working on R-ate Pairings on a BN Curve:

$y^2=x^3+b$ with $b$=5

with its M-type twist:

$y^2=x^3+b\beta$, and $\beta^2 = -2$.

The base finite field characteristic is P

Now, according to the paper, there is a Frobenius endomorphism

$\pi^p:(x,y)\longmapsto(x^p,y^p)$

So, for a given point:

$Q(x,y)$ on $y^2=x^3+5\beta$,

Its Frobenius map $Q`(x^p,y^p)$ should also have $(y^p)^2=(x^p)^3+5\beta$.

My calculation shows the results is $(y^p)^2=(x^p)^3-5\beta$

So where am I going wrong?

Thanks for your help.

Reference of the paper (in Chinese):

Translation of algorithm image:

$\pi_q$ as Frobenius endomorphism, $\pi_q: E \rightarrow E$, $\pi_q(x,y) = (x^q,y^q)$

$\pi_{q^2}: E \rightarrow E$, $\pi_{q^2}(x,y) = (x^{q^2},y^{q^2})$

R-ate pairing ("pair's calculation"):

Input: $P \in \mathbb{E(\mathbb{F_p}})[r], Q \in \mathbb{E'(\mathbb{F_{p^2}})}[r]$, $a = 6t+2$

Output: $R_a(Q,P)$

a) Let $a = \sum_{i=0}^{L-1}a_i 2^i, a_{L-1}=1$

b) Set $T=Q, f=1$

c) With $i$ from $L-2$ down until 0, execute:

c.1) calculate $f = f^2 \cdot g_{T,T}(P), T=[2]T$
c.2) if $a_i = 1$, compute $f = f\cdot g_{T,Q}(P), T = T+Q$

d) Compute $Q_1 = \pi_q(Q), Q_2=\pi_{q^2}(Q)$

e) compute $f = f\cdot g_{T,Q_1}(P), T = T+Q_1$

f) compute $f = f\cdot g_{T,-Q_2}(P), T = T-Q_2$

g) compute $f = f^{(q^{12}-1)/r}$;

h) output $f$.

Edit:

In step d) $Q_1$ is a point after applying the Frobenius map on $Q$.
Then in step e) there is $T=T+Q_1$
Confusion:
According my calculation above, $Q_1$ should not be on the same curve where $T$ is.
Is it correct to calculate $T=T+Q_1$?
Or is my calculation wrong?

In step d) $Q_1$ is a point after applying the Frobenius map on $Q$. Then in step e) there is $T=T+Q_1$. Confusion: According to my calculation above, $Q_1$ should not be on the same curve where $T$ is. Is it correct to calculate $T=T+Q_1$? Or is my calculation wrong?

It looks like CurveEnthusiast verified your calculation in comments, so this is strictly for your final question:

The Frobenius map $\pi$ is a mapping from $\mathbb{E}′(\mathbb{F}_q)$ to itself. $T$ is a point on this curve, and since $\pi:\mathbb{E}′(\mathbb{F}_q) \rightarrow \mathbb{E}′(\mathbb{F}_q)$, $Q_1$ is also on the curve and so the sum is defined.


Is there a CSPRNG capable of generating a large sequence of numbers from a single seed? In my CS course i am in dire need of a CSPRNG that can create N numbers starting from a single key.
Something like this:

CSPRNG(x):
Input 64 bit int;
Output Array of CSR 64 bit Ints;

Does something like this exists? Which ones?
Or is almost every CSPRNG like this?

A PRNG, by definition, outputs a sequence of arbitrary length from a finite state. So you can get as many chunks of 64 bits as you may want from any PRNG. Or, said otherwise: if you have something that gets stuck at some point, then it is not a PRNG.

Such a PRNG is said to be "cryptographically secure" (that's the "CS" in "CSPRNG") if the output bits are unpredictable; that is, given n successive output bits from the PRNG, it is computationally unfeasible to predict the next bit with probability substantially better than 0.5. If you use a 64-bit seed, then there are only 264 possible initial states for the PRNG, a large number, but not practically infinitely so. It is expensive but technologically possible to enumerate all possible 264 seed values, and get the corresponding PRNG output. In that case, it suffices to try all these seed values to pinpoint the one which produces the PRNG output observed so far; afterwards, the future output of the PRNG can be predicted with 100% accuracy, which means that the PRNG is not cryptographically secure.

If you want a really secure PRNG, then you need a larger seed space (typically 128 bits or more). Take care that a big seed is not sufficient to get a CSPRNG; it is merely a necessary condition, to prevent the exhaustive search attack described above.

For some examples of CSPRNG, see NIST SP 800-90A. That document actually separates the "PRNG" part (they call it "DRBG", the "D" meaning "deterministic") from the seeding, and enforce regular re-seeding. You can also get a CSPRNG from any good stream cipher (e.g. the ones from the eSTREAM portfolio) or by running a block cipher (with large blocks, 128 bits or more) in CTR mode.

There are a number of published PRNG (e.g. the Mersenne Twister) which are not meant for cryptography, and fail to be unpredictable by attackers. Such PRNG are good enough for non-adversarial situations (e.g. simulation of physics experiments) but not for anything related to security.


Can HKDF be instantiated with HMAC-SWIFFT? While reading through "Cryptographic Extraction and Key Derivation: The HKDF Scheme" by Hugo Krawczyk, I found the following text intriguing:

  In some cases, well-defined combinatorial assumptions from the hash functions will suffice while in others one has to resort to idealized modeling and “random oracle” abstractions.

I assume it implies that: HKDF can be secure in certain cases even when the hash function is not a "random oracle".

When I recall that "a PRF appears random if it's selected randomly from the family of functions with the same domain", I think this means when the HMAC key is selected appropriately, the output from HMAC function should satisfy the requirements and goals of HKDF.

Is my reasoning true / somewhat plausible / wrong? Can HKDF be securely instantiated with HMAC-SWIFFT and in what situation?

The reasoning is wrong: the whole point of the paper is to establish a definition for secure general-purpose KDFs.

In definition 7 of the paper, it is defined that a KDF is secure, if it can withstand distinguishing game from an adversary with capability to query the KDF oracle - that's what something linear like SWIFFT cannot provide.

As for the quoted text in OP, it just means the author is proving his ideas using as few and as straightforwardly useful assumptions as possible, it did not imply what I thought it implied in OP.


Max size for exponent and modulus in RSA and for y, p, q, g in DSS I'm writing a method in Java to read SSH public key in RFC 4253 format, which, in my case, can be either RSA, or DSS.

What I really need is to read exponent and modulus for RSA key and y, p, q, g values for DSS key, which, according to the standard are of type mpint (multiple precision integers).

So basically, what I'm doing, is reading an integer first (that becomes "length"), then reading as many bytes as this integer is, then converting this byte array to Java's BigInteger.

It works perfectly well for valid keys. But the problem appears if there's a malformed key where this first integer is some extremely big number (let's say Integer.MAX_VALUE). Then such an approach results in Requested array size exceeds VM limit exception or some other Java errors related to memory. What I want to do to solve this issue is pre-checking if the length-integer is in a valid range (smaller then some max value).

And here comes the question: what are the max values for exponent, modulus, y, p, q and g? Is there even any maximum for them?

For DSA/DSS the key sizes are restricted by FIPS 186-4, so nothing will ever exceed 4096-bit.

For RSA, anecdotally the largest size anyone supports is 16k-bit, so a Modulus value expressed in 2049 bytes (2048 plus one padding byte).


How to compute accumulated values in bilinear map accumulators How to compute $ g^{1/(e_1+s)}$, where $g$ is the generator of group $\mathbb G$, and $e_1$ and $s$ are keys? I know only $s$ and $g^{e_1}$, not $e_1$. $\mathbb G$ has prime order for some prime $p$ and $e_1$ and $s$ are some elements of $\mathbb{Z}_p$.

In your setting this is assumed to be hard. It is exactly the task of producing a forgery for message $s$ of the weakly secure Boneh-Boyen signature scheme (Sec. 3.1) under public key $g^{e_1}$ (note that the scheme is presented in the asymmetric setting but can equally be instantiated in the symmetric setting under the $q$-SDH assumption).

In other words, if you can do this, you can break the $1$-SDH problem.


CSPRNG made out of Block Cipher running in CTR Mode? From Definition of CSPRNG, it has two characteristics

It satisfies the next-bit test.
It withstands 'state compromise extensions' - part of all of the state being compromised does not allow for reconstruction of the prior stream of random numbers.

The Design of CSPRNG can be based on

Cryptographic Primitives
Number Theory Problems
Sepcial Designs like Yarrow, Fortuna etc

If CSPRNG is constructed out of AES/Twofish/Camellia in CTR Mode, does it satisfy 2nd characteristic? i.e Compromise of internal state will not lead to reconstruction of prior stream of random numbers?

If we consider state as Counter only, or Counter and IV only (excluding the key). Will it be a CSPRNG?

Will any CPA secure Block Cipher working in Counter mode made CSPRNG under the assumption that compromise of internal state only consists of compromise of Counter only or Counter and IV only (not the key).

If CSPRNG is constructed out of AES in CTR Mode, does it satisfy 2nd characteristic? i.e Compromise of internal state will not lead to reconstruction of prior stream of random numbers?

No, assuming you mean the CSPRNG is just AES in CTR, the state is simply the key and the IV, therefore compromise will allow trivial generation of both past and future outputs.

Exposure of just the key is also as bad, as you can decrypt the output using the key (in ECB mode) to recover the IV.


Random oracles and independence I'm reading an unpublished paper in which the author makes the following conclusions several times:

Assumptions: finite probability space, $H$ is a random oracle, $X$ and $Y$ are two (not necessarily independent) random variables, $X \neq Y$ for every possible outcome.

Conclusion: $H(X)$ and $H(Y)$ are independent and uniformly distributed random variables.

"Proof" (not actually stated as such): obvious, $P(H(x) = a|D) = P(H(x) = a)$ for every event $D$.

Is this a valid conclusion? Are there any counterexamples which don't explicitly involve events $D$ similar to $H(x) \neq a$?

If $H(X)$ and $H(Y)$ were not evaluated as a part of selecting $X$ and $Y$, then yes; the assumption of a random Oracle is that $H(Z)$ is an independent and uniformly distributed variable for every new (not previously submitted to the Oracle) value $Z$.

If this isn't the case, then this need not hold.  One obvious counterexample is:

$X := 1; Y := 2 \textit{ if H(1) < H(2)}\\ X := 2; Y :=1 \textit{ otherwise}$


Calculate new hash from old hash + appended string If I have a hash of some string in the form: hash(UNK + "known"),
Is there a way to calculate the hash of (UNK + "known" + "append"), given the hash of the original value?

Specifically I'm asking about the sha512 algorithm.

Basically, I'm asking if the algorithm works by hashing the old hash + new input, or if it only hashes the input by itself.

Thanks!

What you are looking for is called a length extension attack. A length extension attack is, when an attacker given and $h = H(m)$ is capable to compute $h' = H(m\|m')$ for some $m'$ without knowing $m$.

Hash functions constructed using the Merkle-Damgård construction are generally susceptible to length extension attacks and SHA512 is not an exception.

The reason is the structure of a Merkle-Damgård hash function, which operates by iterating a compression function $$f : \{0,1\}^{\ell'} \times \{0,1\}^\ell \to \{0,1\}^{\ell'}$$
that maps an $\ell'$ bit intermediate hash-value and an $\ell$ bit message block to a new $\ell'$ bit intermediate hash-value. (For SHA-512, $\ell=1024$ and $\ell'=512$).
Essentially it takes a message $m$ that must be a multiple of the block size $\ell$, splits it into blocks $m_1,\dots m_L$ (for a total message length of $|m|=L\cdot\ell$), sets $$h_0 := IV \in \{0,1\}^{\ell'}$$
and for $1\leq i\leq L$ computes $$h_i := f(h_{i-1},m_i).$$
Finally it outputs $h_L$.

From this description you can easily infer that given $h=h_L$ you can choose a new block $m'$ and compute $h_{i+1} = f(h,m') = H(m\|m')$ giving you a length extension attack.

However, as most things it's not quite that simple. I said above, that $| m|$ needs to be a multiple of the block size. This is in general not the case, so some padding needs to take place to bring the message length up to the next multiple of the block length. For SHA-512 the padding works like this:

Let $m$ be a message of length $|m|=b$ bits.
Then we append a single $1$ bit and $k$ $0$ bits, where $k$ is the smallest number, such that $b+1+k+128$ is a multiple of $1024$. Finally $b$ encoded as a $128$ bit integer is appended. This padded message is then fed into the construction outlined above.

What does this mean for a length extension attack? Mainly two things: First, in addition to $h_i$, we also need to know the length $|m|$ of the original message to compute the new padding. Second, we will not be able to freely choose $m'$.

If we run the length extension attack we will end up with a hash for the message $$m\|1\underbrace{0\dots0}_k\|b\|m',$$ which depending on context may or may not be sufficient for whatever an attacker is trying to do.


Differential privacy of "randomized responses" We define randomized responses as follows:

  In a question that can be responded with a "Yes" or "No", a respondent is asked to flip a fair coin, in secret, and answer the truth if it comes up tails. Otherwise he/she flips another coin in secret, and answers "Yes" if comes up tails, "No" otherwise.

According to the introduction this paper [1], the $\epsilon$-differential privacy of surveys relying on randomized responses is:
$$
\ln(0.75/(1-0.75)) = \ln(3)
$$
I am wondering how was this calculated. Note that the proofs contained in paper are related to the RAPPOR protocol.

[1]Úlfar Erlingsson, Vasyl Pihur, Aleksandra Korolova,"RAPPOR: Randomized Aggregatable Privacy-Preserving Ordinal Response"  https://research.google.com/pubs/archive/42852.pdf

I found the answer in this book  https://www.cis.upenn.edu/~aaroth/Papers/privacybook.pdf at page 30

  Fix a respondent. A case analysis shows that
  $$Pr[Response = Yes|Truth = Yes] = 3/4$$
  Specifically, when the truth is “Yes” the
  outcome will be “Yes” if the first coin comes up tails (probability
  1/2) or the first and second come up heads (probability 1/4),
  while $$Pr[Response = Yes|Truth = No] = 1/4$$ (first comes up heads and
  second comes up tails; probability 1/4). Applying similar reasoning to
  the case of a “No” answer, we obtain:
  $$
\frac{Pr[Response = Yes|Truth = Yes]}{Pr[Response = Yes|Truth = No]}=
\frac{3/4}{1/4}= \frac{Pr[Response = No|Truth = No]}{ Pr[Response = No|Truth = Yes]} = 3$$


What is this cryptosystem called? From a paper Outsourcing Large Matrix Inversion Computation to A Public Cloud (IEEE Transactions on Cloud Computing, Vol. 1, N°1, 2013; alternate source requiring registration; preprint), I got to know about an encryption-decryption system. As I know only the basics of cryptography, I can't just figure out which cryptosystem this is. The basic algorithm is:

Generate keyspace using some security parameter.
Randomly pick two keys.
Generate a random permutation.
Shuffle the matrix coefficients using the random permutation and key.
Decrypt the resulting matrix using the random permutation and key.

Review of the paper

The paper's goal is to offload to a server the computation of the inverse of a (non-singular) $n\times n$ matrix $X$ of (the floating-point approximation of) real numbers, while keeping $X$ and $X^{-1}$ confidential.

Towards that goal, the paper's method is to

draw a secret key consisting of two random permutations and $2n$ non-zero random real numbers (that key will be used for a single matrix $X$);
transform $X$ yielding $Y$ according to the key by performing rows and columns swaps and scalings:

swap rows according to one permutation;
swap columns according to the other;
multiply each raw by a secret random real non-zero value;
multiply each column by a secret random real non-zero value;

send the result $Y$ to the server
obtain the alleged $Y^{-1}$
transforms the alleged $Y^{-1}$ into the alleged $X^{-1}$ by performing rows and columns scalings and swaps:

multiply each raw by the secret random real non-zero value formerly used for the column of same index
multiply each column by the secret random real non-zero value formerly used for the row of same index
swap rows according to the inverse of the permutation formerly used for columns;
swap columns according to the inverse of the other permutation;

verify the result by recomputing some of the coefficients of $X\cdot X^{-1}$ and checking if that's $1$ for the diagonal and $0$ elsewhere.

The paper

rightly observes that for large enough $n$, the bulk of the work is offloaded to the server (the client has $\mathcal O(n^2)$ work, when the server has $\mathcal O(n^\rho)$ works for $2.373\le\rho\le3$ depending on the matrix inversion technique used by the server);
has a section on Security Guarantee that culminates in the imprecise

  the cloud cannot recover X from Y by trivial means.(..) the security analysis follows an informal approach. A meaningful and challenging future work lies in giving a rigorous proof of security.

claims in the abstract (too optimistically at the very least) that it

  fulfills the goals of correctness, security, robust cheating resistance, and high efficiency

wrongly ignores issues of numerical stability in the verification procedure (as well as underflow and overflow that could occur in the scaling process), and is thus incorrect as described (the cheating resistance test has false positives in any implementation with bounded bandwidth to the server);
is insecure from a cryptographic standpoint for $n>1$, in particular because:

the number of elements equal to zero (or of very small magnitude) in $X$ is the same as in $Y$;
for even $n$ and $X$ with no zero elements, the sign of the product of all entries in $X$ is the same as in $Y$;
at least for moderate $n$, given $Y$ and $2n-1$ out of $n^2$ elements of a random $X$, it is typically possible to determine the $n^2-2n+1$ unknown elements of $X$, and a key equivalent to the original one.

Source and name of the cryptographic algorithm

The algorithm used to transform the matrix belongs to symmetric homomorphic cryptography. It is named disguise by Mikhail J. Atallah, Konstantinos N. Pantazopoulos, John R. Rice, Eugene H. Spafford: Secure Outsourcing of Scientific Computations, Technical report of the Department of Computer Sciences of Purdue University (1999), where it appears in section 1.4.1, with the same notation as the 2013 article discussed (which sadly does not cite this apparent inspiration).

The 1999 paper correctly identifies the security shortcomings of disguises (section 4.1), when the 2013 paper sidesteps theses. The 1999 paper has a section (3.1.2) on matrix inversion using this disguise technique, but what the 2013 article describes is more focused and slightly simpler.

Update: an earlier reference is by Mikhail J. Atallah, Konstantinos N. Pantazopoulos, Eugene H. Spafford: Secure Outsourcing of Some Computations, Technical report of the Department of Computer Sciences of Purdue University (1996); but there the technique is not yet named.


How can I prove the result of a long computation with a short string? I have a simple program F (think of a cellular automaton) that, when executed in some input X, takes a while to complete and returns a short result (a hash function, for example). How do I produce a short string that proves the result F(X) = Y without requiring the verifier to run the entire computation?

I'm aware of zk-snarks, but I couldn't a simple, practical "get started" guide to them. Moreover, they might be overkill for this since I don't need any privacy.

There are several option - none of which is trivial to implement.

A bit of background first. Essentially, verifiable delegation of computation boils down to being able to prove relations between inputs and outputs, so that the verification time is way smaller than the computation time, for relations that can be computed in polynomial time. In contrast, the famous SNARGs are way more powerful, as they also allow to prove any NP statement, even those that are not known to be computable in polynomial time. So in a sense, delegating computation is "easier" than constructing SNARGs. However, two remarks are in order:

A very large effort has been devoted to the analysis and construction of SNARGs, even leading to some implementations (e.g. zcash). Therefore, it might be that the current best way of verifying delegated computation in practice goes through SNARGs
A sense in which SNARGs are harder than verifiable computation is with respect to the underlying assumptions: while we have strong indications that SNARGs require non-standard assumptions, we know how to base verifiable computation on standard assumptions. But if you are looking for a practical solution, you might well not care about the theoretical issues of the underlying assumptions.

For those reasons, even in SNARG is an overkill from a theoretical point of view, it is not necessarily the case if what you care about is practice, and you can easily find some implementations (there are more recent ones, such as the famous Pinocchio, or the even more recent Geppetto).

That being said, there are several natural approaches for delegation of computation. The first that comes to mind is this approach, which is the seminal paper on the topic of delegation, and that works for restricted classes of computation. This approach was refined several time, culminating with this beautiful paper that gives a very satisfying solution for delegating evaluation of boolean circuit, with reasonable efficiency. I believe they have implementations, I do not know how easy it is to find and reuse these implementations.

The second, that I only mention for the sake of completeness, is to use techniques for batch verification: the prover evaluate the same program $P$ on many inputs $x_1, \cdots, x_n$, in time $O(sn)$ ($s$ being the time needed to evaluate $P$ on a single input) and the verifier can check the correctness of all computations in time $O(s + n)$, instead of $O(sn)$.

Another natural approach (see also this paper, this paper, and papers that reference them on Google scholar) for delegation of computation essentially requires to ask the server to perform the computation in the encrypted domain, via fully homomorphic encryption. It is based on homomorphic MACs, which can be constructed from FHE. From my understanding, they are conceptually quite simple - you essentially have to execute the computation several time in the encrypted domain, and there is an easy check for the verifier. The main issue is the cost of using FHE - but if your circuit is small enough, using this recent FHE scheme (see also the follow up) which performs bootstrapping in less than 20ms, this might be quite feasible. For more restricted computations, one can also avoid using FHE.

I've not read it yet, but if you have access to the ACM digital library, there was a recent survey on the subject of verifiable computation, by one of the leading researchers in the area (Rosario Gennaro), called "Verifiable Outsourced Computation: A Survey".


About DH-EKE and ECDHE_PSK (PSK versus Pasword) I am currently having a look at J-PAKE , so learning about Authenticated Key Exchange :
Reading 2.2.2 E.K.E from this paper https://people.kth.se/~maguire/Erik_Ehrlund_Literature_Study_report_v1.2.pdf
I understand the use of the password to authenticate a DH handshake.

The question is :

Is TLS DH ciphersuite based on PSK authenticated in the same way as the DH exchange authenticated with password ?
Is entropy a matter for PSK considering weak password ?

Assuming you're actually asking wether there is a difference for TLS in between a (high-entropy) pre-shared key (PSK) and a (low-entropy) pre-shared password, the short answer is:

No.

The long answer, however is a bit more complicated.
By itself the TLS-PSK ciphersuites don't differentiate between different degrees of entropy. However there are a few TLS-SRP ciphersuites, using the secure remote password protocol - a password-authenticated key-exchange (PAKE) protocol. They actually have some nice properties which only get interesting if you can assume the PSKs to be low entropy.

  Does entropy matter for TLS-PSK?

Yes it does.
If you're using the TLS_PSK_... ciphersuites you actually use the PSK as a basis for your session key meaning that this key is susceptible to off-line brute-force attacks. However it looks like you want to use TLS_ECDHE_PSK_... ciphersuites, which are much harder to attack. You can't derive the session key without breaking the ECDH key-exchange and knowing the PSK. So there's no trivial passive attack to obtain the transmitted contents after the handshake was done. However active attacks are very well possible, as you can install yourself as a man-in-the-middle (standard attack on DH) and try to impersonate the other client by trying out the different possible values for the PSK. This is infeasible if the PSK is high-entropy but very well possible if the PSK has low entropy.


Relationship between generating elements given by cycles in Cayley graph The strong RSA assumption is that the following problem is hard to solve.

"Given a randomly chosen RSA modulus $n$ and a random $z \in \mathbb{Z}_n^*$, find $r>1$ and $y \in \mathbb{Z}_n^*$ such that $y^r=z$."

The RSA assumption can be written as "it is computationally difficult to find a non-trivial relation in the RSA group $(\mathbb{Z}/pq\mathbb{Z})^*$". So when considering Cayley graphs, the problem of finding relationship between generating elements can be viewed as finding cycles in the Cayley graph, since cycles give relationships between generating elements.

(As an example, suppose a Cayley graph is generated by the elements $s$ and $t$. When we trace along $sttstt$, suppose we have traced along a cycle of length 6. Then because it is a cycle, $st^2st^2=e$, which actually represents a relationship between the generating elements $s$ and $t$.)

When we consider a situation of finding $y$ such that $y^r=z$ as mentioned above, we don't know which cycle gives this particular relationship right?

Is there way to connect this with the length of the cycle, so that we have some kind of an idea which type of cycle gave the above relationship?

Also, another question came to my mind is, when finding $y$, we might be able to use an algebraic method by making use of a private key or some data relevant to the cryptosystem considered. But if we hope to try to give a solution to $y$ though the process of finding a cycle in the graph, it is going to be very difficult, right?

I mean it'll be difficult even for the sender and receiver of a message, because finding cycles take time, even when done using an algorithm, right?

Thanks a lot in advance.

By the Chinese remainder theorem, we have that:
$$(\mathbb{Z}/pq\mathbb{Z})^* \cong (\mathbb{Z}/p\mathbb{Z})^*\times (\mathbb{Z}/q\mathbb{Z})^* \cong (\mathbb{Z}/(p-1)\mathbb{Z})\times (\mathbb{Z}/(q-1)\mathbb{Z})$$
From this, we should be able to write:
$$(\mathbb{Z}/pq\mathbb{Z})^* \cong \langle g_q, g_p\mid [g_q, g_p] = e, g_q^{q-1} = e, g_p^{p-1} = e\rangle$$
Where $e$ is the identity element of the group, $[g_q, g_p]$ is the commutator, etc. Essentially, this is the free abelian group on two generators, subject to the relations on the order of the generators that come from the CRT representation.

We can then write all the quantities you talk about in terms of the generators $g_q, g_p$.
Say that $z = g_q^{z_q}g_p^{z_p}$, and $y = g_q^{y_q}g_p^{y_p}$.
Then your equation:
$$y^r = z\implies g_q^{ry_q}g_p^{ry_p} = g_q^{z_q}g_p^{z_p}\implies g_q^{ry_q - z_q}g_p^{ry_p - z_p} = e$$
Gives us the "cycle". In particular, if you view the Cayley graph as being on vertices of the form $g_q^{x}g_p^{y}$ (so we can sort of visualize it as being some subset of $\mathbb{Z}^2$), this reduces the problem of finding cycles to finding points $(y_q, y_p)$ such that $(ry_q \equiv z_q \bmod (q-1))$ and $(ry_p\equiv z_p\bmod (p-1))$.
You may want to enforce some non-triviality condition (such as $ry_q\neq z_q$ and $ry_p\neq z_p$), I'm not sure.
If you want to find the minimum/maximimum length cycle, you could then find the minimum/maximum non-trivial $(y_q, y_p)$ such that $ry_q \equiv z_q\bmod (q-1)$ and $ry_p\equiv z_p\bmod(p-1)$. Note that if you know the factorization of $N = pq$, you can compute $y_q \equiv r^{-1}z_q\bmod(q-1)$ and $y_p\equiv r^{-1}z_p\bmod(p-1)$ easily (assuming $r$ is invertible in both rings), and then find particular representatives $(y_p, y_q)$ with properties you want by searching through the cosets $r^{-1}z_q + (q-1)\mathbb{Z}$.

I believe we can read off the length of any cycle fairly easily.
In particular, a cycle is a path from $(0,0)$ in $\mathbb{Z}^2$ to $(k_q, k_p)$ such that $k_q\equiv ry_q-z_q\bmod (q-1)$ and $k_p\equiv ry_pz_p\bmod(p-1)$.
The length of the shortest path from $(0,0)$ to $(k_q, k_p)$ is therefore $|k_q| + |k_p|$, which is the length of your cycle.
As $k_q\equiv 0\bmod(q-1)$ (and similarly for $k_p$), we see that the length of any cycle must be of the form $|a_p|(p-1) + |a_q|(q-1)$ for non-zero integers $a_p, a_q$, which puts some restrictions on which possible lengths are achievable (this is related to the Frobenius coin problem). There are likely upper bounds on $a_p$ and $a_q$ which come from the group relations of the type $g_q^{q-1}$, but this requires defining a good notion of "trivial" cycle first.

As for the computability of this, it can be efficiently computed if you know the factorization of $N = pq$ (all of the discussion above does this), and (likely) can't without this. I don't know if there are any gains to rewriting RSA in this way (I don't see any immediately), and don't guarantee the computations above are correct, but they seem vaguely right to me at least.

One thing to worry about is compact representation of the edges. All of the above required knowing the factorization of $N$. If we remove this, then we can abstractly view the cayley graph will as a graph on $\phi(N)$ vertices, which as $p,q\approx 2^{n/2}$ will be $\phi(N)\approx 2^n$.
Vertices can be communicated by indexing into $[\phi(N)]$, and since the graph is 4-regular (I think, edges from each vertex being $\{g_p, g_p^{-1}, g_q, g_q^{-1}\})$ each particular edge can be efficiently described. But I don't know how you can efficiently transmit the entire graph, as there are $O(2^n)$ edges, meaning that treating it as an abstract graph means you cannot efficiently communicate it.

Of course there are efficient ways to "compress" the graph (this must implicitly be done in traditional RSA-based cryptosystems), but its unclear how much of that compression will generalize to other groups, which appears to be your intention.


Plaintext XOR'd with keylength-shifted plaintext While solving a (easy...) Project Euler cipher problem this week I repeatedly saw instructions for breaking ciphers after identifying the keylength as:

  'shift the ciphertext by that key length and XOR it with itself. This
  removes the key and leaves you with plaintext XORed with the plaintext
  shifted the length of the key'

So I can understand how this drops the key out the equation, but I don't see how plaintext XORd with plaintext shifted by keylength is any more tractable.  In the many references I saw about this, no one followed up with how to solve the plaintext^shiftedPlaintext piece.  It doesn't seem that different than plaintext^keyPhrase really.

What am I missing about why this makes the problem easier to solve? What approaches deal with this part of the problem?

Well, if we have plaintext^shiftedPlaintext, what we have is the values $P_i \oplus P_{i+k}$, where $k$ is the length of the shift.

What does this imply?  Well, if we consider the values $P_i \oplus P_{i+k}$, $P_{i+k} \oplus P_{i+2k}$, $P_{i+2k} \oplus P_{i+3k}$, ... we get a chain where, if we guess one of the values $P_{i+nk}$ for some $n$, we can immediately reconstruct all other plaintext bytes in the chain; thus giving us the correct value for every $k$th plaintext byte.

That can be exploited in several ways.  One approach is crib dragging; we guess that a common word (the canonical crib for English is "the") occurs at a specific location, and see what that implies for other places in the plaintext; if it makes sense, then it is likely correct (and we have a large amount of plaintext; that gives useful context for other cribs); if it doesn't make sense, we try our crib elsewhere.

In addition, if the plaintext includes spaces, then a useful fact of ASCII can be useful; alphabetical letters have bit 6 set, spaces have bit 6 clear (and while numbers and punctuation also have bit 6 clear, those are comparatively rare).  So, if we see that the value of $P_i \oplus P_{i+k}$ has bit 6 set, then a good guess is that either $P_i$ or $P_{i+k}$ is a space; that acts as a 1 character crib.


Can we use Pohlig-Hellman Exponentiation Cipher with a PRG to achieve an oblivious PRF The Commutative Cipher Setup

Alice and Bob agree on a 2048-bit safe-prime $p$, where $(p-1)/2$ is also a prime.
Both parties have an encryption exponent $e$ in the range $(1, p-1)$ with $gcd(e, p-1) = 1$. And a decryption exponent $d$ chosen such that $d * e ≡ 1\bmod (p-1)$. Alice has $(e_A, d_A)$ and Bob has $(e_B, d_B)$ as their private key pairs.

Note:
I've also discovered that @fgrieu has proposed two variants of Pohlig-Hellman adressing some of the problems of modular exponentiation. Please assume the the key generation is done according to their explanation in both. variant 1, variant 2
We expect, this commutative cipher setup should be secure enough to use.

The Protocol
Alice has a message $m$ and wants to perform an oblivious PRF with Bob for this message.
The steps are as follows:

Alice seeds a PRG with $m$ and generates a 2048 (or 2047) bit random output $r$
a. For the properties $r$ satisfies, please check the PH variant by @fgrieu

Alice calculates the following encrypted random sequence with modular exponentiation, $E_A(r) = r^{e_A} \bmod p$ and sends the result to Bob.

Bob calculates $E_B(E_A(r)) = (E_A(r))^{e_B}\bmod p = E_{A,B}(r)$ and sends the result $E_{A,B}(r)$ back to Alice

Finally Alice calculates $D_A(E_{A,B}(r))=(E_{A,B}(r))^{d_A}\bmod p = E_B(r)$.

This should be the same value, where Bob:

Seeds the same PRG with the message $m$ to get $r$ (The same sequence Alice got from her PRG)
And calculate $E_B(r) = r^{e_B}\bmod p$

I believe this protocol should be satisfying the requirements of an Oblivious PRF. I'm assuming, given a random input, we can use modular exponentiation as a PRF.  Using the commutative nature of modular exponentiation, I believe we can achieve an Oblivious PRF. However I'm not sure if that's true, and I don't know how to prove this.
Once Alice and Bob have achieved an Oblivious PRF, My final goal for this OPRF is to use it for a Private Set Intersection protocol. Based on the answer of @Mikero in the question: How can Alice enable Bob to look-up values in a private map
Do you see any vulnerabilities here whether it might leak the keys of either parties or the message of Alice? Do you see any problems with my assumptions and utilization of modular exponentiation, if there are any points potentially insecure and should be avoided or fixed?

I believe this protocol should be satisfying the requirements of an
  Oblivious PRF.

This protocol is (nearly) identical to what is proven secure as an OPRF in the OPAQUE paper (Appendix A). There the OPRF is described (up to some formal notation) as follows, I'll annotate your notation in parenthesis:

Parameters: A multiplicatively-written Group $\mathbb G$ of order $q$ where the discrete logarithm is hard. A hash function $H(\cdot,\cdot):\{0,1\}^*\times \mathbb G\to\{0,1\}^l$. A hash function $H'(\cdot):\{0,1\}^*\to\mathbb G$.
(You call $H'$ a "PRG" and use $\mathbb Z_p$, that is the group of integers modulo $p$ with multiplication, as $\mathbb G$. This means that if it says $a^b$ below it means $a^b\bmod p$ for this group. If you need guidance on instantiating any of these hash functions, have a look at my prepared answer for this)

Setup: The Server $\mathsf{S}$ picks $k\gets_R\mathbb Z_q$, that is the server randomly picks a non-negative integer smaller than $q$.

Execution:

$\mathsf U$ wants to learn $F_k(x)$ with $F:\mathbb Z_q\times \{0,1\}^*\to\mathbb \{0,1\}^l$ without learning $k$ nor having $\mathsf S$ learn $x$.

$\mathsf U\to\mathsf S: H'(x)^r$, that is $\mathsf U$ picks an $r\gets_R\mathbb Z_q$, stores it and sends $H'(x)^r$. (This is step 1 and 2 of your protocol.)
$\mathsf S\to\mathsf U: \left(H'(x)^r\right)^k$, that is $\mathsf S$ simply exponentiates the given input with its secret value and returns the result. (This is step 3 in your protocol)
$\operatorname{return}\ H\left(x,\left(\left(H'(x)^r\right)^k\right)^{1/r}\right)$ That is $\mathsf U$ simply "unblinds" the received value (which is the decryption in your commutative cipher) and returns the original input and the received value through another hash function. (The last hashing step has been missing)

Additional notes: In OPAQUE, $x$ is the password and one can see $H'(x)^k$ as the "salt" and $H(\text{pw},s)$ as a password-based key derivation function, which gets evaluated client-side to decrypt a server-stored long-term DH key-pair. Then this key-pair with an ephemeral keypair gets used in a standard DH-based key-exchange computation (in this case HMQV).


When confusion is applied during encryption? I know confusion is used in cryptography to make it more difficult to identify any
relationship between the ciphertext and the symmetric key. I want to know when the confusion is applied during encryption, for example:

Confusion applied on the symmetric key K1 to form the modified symmetric key K2, and then K2 is used in the encryption: enc(Plain_text,K2).
K1 is used in encryption: Cipher_text = enc(Plain_text,K1), and then a confusion function is applied on Cipher_text.

Is it one of these two methods, or something else? An example would be appreciated.

Neither of those really represent how confusion might get introduced into an encryption function. Confusion typically gets introduced during the computation of the ciphertext, not before or after.

As an example, we can look at AES. AES is a substitution-permutation network. This means the encryption is done by doing several rounds of substitutions and then permutations. In the case of AES, there are 10-14 rounds of substitutions and permutations.

The way confusion gets introduced into AES is through propagation of bits through the rounds. Imagine if you flip one bit in K. In the first round, this might only effect the one bit of input. Once it passes through the substitution step in the AES S-box, all of the output bits of that S-box will be different. These "changed" bits then get distributed to several other S-boxes in the next round through the permutation step. This continues for all the rounds.

So a single bit change in the key started by only changing one bit in the intermediate computation, but then "spread out" through the encryption process to effect many ciphertext bits.


Does PBKDF2 reveal any knowledge about the salt? DK = PBKDF2(PRF, Password, Salt, c, dkLen)

When PBKDF2 is used for key derivation (not password hashing), is it possible for an adversary who doesn't know Password to learn anything about Salt when given DK?

Edit

To clarify this question a bit, let's fix c and dkLen and simplify the function a bit:

DK = PBKDF2(PRF, Password, Salt)

This function has 3 inputs and 1 output. When given PRF, Password and Salt, we can calculate DK exactly.

My question is actually very simple:

When given PRF and DK, is it possible for an adversary to learn anything about Salt?

Here are some trivial examples that may help you understand the question better:

If we define function1(PRF, Password, Salt) = Password, then obviously the adversary won't learn anything about Salt because it's not being used.
If we define function2(PRF, Password, Salt) = Salt, then obviously the adversary will learn something (everything, in fact) about Salt.

The parameter name Salt may be confusing because we are not using it as a salt here. Instead, it's some information that we want to keep a secret. This may or may not be its original design goal. But I'd simply like to know whether it's safe to use PBKDF2 in this way.

No, the adversary won't learn anything about the salt, if the salt is a cryptographic random of sufficient length.

A PBKDF such as PBKDF2 is generally build up from keyed one-way-functions (PRF's) such as HMAC's. That means that you cannot retrieve any of the inputs given the output. It does mean that if the inputs when put together can be guessed or brute forced that the input can be verified to be correct.

A secret salt is commonly called a pepper which acts as a secret key. The security provided by the pepper is comparable to a secret key of the same length.

A pepper can be concatenated with a real salt to create a new salt input parameter. The real salt can be stored together with the output of PBKDF2 or the ciphertext to avoid that identical pepper & password combinations can be identified.


Determine if a public key point y is negative or positive, odd or even? Take an elliptic curve cryptography public key (x, y) and its additive inverse (x, -y). How do you identify which is the positive point and which is the negative point?

Examples:

Private key 1 -> (x, y)

x = 0x79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798L

y = 0x483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8L

-y = 0xb7c52588d95c3b9aa25b0403f1eef75702e84bb7597aabe663b82f6f04ef2777L

Private key 2 -> (x, y)

x = 0xc6047f9441ed7d6d3045406e95c07cd85c778e4b8cef3ca7abac09b95c709ee5L

y = 0x1ae168fea63dc339a3c58419466ceaeef7f632653266d0e1236431a950cfe52aL

-y = 0xe51e970159c23cc65c3a7be6b99315110809cd9acd992f1edc9bce55af301705L

Private key 3 -> (x, y)

x = 0xf9308a019258c31049344f85f89d5229b531c845836f99b08601f113bce036f9L

y = 0x388f7b0f632de8140fe337e62a37f3566500a99934c2231b6cb9fd7584b8e672L

-y = 0xc77084f09cd217ebf01cc819d5c80ca99aff5666cb3ddce4934602897b4715bdL

Also, how can you identify which public key is odd and which is even?

For example: private key 1 x,y is odd, private key 2 x,y is even (based with pub key).

Elements of finite fields don't really have a sign. But depending on context you can define a property that's different for $x$ and $-x$ (when $x$ is not $0$) and call that property sign.

Some possible choices:

A number is called a square (or Quadratic residue) if there is another number which produces it when squared. Since positive real numbers are squares, identifying square field elements with a positive sign is a natural choice.

The Legendre symbol is 0 for 0, +1 for squares and -1 for non-squares. The Legendre symbol of the product of two numbers is the product of the two Legendre symbols, which mirrors how signs behave under multiplication.

You can even define $i = \sqrt{-1}$ to get some kind of complex numbers. Imaginary values of the $y$ coordinate of an elliptic curve correspond to its twist.
You can use the least significant bit. Computing this is very cheap, you only need to look at that one bit. This approach is often used to store the "sign" of a compressed elliptic curve coordinate.
Values smaller than $p/2$ have one sign, values greater than $p/2$ the other. I believe Bitcoin uses this convention to define canonical signatures.

You can extend any of these definitions from the underlying field to the elliptic curve defined over that field by defining the sign of the point as the sign of its $y$ coordinate.


Salting Hash stored on RFID tag? In my application, I am trying to prevent counterfeit widgets from being used on our gadgets; think HP ink-cartridges. I will be doing such with UHF RFID tags embedded in the widgets.

Unfortunately, the environment in which the gadgets are used does not allow me to keep a database of every widget in existence. I am operating in a closed, non-connected environment. The gadgets will have a computer and RFID reader installed on them. And the widgets may be used across multiple gadgets and they are reusable for a certain, to be determined, number of cycles.

I'd like to use the unique Tag ID (TID) of each tag as the salt for a common passphrase. These will be used to generate a 32-bit hash which will then be used as the tag read/write enable field. I then want to use some other hash in the user memory as secondary assurance that the widget is indeed authentic. Possibly using some random number and/or the date/time. However, I'm not exactly sure how I'd do that across multiple gadgets without storing unencrypted, unhashed information on the tag.

I know my current plan is not fool-proof (and it won't be without a database), but I'd like to know if there's any other ways to make it stronger. The tags in question (Alien Higgs 3) do not have an onboard microcontroller or any other "smarts" with which to interpret data.

First use the TID as input for a KDF to generate one or more tag specific keys, using a static, symmetric master key stored in the initialization software and gadget.

Use one of these keys to obtain access. Use another for verification of the tag.

During initialization derive and set the access key (s). Then create a HMAC over a static value (or multiple static values) within or outside the memory of the tag, and store it within the tag.

During read out by the gadget use the keys to gain access and to verify the HMAC value over the static value(s).

This symmetric solution can of course be complicated by several patches with regards to key management (roll over to different keys and such, possibly storing multiple hash values).

That's for a symmetric solution. If you're brave you may consider an asymmetric solution. As you don't have enough room for e.g. RSA signatures you may want to go for a small size signature. The obvious advantage is that you don't need to distribute the private key to the gadgets. These kind of schemes do however require more cryptographic capabilities from your side.

Don't forget to store a version number or something similar in your tags so you have an upgrade path.


Coin flipping with limited communication between participants Alice and Bob want to play a coin flipping game. Alice wins if the coin flips head.

They choose to trust a independent third party that generates a random beacon (such as NIST). There is no communication only before the random beacon is generated. After it is generated, there may be communication.

Alice has a message known only to her.
The result is the first bit of hash(message, beacon).

Alice and Bob may not be able to communicate before the random
beacon is generated.
The result can't be changed when at least one person knows the
result.

With (2) we avoid the situation where Alice reads the random beacon then changes the message to yield a different result that favors her.

One solution may be having the message hash timestamped by another third party (not the one of the random beacon) to a time before the random beacon is generated. Alice then can't change the message retroactively. I see two problems with this solution:

Alice may generate several messages and timestamp them before the
random beacon is generated. Then, after the random beacon is
generated, she can choose the message that yield the result that
favors her.
How can we prove that the timestamp was generated before the
random beacon?

Is there a crypto solution to this problem? Is this a common and studied problem in cryptography, please can you point me to some literature that describes and solves this problem?

As fgrieu pointed out, Alice and Bob must have somehow come to some kind of agreement before the random beacon is generated.
Would either of these techniques work for you?

use the random beacon directly

They could agree ahead of time that "Alice wins if the first random bit sent by the NIST Randomness Beacon on 2015-11-02 at 11:59 is a 0, and Bob wins if that bit is a 1."

Randomness beacons allow a person to prove that the random number (or any hash value calculated from it) was generated after some particular time.

use Alice's message with trusted timestamping

There are ways of doing trusted timestamping to prove that Alice knew a message before some particular time.

They could agree ahead of time that "After Alice commits to a single message by including that message in the Bitcoin blockchain as part of a transaction sending a tiny amount of bitcoin from Alice to Bob sometime during the day of 2015-11-01, and then later the NIST Randomness Beacon on 2015-11-02 at 11:59 generates some random data, Alice wins if the first bit of hash(message, beacon) is a 0, and otherwise Bob wins."

(If the message is long, it would be better to store only the hash of that message in the blockchain as a commitment to that message).

There is no direct communication from Alice to Bob or from Bob to Alice before the beacon transmission,
although this particular system requires some two-way communication between Alice and the Bitcoin system before the beacon transmission.

  Alice may generate several messages and timestamp them before the
  random beacon is generated. Then, after the random beacon is
  generated, she can choose the message that yield the result that
  favors her.

With this system, after the beacon transmission, Bob can fairly easily inspect the Bitcoin blockchain for that day and see if Alice tried to cheat by sending small amounts of bitcoins to him over several transactions that day, each transaction with the hash of a different message.
(Bob could inspect that blockchain even before the beacon transmission, although you could argue that would count as a message from Alice to Bob before the beacon transmission).

  How can we prove that the timestamp was generated before the random
  beacon?

That is a hard problem, but that is the problem that Bitcoin was designed to solve.


What does the PFX file extension stand for PFX is commonly used as a synonym of PKCS#12 certificate stores. However, I've never seen an explanation why these stores are called PFX (on Microsoft platforms) in multiple articles, including those of Microsoft. I can think up some names for what is seemingly an acronym, but "protected file X.509" doesn't seem to work well.

Does anybody have any idea what it actually stands for?

EDIT: I did know, but I forgot.

On my Windows 7 machine the .pfx file-type is called:

  Personal Information Exchange

I'm not sure why this turned into .pfx, but guess that they wanted to avoid .pix, because it sounds like an image format.

The acronym can also be found in MSDN where it describes a set of functions in an API for creating PFX files.


Argon2 with SHA-256 instead of Blake2 Can SHA-256 be substituted for Blake2 in the Argon2 algorithm?

I am working my way through the C reference source code for Argon2 and hand-translating it to Go. I was just wondering why Blake2 was chosen instead a well-tested algorithm like SHA-256.

If you take a look at the Password Hashing Competiton, you can see, that most of the schemes use Blake2b, some of them uses SHA-512, none of them uses SHA-256.

Blake2b is optimized for 64-bit platforms and this property fits exactly the requirement of a password hashing scheme. SHA-512 would also be OK, but SHA-256 would be much slower in software and the due to the fact, that SHA-256 is used for Bitcoin mining, custom hardware for SHA-256 is very cheap – this is exactly, what we do not want for a password hashing scheme.

I do not recommand to substitute any part of Argon2. All cryptoanalysis refer to the original version. Argon2 is – unlike Catena (another scheme from the password hashing competition) – not a flexible framework, that has been designed to be used with variable algorithms.
Argon2 uses not only the Blake2b function, but also something like a reduced version of Blake2b, the compression function G. You could possibly replace Blake2b by SHA-256, but you can‘t replace easily the reduced version, because Blake2b uses fewer rounds than SHA-256.


Cryptanalysis of S-DES - Equations I am trying to derive equations for s and t in the cryptanalysis of a Simple DES algorithm, but I haven't been able to deduce it. I have attached an image of the portion that I'm referring to, and I would appreciate it if someone could explain as to how the equations q and r are derived and what would be the derivation for s and t.

The question is actually about Simplified DES (rather than Simple DES as stated), which is an extremely simplified mock-up of Single DES.

From reading the definition of S-DES in the reference used in the question, we get that:

  The S-boxes operate as follows. The first and fourth input bits are treated as a 2-bit number that specify a row of the S-box, and the second and third input bits specify a column of the Sbox. The entry in that row and column, in base 2, is the 2-bit output.

Now let $a b c d$ be the input bits, $q r$ the output bits, use big-endian convention, and reformat that table as:

abcd qr     abcd qr    abcd qr    abcd qr
0000 01     0010 00    0100 11    0110 10
0001 11     0011 10    0101 01    0111 00
1000 00     1010 10    1100 01    1110 11
1001 11     1011 01    1101 11    1111 10

In order to verify the equations $q=abcd\oplus ab\oplus ac\oplus b\oplus d$ and $r=abcd\oplus abd\oplus ab\oplus ac\oplus ad\oplus a\oplus c\oplus 1$, just compute what $q$ and $r$ they give for each of the $2^4$ combinations of input, and compare that to the reformatted table; this is left as an exercise to the reader.

There is no systematic practical method to derive the most compact equation for a sizable bit table, and in the case of DES S-boxes this has been the subject of intense research. One systematic method leading to the most compact representation of an arbitrary boolean function as OR-of-AND-terms is known as Karnaugh map, but here the equations are wanted as XOR-of-AND-terms, and I know no analogous method. With 4 entries, finding the shortest equation (by some metric) that match would be tractable by brute force with a computer.

Still, here is how one of the equation could have been derived by hand. First we rewrite the table with the arguments in Gray order

a | 0000000011111111
b | 0000111111110000
c | 0011110000111100
d | 0110011001100110
--|-----------------
q | 0110100101111010
r | 1100110001011110

By comparing the line for $d$ with the line for $q$, it is striking that a bit flip of $d$ cause a flip in $q$, except when $a=b=c=1$; in other words, $q'=q\oplus d\oplus abcd$ is independent of $d$. We have reduced the problem to finding an equation for $q'$, with table

a | 00001111
b | 00111100
c | 01100110
--|---------
q'| 00110110

and some trial and error is enough to find $q'=ab\oplus ac\oplus b$, from which $q=abcd\oplus ab\oplus ac\oplus b\oplus d$ follows.


How to find p,q in this problem? Suppose

\begin{align*}
  g^r &\equiv h \pmod N, \\
  h^s &\equiv g \pmod N,
\end{align*}

for known $g$, $h$, $r$, $s$, and $N$, but not $\phi(N)$.

Then $$g^{r\cdot s - 1} \equiv 1 \pmod N,$$ so I can calculate $r\cdot s - 1 = k\cdot\phi(N)$.

Is $g$'s order $(r\cdot s - 1)/k$?

I think g's real order to be divided $\phi(N)$.

But $k$ is so big that I do not know what to do anymore.
How can I factorize N?

Note. In this case, we also have $g^{(r\cdot s-1)/3} \equiv 1 \pmod N$.

Then $$g^{r\cdot s - 1} \equiv 1 \pmod N,$$ so I can calculate $r\cdot s - 1 = k\cdot\phi(N)$.

Actually, we have $r \cdot s - 1 = a / b \cdot \lambda(N)$, where $\lambda(N) = \text{lcm}(p-1, q-1)$, and $b$ is likely to be small if $g$ was chosen randomly (example what can happen if $g$ is not chosen randomly, consider $g=h=r=s=1$).

With that, here is a randomized procedure that will find the factorization of $n$ with decent probability if $b$ is not too large:

Compute $z \cdot 2^{\ell}= r \cdot s - 1$ with $z$ odd
Select a random value $u$ and compute $v = u^z \bmod n$; if $v = 1$ or $v = n-1$, this iteration fails to find the factors; try again with another value of $u$
For $\ell$ times,

Compute $w = v^2 \bmod n$.
If $w = 1$, then this iteration succeeds, the factors are $\gcd( v-1, n)$ and $\gcd(v + 1, n)$
If $w = n-1$, then this iteration fails, try again with another value of $u$
Set $v := w$

If we went through $\ell$ loops without hitting 1 or $n-1$, this iteration fails to find the factors, try again with another value of $u$.