[cryptography] Asynchronous forward secrecy encryption

[Marco Pozzato]

Hi all,

I'm looking for an asynchronous messaging protocol with support for forward
secrecy: I found some ideas, some abstract paper but nothing ready to be
used.

OTR seems the preeminent protocol, but does not have support for
asynchronous communication.
This post https://whispersystems.org/blog/asynchronous-security/ describes
an interesting variation on OTR: the basic idea is to precalculate 100
Diffie-Hellman and consume one at every new message.

On the opposite side, for OpenPGP lovers, I found an old extension
http://tools.ietf.org/html/draft-brown-pgp-pfs-01 which adopt the same
approach, using many short-lived keys, which frequently expire (eg: every
week) and are deleted.

They are both clever ideas to provide PFS, but what does it mean to the
average user? Let say that today I discover an attack run on 1st of August:

   - OTR variation: I do not know which messages were wiretapped. 100
   messages could spawn few hours or two months.
   - OpenPGP: I know I lost messages sent in the first week of August.


What do you think about it?

Marco
___
cryptography mailing list
cryptography@randombit.net
http://lists.randombit.net/mailman/listinfo/cryptography

Re: [cryptography] Asynchronous forward secrecy encryption

[Adam Back]

Well aside from the PGP PFS draft that you found (which I am one of the
co-authors of) I also had before that in 1998 observed that any IBE system
can be used to make a non-interactively forware secret system.

http://www.cypherspace.org/adam/nifs/

There were prior IBE systems (with expensive setup and weak security margin
where you had to compute a 512-bit discrete log during to setup to gain
1024-bit security in the cse of Maurer & Yacobi's [1]), however that IBE ->
NIFS approach become efficient with Boneh & Franklins 2001 Weil pairing
based IBE.

However personally I consider that to still be a bit experimental on the
experimantal sid and prefer still more conventional approaches.

However in the mean time here's another approach for you (all new AFAIK :)
Use the paillier (1999) cryptosystem to compute discrete log mod n^2. 
(Knowledge of lambda(n^2) (the carmichael function of n^2) allows computing

the discrete log in paillier.) Create some relatively arbitrary set of
public keys y_i in an easily (publicly) computable sequence eg y_i=KDF(i). 
Use lambda to compute x_i st y_i = h^x_i mod n^2 with "generator" h.  Delete

lambda (and p,q, e, d etc).

Now encryption is (randomized) Elgamal using y_i, h and x_i during epoch i. 
Or for message i (if you stash a big load of public keys on an auxilliary
server for senders to take).  Should be pretty easy to implement. 


discrete log of y = h^x mod n^2 is computed with l = lamda:

define log(y,h) {
  return (modexp(y,l,n^2)-1)/n * modinv((modexp(h,l,n^2)-1)/n,n)%n;
}

(in bc syntax).  


or x = (y^l-1 mod n^2)|n / (h^l-1 mod n^2) mod n

where | is literally divided by (no modulus) and / is multiple my modular
inverse mod n.  n is an RSA modulus.

Adam

[1] Nov 1996 - U M Maurer and Y Yacobi - "A Non-interactive Public-Key
Distribution System", Designs, Codes and Cryptography vol 9 no. 3 pp 305-316

On Mon, Sep 16, 2013 at 01:45:43PM +0200, Marco Pozzato wrote:

  Hi all,
  I'm looking for an asynchronous messaging protocol with support for
  forward secrecy: I found some ideas, some abstract paper but nothing
  ready to be used.
  OTR seems the preeminent protocol, but does not have support for
  asynchronous communication.
  This post [1]https://whispersystems.org/blog/asynchronous-security/
  describes an interesting variation on OTR: the basic idea is to
  precalculate 100 Diffie-Hellman and consume one at every new message.
  On the opposite side, for OpenPGP lovers, I found an old
  extension [2]http://tools.ietf.org/html/draft-brown-pgp-pfs-01 which
  adopt the same approach, using many short-lived keys, which frequently
  expire (eg: every week) and are deleted.
  They are both clever ideas to provide PFS, but what does it mean to the
  average user? Let say that today I discover an attack run on 1st of
  August:
* OTR variation: I do not know which messages were wiretapped. 100
  messages could spawn few hours or two months.
* OpenPGP: I know I lost messages sent in the first week of August.

  What do you think about it?
  Marco

References

  1. https://whispersystems.org/blog/asynchronous-security/
  2. http://tools.ietf.org/html/draft-brown-pgp-pfs-01



___
cryptography mailing list
cryptography@randombit.net
http://lists.randombit.net/mailman/listinfo/cryptography


___
cryptography mailing list
cryptography@randombit.net
http://lists.randombit.net/mailman/listinfo/cryptography

Re: [cryptography] Asynchronous forward secrecy encryption

[Trevor Perrin]

On Mon, Sep 16, 2013 at 4:45 AM, Marco Pozzato  wrote:
> Hi all,
>
> I'm looking for an asynchronous messaging protocol with support for forward
> secrecy: I found some ideas, some abstract paper but nothing ready to be
> used.
>
> OTR seems the preeminent protocol, but does not have support for
> asynchronous communication.
> This post https://whispersystems.org/blog/asynchronous-security/ describes
> an interesting variation on OTR: the basic idea is to precalculate 100
> Diffie-Hellman and consume one at every new message.

Not at every new message.  Only for starting a conversation with a new partner.

Once a conversation is started, TextSecure uses OTR's "ratcheting"
algorithm for updating DH keys as messages are exchanged.

(
For a fuller picture of how this sort of key agreement could be done,
you should also read that post in conjunction with the previous post:

https://whispersystems.org/blog/simplifying-otr-deniability/
)


Trevor
___
cryptography mailing list
cryptography@randombit.net
http://lists.randombit.net/mailman/listinfo/cryptography

Re: [cryptography] [Bitcoin-development] REWARD offered for hash collisions for SHA1, SHA256, RIPEMD160 and others

[Lodewijk andré de la porte]

1) We advise mining the block in which you collect your bounty yourself;
   scriptSigs satisfying the above scriptPubKeys do not cryptographically
sign
   the transaction's outputs. If the bounty value is sufficiently large
   other miners may find it profitable to reorganize the chain to kill
   your block and collect the reward themselves. This is particularly
   profitable for larger, centralized, mining pools.

This is a *big *problem.


2013/9/15 Moritz 

> On 09/15/2013 03:12 AM, Peter Todd wrote:
> > It's amusing that the Bitcoin scripting language lets you pull off
> > stunts like this; annoying that the scripting language is too limited to
> > pull off much more than this.
>
> You have seen the "CoinWitness" proposal?
>
> https://bitcointalk.org/index.php?topic=277389.0
>
> --Mo
> ___
> cryptography mailing list
> cryptography@randombit.net
> http://lists.randombit.net/mailman/listinfo/cryptography
>
___
cryptography mailing list
cryptography@randombit.net
http://lists.randombit.net/mailman/listinfo/cryptography

[cryptography] Fatal flaw in Taiwanese smart card RNG

[John Kemp]

See:

http://arstechnica.com/security/2013/09/fatal-crypto-flaw-in-some-government-certified-smartcards-makes-forgery-a-snap/

for overview, and:

http://smartfacts.cr.yp.to/

for more details of the research.

Would it be advisable to implement a test, prior to any certification of an 
RNG, whereby some large number of keys are created and tested using a set of 3 
or 4 known algorithms (such as those used in this paper) for breaking keys?

Cheers,

- johnk___
cryptography mailing list
cryptography@randombit.net
http://lists.randombit.net/mailman/listinfo/cryptography

Re: [cryptography] Fatal flaw in Taiwanese smart card RNG

[Tim]

> no. you can't test a rng by looking at the output. only the
> algorithm and the actual code can be analyzed and reviewed. it is
> because it is extremely easy to create a crappy rng that fools the
> smartest analytical tool on the planet. it is not that easy to fool an
> attacker that reverse engineers your system.

I agree with you.  Any test of the output could be fooled while still
having a vulnerable generator.

However, I'm often in the position where I'm black box testing
software that uses PRNGs and I want to make a best effort to spot any
obvious mistakes, such as using a bad seed, weak generator, etc.
While in theory, there are a huge array of possible ways to make these
mistakes, in practice developers tend to make the same ones over and
over again, with slight variations.  Therefore there is utility in
having a simple way to check output for a discrete set of common
mistakes.  Generic statistical tests usually aren't helpful here.
Instead, tests targeted at well-known weak generators or seed methods
would be quite handy in my line of work.

tim


___
cryptography mailing list
cryptography@randombit.net
http://lists.randombit.net/mailman/listinfo/cryptography

Re: [cryptography] Fatal flaw in Taiwanese smart card RNG

[Seth David Schoen]

Krisztián Pintér writes:

> no. you can't test a rng by looking at the output. only the algorithm
> and the actual code can be analyzed and reviewed. it is because it
> is extremely easy to create a crappy rng that fools the smartest
> analytical tool on the planet. it is not that easy to fool an attacker
> that reverse engineers your system.

Well, there's a distinction between RNGs that have been maliciously
designed and RNGs that are just extremely poor (or just are
inadequately seeded but their designers or users don't realize this).

It sounds like such extremely poor RNGs are getting used in the wild
quite a bit, and these problems might well be detected by more
systematic and widespread use of these researchers' techniques.  It's
true that a maliciously designed RNG would not be detected this way.
The researchers do emphasize that

  An absence of common divisors is also not an indication of security.
  There are many potential vulnerabilities resulting from bad randomness;
  it is important to thoroughly test every component of a random-number
  generator, not merely to look for certain types of extreme failures.

-- 
Seth David Schoen   |  No haiku patents
 http://www.loyalty.org/~schoen/|  means I've no incentive to
  FD9A6AA28193A9F03D4BF4ADC11B36DC9C7DD150  |-- Don Marti
___
cryptography mailing list
cryptography@randombit.net
http://lists.randombit.net/mailman/listinfo/cryptography

Re: [cryptography] Fatal flaw in Taiwanese smart card RNG

[Krisztián Pintér]

no. you can't test a rng by looking at the output. only the algorithm and the 
actual code can be analyzed and reviewed. it is because it is extremely easy to 
create a crappy rng that fools the smartest analytical tool on the planet. it 
is not that easy to fool an attacker that reverse engineers your system.

> Would it be advisable to implement a test, prior to any
> certification of an RNG, whereby some large number of keys are
> created 

___
cryptography mailing list
cryptography@randombit.net
http://lists.randombit.net/mailman/listinfo/cryptography

Re: [cryptography] [Bitcoin-development] REWARD offered for hash collisions for SHA1, SHA256, RIPEMD160 and others

[Adam Back]

Mining power policy abuse (deciding which transactions prevail based on
compute power advantage for theft reasons, or political reasons, or taint
reasons) is what committed coins protect against:

https://bitcointalk.org/index.php?topic=206303.0

(Its just a proposal, its not implemented).

Adam

On Mon, Sep 16, 2013 at 05:21:42PM +0200, Lodewijk andré de la porte wrote:


1) We advise mining the block in which you collect your bounty yourself;
   scriptSigs satisfying the above scriptPubKeys do not cryptographically sign
   the transaction's outputs. If the bounty value is sufficiently large
   other miners may find it profitable to reorganize the chain to kill your
   block and collect the reward themselves.  This is particularly
   profitable for larger, centralized, mining pools.


This is a big problem.

___
cryptography mailing list
cryptography@randombit.net
http://lists.randombit.net/mailman/listinfo/cryptography

[cryptography] It's time for a Whistleblowing / Leaking Initiative for Cryptographer ?

[Fabio Pietrosanti (naif)]

http://threatpost.com/uk-cryptographers-call-for-outing-of-deliberately-weakened-protocols-products/102301

-- 
Fabio Pietrosanti (naif)
HERMES - Center for Transparency and Digital Human Rights
http://logioshermes.org - http://globaleaks.org - http://tor2web.org

___
cryptography mailing list
cryptography@randombit.net
http://lists.randombit.net/mailman/listinfo/cryptography

Re: [cryptography] Asynchronous forward secrecy encryption

[Patrick Baxter]

Has anyone here looked at Pond?
https://pond.imperialviolet.org/

Its by Adam Langley and while still very new and maybe in need of more
review, it seems quite promising.

On Mon, Sep 16, 2013 at 4:45 AM, Marco Pozzato  wrote:
> Hi all,
>
> I'm looking for an asynchronous messaging protocol with support for forward
> secrecy: I found some ideas, some abstract paper but nothing ready to be
> used.
>
> OTR seems the preeminent protocol, but does not have support for
> asynchronous communication.
> This post https://whispersystems.org/blog/asynchronous-security/ describes
> an interesting variation on OTR: the basic idea is to precalculate 100
> Diffie-Hellman and consume one at every new message.
>
> On the opposite side, for OpenPGP lovers, I found an old extension
> http://tools.ietf.org/html/draft-brown-pgp-pfs-01 which adopt the same
> approach, using many short-lived keys, which frequently expire (eg: every
> week) and are deleted.
>
> They are both clever ideas to provide PFS, but what does it mean to the
> average user? Let say that today I discover an attack run on 1st of August:
>
> OTR variation: I do not know which messages were wiretapped. 100 messages
> could spawn few hours or two months.
> OpenPGP: I know I lost messages sent in the first week of August.
>
>
> What do you think about it?
>
> Marco
>
>
>
> ___
> cryptography mailing list
> cryptography@randombit.net
> http://lists.randombit.net/mailman/listinfo/cryptography
>
___
cryptography mailing list
cryptography@randombit.net
http://lists.randombit.net/mailman/listinfo/cryptography

Re: [cryptography] Asynchronous forward secrecy encryption

[Tony Arcieri]

On Mon, Sep 16, 2013 at 4:45 AM, Marco Pozzato  wrote:

> I'm looking for an asynchronous messaging protocol with support for
> forward secrecy
>

There's also Nitro, which is a CurveCP derivative:

http://gonitro.io/

Unfortunately they didn't implement the full CurveCP handshake, which
provides both passive and active forward secrecy. It's unfortunate :(

-- 
Tony Arcieri
___
cryptography mailing list
cryptography@randombit.net
http://lists.randombit.net/mailman/listinfo/cryptography

Re: [cryptography] It's time for a Whistleblowing / Leaking Initiative for Cryptographer ?

[Jeffrey Walton]

On Mon, Sep 16, 2013 at 5:17 PM, Fabio Pietrosanti (naif)
 wrote:
> http://threatpost.com/uk-cryptographers-call-for-outing-of-deliberately-weakened-protocols-products/102301
>
Right now, whistle blowers are vilified in the US. Just ask Jesselyn
Radack, Thomas Drake, William Binney, Bradley Manning, et al. The
irony is the US recognized the usefulness of whistle blowing hundreds
of years ago during colonial times:
https://en.wikipedia.org/wiki/Qui_tam. (Thanks CB).

I'm all for monetization of whistle blowing to encourage the behavior.
But that would take a proverbial 'paradigm shift', because the sneaky
assholes who need to be uncovered are the same assholes who hold the
power and control popular thinking.

From the article:

> ... that calls on authorities in that country and the United States to
> conduct an investigation to determine which security products,
> protocols and standards have been deliberately weakened by the
> countries’ intelligence services.

I think MQV and Dual_EC_DRBG events are kind of rare, and I'm not sure
about this.

Does an intelligence agency need to backdoor code when: (1)
architectural and design defects are incumbent; and (2) shitty code is
regularly checked-in? I think the agency's best course of action is to
do nothing and wait for the defects to become widely available through
normal channels.

Given the above, an agency probably benefitted by doing nothing with,
for example, MQV and Dual_EC_DRBG. In this case, would the panel of
scientists be asking to investigate lack of agency action? I think
that's going to be pretty tenuous.

Jeff
___
cryptography mailing list
cryptography@randombit.net
http://lists.randombit.net/mailman/listinfo/cryptography

Re: [cryptography] Asynchronous forward secrecy encryption

[Fabio Pietrosanti (naif)]

Il 9/17/13 12:10 AM, Tony Arcieri ha scritto:
> On Mon, Sep 16, 2013 at 4:45 AM, Marco Pozzato  > wrote:
>
> I'm looking for an asynchronous messaging protocol with support
> for forward secrecy
>
>
> There's also Nitro, which is a CurveCP derivative: 
>
> http://gonitro.io/
>
> Unfortunately they didn't implement the full CurveCP handshake, which
> provides both passive and active forward secrecy. It's unfortunate :(

It's plenty of "custom solution and custom technologies" to achieve
those goals.

I am wondering why we don't just extend OpenPGP standard, by using
OpenPGP/Mime envelope, to include procedures to achieve Forward Secrecy?

Internet Standard are the bibble and saint text specification to look for.

Shouldn't we first try to improve Internet Standard, and only after look
for custom (and usually not interoperable) implementation?

-- 
Fabio Pietrosanti (naif)
HERMES - Center for Transparency and Digital Human Rights
http://logioshermes.org - http://globaleaks.org - http://tor2web.org

___
cryptography mailing list
cryptography@randombit.net
http://lists.randombit.net/mailman/listinfo/cryptography

Re: [cryptography] Asynchronous forward secrecy encryption

[Tony Arcieri]

On Mon, Sep 16, 2013 at 3:22 PM, Fabio Pietrosanti (naif) <
li...@infosecurity.ch> wrote:

>  Shouldn't we first try to improve Internet Standard, and only after look
> for custom (and usually not interoperable) implementation?
>

Well, if you want a forward secrecy for asynchronous communication using
existing Internet standards, perhaps you could use DTLS?

http://tools.ietf.org/html/draft-ietf-sip-dtls-srtp-framework-01#page-20

But FWIW, most of the design elements of Nitro come from CurveCP (albeit
implemented atop TCP):

http://curvecp.org/

Call CurveCP "custom" if you wish, but it's the sort of thing that *should*
be an Internet standard ;)

-- 
Tony Arcieri
___
cryptography mailing list
cryptography@randombit.net
http://lists.randombit.net/mailman/listinfo/cryptography

Re: [cryptography] Asynchronous forward secrecy encryption

[Trevor Perrin]

On Mon, Sep 16, 2013 at 3:36 PM, Tony Arcieri  wrote:
> On Mon, Sep 16, 2013 at 3:22 PM, Fabio Pietrosanti (naif)
>  wrote:
>>
>> Shouldn't we first try to improve Internet Standard, and only after look
>> for custom (and usually not interoperable) implementation?
>
>
> Well, if you want a forward secrecy for asynchronous communication using
> existing Internet standards, perhaps you could use DTLS?

I think Marco was talking about "messaging" cases where you don't want
the roundtrips of a TLS (or CurveCP) handshake.


> Call CurveCP "custom" if you wish, but it's the sort of thing that *should*
> be an Internet standard ;)

For another design with a lot of attention to forward secrecy and
immediate (zero-latency) sending, see QUIC [1]...

CurveCP spends 3 DHs, so it's computationally slower than MQV but more
complex than a Kudla & Paterson-style "triple DH" [2].  I also don't
think it's as amenable to "zero-latency" data transmission based on
pre-cached or pre-distributed ephemeral info as these other things.

CurveCP is also vunerable to impersonation of a client to a server if
either the client's ephemeral or server's key is compromised, which
are unusual properties for a key agreement protocol [3].


Trevor

[1] 
https://docs.google.com/a/chromium.org/document/d/1g5nIXAIkN_Y-7XJW5K45IblHd_L2f5LTaDUDwvZ5L6g/edit

[2]
https://whispersystems.org/blog/simplifying-otr-deniability/
http://www.isg.rhul.ac.uk/~kp/ModularProofs.pdf

[3] http://codesinchaos.wordpress.com/2012/09/09/curvecp-1/
___
cryptography mailing list
cryptography@randombit.net
http://lists.randombit.net/mailman/listinfo/cryptography

Re: [cryptography] Fatal flaw in Taiwanese smart card RNG

[Jeffrey Goldberg]

On 2013-09-16, at 11:56 AM, Seth David Schoen  wrote:

> Well, there's a distinction between RNGs that have been maliciously
> designed and RNGs that are just extremely poor

This has been something that I’ve been trying to learn more about in the past 
week or so. And if this message isn’t really appropriate for this list, please 
suggest alternatives.

Roughly, I’m trying to figure out how bad the (allegedly) RNGs that come with 
Apple or Microsoft Operating systems could be without that badness being 
discovered. I’m not talking about the spectacularly awful RNG apparently used 
for Taiwanese Citizen Digital Certificate cards.   Previously I’d only thought 
about this in terms of accidental badness; it’s hard to get these things right. 
But more recently, I’ve had to think in terms of malicious implementation.

Now when I say, “I’ve had to think about” it means little more than me just 
thinking about it. I don’t have the skills or training necessary to actually 
make much progress in my thinking.

My primary concern is with symmetric key generation.  For my application, I’m 
not looking at streams, and I’m only generating a small number of keys.  So 
really the question is if I grab 32 bytes from, say, Apple’s 
SecCopyRandomBytes(), how unsuitable is that to use directly as a key. I 
*think* an equivalent way of asking this question is do we have an estimate of 
how big of a Statistical Distance there could be between these RNGs and a 
uniform distribution without it being detected by public research?

I believe that I can compensate for a non-negligible SD from uniform by just 
getting for data than the target key length and using something like HKDF(). 
But is the same approach appropriate if I consider that the RNG may be 
maliciously bad, but still not bad enough to have been detected?

It seems that a one way to look for a large SD from uniform is to just fetch 
lots of data and look for collisions. (And without having to look for 
collisions of factors of public keys as we direct access to the output of the 
RNG.) But I”m not sure whether that is sufficient to demonstrate that I am safe 
using these RNGs as I do.

> It sounds like such extremely poor RNGs are getting used in the wild
> quite a bit, and these problems might well be detected by more
> systematic and widespread use of these researchers' techniques. It's

> true that a maliciously designed RNG would not be detected this way.

If we had access to the private keys, the factors, generated would checking for 
collisions be sufficient for identifying a maliciously designed RNG? I have no 
clear intuition on whether that would be sufficient, and I really need to not 
trust my intuitions anyway.

I’m interested in this both practically (so I can take appropriate defensive 
measures in app development) and also because I find this stuff fascinating. 
But I should acknowledge that my linear algebra sucks. I was able to fully 
understand everything in this research until talk a matrix as generator for a 
lattice.

smime.p7s
Description: S/MIME cryptographic signature
___
cryptography mailing list
cryptography@randombit.net
http://lists.randombit.net/mailman/listinfo/cryptography

Re: [cryptography] Fatal flaw in Taiwanese smart card RNG

[James A. Donald]

On 2013-09-17 02:56, Seth David Schoen wrote:


Well, there's a distinction between RNGs that have been maliciously
designed and RNGs that are just extremely poor (or just are
inadequately seeded but their designers or users don't realize this).

It sounds like such extremely poor RNGs are getting used in the wild
quite a bit, and these problems might well be detected by more
systematic and widespread use of these researchers' techniques.  It's
true that a maliciously designed RNG would not be detected this way.
The researchers do emphasize that


Typical design:   Bad randomness seeds a good pseudo random number 
generator - which unintentionally hides the fact that the randomness is 
weak.


Thus the difference between a malicious random number generator, and a 
random number generator where the seeding just is not working right, is 
seldom observable.



___
cryptography mailing list
cryptography@randombit.net
http://lists.randombit.net/mailman/listinfo/cryptography