Re: [cryptography] preventing protocol failings

[Peter Gutmann]

Nico Williams  writes:
>On Wed, Jul 6, 2011 at 12:06 AM, Peter Gutmann
> wrote:
>> (The ASN.1 filter I mentioned earlier is a stripped-down version of dumpasn1.
>> Remember that dataset of 400K broken certs that NISCC generated a few years
>> ago and that broke quite a number of ASN.1-using apps (and filesystems when
>> you untarred it :-)?  It processed all of those without any problems).
>
>Do you have a link for that dataset?  

You have to write to them and they'll send you a CD.  I'm not sure if it's 
available online anywhere.

>I want to check if the data is for explicitly or implicitly tagged modules.

It's randomly-modified cert data, there's every kind of tagging in there, 
including ones you've never heard of before (due to the random permutations 
used).

>See "ASN.1 Communication Between Heterogeneous Systems", page 213, which says 
>that "[a] type tagged in implicit mode can be decoded only if the receiving 
>application 'knows' the abstract syntax, that is, the decoded has been 
>generated from the same ASN.1 module as the encoded was".  

I know what implicit and explicit tagging is.  You don't need to know the 
syntax at all, a few simple heuristics will get BIT STRING and OCTET STRING 
holes and the like.  Throw stuff at dumpasn1 and see what it gives you.

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

Re: [cryptography] preventing protocol failings

[Nico Williams]

On Wed, Jul 6, 2011 at 12:06 AM, Peter Gutmann
 wrote:
> Nico Williams  writes:
>>In other words, in ASN.1 as it's used you have to know the schema and message
>>type in order to do a good job of parsing the message,
>
> No you don't.  I give as a counterexample dumpasn1, which knows nothing about
> message types or schemas, but parses any (valid) ASN.1 you throw at it.
>
> (The ASN.1 filter I mentioned earlier is a stripped-down version of dumpasn1.
> Remember that dataset of 400K broken certs that NISCC generated a few years
> ago and that broke quite a number of ASN.1-using apps (and filesystems when
> you untarred it :-)?  It processed all of those without any problems).

Do you have a link for that dataset?  I want to check if the data is
for explicitly or implicitly tagged modules.

Implicit tagging is supposed to replace the type's normal (say,
UNIVERSAL) tag with a CONTEXT tag.  This loses all information about
the type *except* whether it's constructed (as opposed to scalar).
Explicit tagging loses nothing -- it just adds a tag and length prefix
to the value that is already tagged with a UNIVERSAL tag.
Automatically tagged modules only add implicit tags when necessary to
disambiguate.  So whether you can recover enough information about the
types of scalar values (as well as whether constructed ones are
SEQUENCEs or SETs) depends on how the module is tagged.  And, of
course, a dumper can still distinguish individual scalar and
constructed values even when the module is implicitly tagged -- it
just can't tell the types of the scalar values (except, of course,
heuristically).  All of this applies only to BER and friends, but not
PER.

Now, the PKIX modules come in implicitly and explicitly tagged forms...

See "ASN.1 Communication Between Heterogeneous Systems", page 213,
which says that "[a] type tagged in implicit mode can be decoded only
if the receiving application 'knows' the abstract syntax, that is, the
decoded has been generated from the same ASN.1 module as the encoded
was".  See also X.680 (various places) and X.690 (for example,
appendix A).

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

Re: [cryptography] Bitcoin observation

[Alfonso De Gregorio]

On Tue, Jul 5, 2011 at 9:22 AM, Jon Callas  wrote:

Good points. But nonetheless, it's a really, really cool property of the
> system that you can gain by destroying bitcoins. I mean heck -- let's create
> another sub-constant, H_s which is the constant that shows when it better to
> destroy one than steal one. Obviously, if you have zero bitcoins, then
> stealing them has some value. But heck -- what if you're sitting on a cache
> of 371,000 coins. My intuition is that it's going to be better to destroy
> than steal. If you're found with a stolen bitcoin, you have some 'splaining
> to do. But if you silently destroy one -- then you see a market float.
>


Let's assume there is a way to convince market participants that some
Bitcoins has been destroyed, what would happen then? The value of the
current Bitcoin supply would slightly increase, that's correct.

Would market participants be willing to invest more in order to secure their
liquid assets against Bitcoin assassination attacks? How the attack rate
would increase/decrease?

The tragedy of the commons suggests us that when both risks and benefits are
socialized between the elements of the population, individuals lack the
incentive to unilaterally invest in security.

On the other hand, as long as the reduction of money supply increases the
value of the survived assets (ie, there's demand), some elements of the
population will have an incentive to attack.

It would be interesting to investigate further.

Alfonso

-- 
 tweets @secYOUre  blog. http://Plaintext.crypto.lo.gy/
___
cryptography mailing list
cryptography@randombit.net
http://lists.randombit.net/mailman/listinfo/cryptography

Re: [cryptography] preventing protocol failings

[Peter Gutmann]

Nico Williams  writes:

>In other words, in ASN.1 as it's used you have to know the schema and message 
>type in order to do a good job of parsing the message, 

No you don't.  I give as a counterexample dumpasn1, which knows nothing about 
message types or schemas, but parses any (valid) ASN.1 you throw at it.

(The ASN.1 filter I mentioned earlier is a stripped-down version of dumpasn1. 
Remember that dataset of 400K broken certs that NISCC generated a few years 
ago and that broke quite a number of ASN.1-using apps (and filesystems when 
you untarred it :-)?  It processed all of those without any problems).

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

Re: [cryptography] Bitcoin observation

[John Levine]

> Did you know that if a Bitcoin is destroyed, then the value of all
> the other Bitcoins goes up slightly? That's incredible. It's amazing
> and leads to some emergent properties

Let's imagine that there was an artist who we'll call Aldi. He made a
lot of signed prints, which are worth whatever they're worth, with
their value set by specialist businesses that will exchange his prints
for some amount of normal money.  (If I may introduce a little
technical jargon, these businesses are called "art dealers.")

Let's also imagine that Aldi signed 100,000 blank pieces of art paper,
which are sitting in warehouses and could be turned into signed prints
by printing a copy of one of his works on them.  The total supply of
Aldi prints is fixed (he's dead now), but the price of the prints is
held down by the knowledge that there's a whole lot of hoarded
potential prints whose owners could flood the market.  Now let's
imagine that someone takes a match and burns up one of those pieces of
signed paper.  What happens to the value of the rest of them?  Wow,
the value of all of the other Aldi prints goes up slightly. That's
incredible, not. 

Like any other commodity they're subject to hoarding, cornering the
market, and all of the other abuses that regulators like the CFTC
exist to prevent, for the commodities that anyone cares about.

The most amazing thing to me about bitcoins is that so many otherwise
sensible people are willing to believe that they are money, when they
so obviously are nothing like money.  They're pet rocks.

R's,
John
___
cryptography mailing list
cryptography@randombit.net
http://lists.randombit.net/mailman/listinfo/cryptography

Re: [cryptography] Bitcoin observation

[Taral]

On Tue, Jul 5, 2011 at 7:16 PM, Marsh Ray  wrote:
> So this suggests the attacker who pwned Mt. Gox was probably doing it "for
> the lulz" as they say. (Or maybe they didn't know about this property).
>
> Next time they might just take all the bitcoins held in escrow by the
> exchange and transfer them to /dev/null.

Sorry. It is not clear that the Mt Gox software would allow the
creation of such a transaction. I was speaking from the protocol
level.

-- 
Taral 
"Please let me know if there's any further trouble I can give you."
    -- Unknown
___
cryptography mailing list
cryptography@randombit.net
http://lists.randombit.net/mailman/listinfo/cryptography

Re: [cryptography] Bitcoin observation

[Marsh Ray]

On 07/05/2011 08:07 PM, Taral wrote:

On Tue, Jul 5, 2011 at 3:53 AM, Adam Back  wrote:

I dont think you can prove you have destroyed a bitcoin, neither your own
bitcoin, nor someone else's.  To destroy it you would have to prove you
deleted the coin private key, and you could always have an offline backup.


Actually, it's pretty easy to create a transaction whose outputs are
obviously unsatisfiable.


So this suggests the attacker who pwned Mt. Gox was probably doing it 
"for the lulz" as they say. (Or maybe they didn't know about this property).


Next time they might just take all the bitcoins held in escrow by the 
exchange and transfer them to /dev/null.


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

Re: [cryptography] Bitcoin observation

[Taral]

On Tue, Jul 5, 2011 at 3:53 AM, Adam Back  wrote:
> I dont think you can prove you have destroyed a bitcoin, neither your own
> bitcoin, nor someone else's.  To destroy it you would have to prove you
> deleted the coin private key, and you could always have an offline backup.

Actually, it's pretty easy to create a transaction whose outputs are
obviously unsatisfiable.

-- 
Taral 
"Please let me know if there's any further trouble I can give you."
    -- Unknown
___
cryptography mailing list
cryptography@randombit.net
http://lists.randombit.net/mailman/listinfo/cryptography

Re: [cryptography] preventing protocol failings

[Ian G]

On 5/07/11 3:59 PM, Jon Callas wrote:


There are plenty of people who agree with you that options are bad. I'm not one 
of them. Yeah, yeah, sure, it's always easy to make too many options. But just 
because you can have too many options that doesn't mean that zero is the right 
answer. That's just puritanism, the belief that if you just make a few absolute 
rules, everything will be alright forever. I'm smiling as I say this -- 
puritanism: just say no.


I find it ironic to be on the side of the puritans, but I think it's not 
inappropriate.


The 90s were the times of an excess of another religious crowd -- the 
hedonists.  In those times, more modes was more better.  The noble drive 
to secure the Internet intersected with the jihadic expression of code 
as freedom, the net as the new world, crypto as numbers, government as 
the enemy, and as much as possible of all of them.  Right now!  Today!


Hell, I was even part of it.  I thought it was so cool I coded up extra 
algorithms for Cryptix, just for fun, and lobbied to get extra 
identifiers stuffed into OpenPGP.




But what was the benefit?  Let's just take one example, the 
oft-forgotten client certificate.


Does anyone make much use of client certificate mode in SSL?  No, 
probably not.  They work [0], but nobody uses them, much.  And, it turns 
out that there is a good reason why nobody uses this fairly workable 
product:  because you don't have to.  Because it is optional.  As client 
certificates are optional, sites can't rely on the client certs being 
available.  So they fall back to that which they can insist on, which is 
passwords.  Which humans can be told to invent, and they will, without 
any audible grumbling.


So, options means unavailability.  Which means it can't be used.

Yet, there's no *security* reason for them being optional.  Client certs 
could be mandatory, just like server certs.  There is no *business 
benefit* for users in client certs being optional (and by this I mean 
client-side and server-side).




That's just one mode.  It turns out there is another mode -- HTTP.  This 
mode is turned on far more than it should be, resulting in a failure of 
user discrimination.  Hence, phishing.


Now, we may poo-poo the whole phishing thing, but consider that phishing 
is a bypass on SSL's authentication properties for online banking, etc. 
 At whatever layer we found it.  Phishing is the breach that exploits 
HTTP mode in browsing.


And consider that phishing, alongside server-breaching, financed the 
current wave of crime, step by step, to our current government 
cybercrime social disaster.


It's a lot to lay at the feet of a little mode like optional HTTP in 
secure browsing, but the bone points squarely at it.


If you've followed the history of real use and real breach, modes can be 
shown to cause failure.  OTOH, if we look at famous systems with few 
modes, we see less failure.  Skype has only one mode.  And it is secure. 
 SSH has very few modes.  And what modes it has -- password login for 
example -- caused a wave of SSH password snaffling until sysadms learned 
to turn off password mode!


In contrast:  SSL again.  Some packet bugs fixed in SSL v3.  MD5 
deprecation, much anticipated by a squillion cipher suites but target 
missed completely!  Re-negotiation - a mode to re-negotiate modes!  And 
finally the TLS/SNI bug.  Ug.




I claim that we've got causality and we've got correlation.  Which gives 
us the general hypothesis:


   there is only one mode, and it is secure.


I think that crypto people are scared of options because options are hard to 
get right, but one doesn't get away from options by not having them. The only 
thing that happens is that when one's system fails, someone builds a completely 
new one and writes papers about how stupid we were at thinking our system would 
not need an upgrade. Options are hard, but you only get paid to solve hard 
problems.



What's left is arguing about the exceptions.  In H6.6 [6], I argued that:

   "Knowing the Hypotheses is a given, that's the job of a
   protocol engineer. That which separates out engineering
   from art is knowing when to breach a hypothesis."

Another way of putting it is, do you think you know as much as Jon or 
Peter or the designers at Skype or Tatu Ylönen?  Probably not, but I for 
one am not going to criticise you if you've got the balls for trying, 
and you *know the risks*.




iang



[0] An alternate view on why & how client certs work:
http://wiki.cacert.org/Technology/KnowledgeBase/ClientCerts/theOldNewThing

[6]http://iang.org/ssl/h6_its_your_job_do_it.html#6.6
Hmm, perhaps that should be numbered H6.6.6 ?
___
cryptography mailing list
cryptography@randombit.net
http://lists.randombit.net/mailman/listinfo/cryptography

Re: [cryptography] Bitcoin observation

[Steven Bellovin]

On Jul 5, 2011, at 2:44 57AM, Jon Callas wrote:

> I was sitting around the other weekend with some friends and we were talking 
> about Bitcoin, and gossiping furiously about it. While we were doing so, an 
> interesting property came up.
> 
> Did you know that if a Bitcoin is destroyed, then the value of all the other 
> Bitcoins goes up slightly?

Mmm -- the curve isn't monotonic; once the distribution of bitcoins gets 
sufficiently small, you can buy less with it, because there are fewer 
acceptors.  This in turn hurts the purchasing power, which means that 
completely cornering the market is bad for the actor who does it.  This 
suggests that there's another critical parameter needed for your model.

--Steve Bellovin, https://www.cs.columbia.edu/~smb





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

Re: [cryptography] Minimally Sufficient Cryptosystem

[Alexander Klimov]

On Tue, 5 Jul 2011, Scott Guthery wrote:
> the following cryptosystem was minimally sufficient:
>
> XOR Key / Permutation / XOR Key

"A Construction of a Cipher From a Single Pseudorandom Permutation"


One can see it as a hint that building a keyless pseudorandom
permutation is not simpler than encryption.

-- 
Regards,
ASK
___
cryptography mailing list
cryptography@randombit.net
http://lists.randombit.net/mailman/listinfo/cryptography

Re: [cryptography] preventing protocol failings

[Arshad Noor]

On 07/05/2011 09:09 AM, Steven Bellovin wrote:


More importantly (and to pick a less extreme scenario), security isn't
an absolute, it's a matter of economics.  If the resource you're
protecting isn't worth much, why should you spend a lot?


And, one does not need to guess at how much "a lot" is; the legal
community uses a ruling from 1947, issued by Judge Learned Hand in
the case of United States vs. Carroll Towing Co., to determine how
much someone should have spent:

http://en.wikipedia.org/wiki/United_States_v._Carroll_Towing_Co.
or
http://en.wikipedia.org/wiki/Calculus_of_negligence

The only issue with our rather immature security industry is, that
without a central repository of information about attacks (that
might have provided quantitative data to researchers), its very hard
to calculate estimated damage.

Arshad Noor
StrongAuth, Inc.
___
cryptography mailing list
cryptography@randombit.net
http://lists.randombit.net/mailman/listinfo/cryptography

Re: [cryptography] preventing protocol failings

[Steven Bellovin]

> there may be a pragmatic need for options dealing with existing
> systems or business requirements, however i have yet to hear a
> convincing argument for why options are necessary in any new system
> where you're able to apply lessons learned from past mistakes.

You said it yourself: different businesses have different requirements.
The requirements may be operational environment or they may be
marketing-related.  I'll give just one example: web authentication.
If, say, I'm building a web-based interface to a system for tasking
an orbital COMSAT satellite.  That system should likely require
strong role-based authentication, possibly coupled with authentication
of the machine it's coming from, plus personal authentication for
later auditing.  By contrast, an airline reservation system that's
used for selecting seats (and printing boarding passes) will frequently
be used at hotel and airport kiosks, may be delegated to administrative
assistants, etc.  At some level, it's the same problem -- reserving
a resource (surveillance slot or an airplane seat), but the underlying
needs are very different.

More importantly (and to pick a less extreme scenario), security isn't
an absolute, it's a matter of economics.  If the resource you're
protecting isn't worth much, why should you spend a lot?  There are
certainly kinds of security that cost very little (RC4-128 has exactly
the same run-time overhead as RC4-40, though the cost of the public
key operations commensurate with those key lengths will differ);
other times, though, requirements are just plain different.

To quote the old Einstein line, a system should be as simple as possible
but no simpler.

--Steve Bellovin, https://www.cs.columbia.edu/~smb





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

Re: [cryptography] preventing protocol failings

[Nico Williams]

On Tue, Jul 5, 2011 at 7:59 AM, Peter Gutmann  wrote:
> Nico Williams  writes:
>>Why even have a tag??  The ASN.1 Packed Encoding Rules (think ONC XDR with 1-
>>byte alignment instead of 4-byte alignment) doesn't use tags at all.
>
> Which makes them impossible to statically check, and leads to hellishly
> complex decoders.

That was my first reaction to PER also.  But then I noticed the
similarities to XDR.  XDR encoding/decoding is not terribly complex,
and has had a compiler and runtime for decades.

OTOH, PER *is* hellishly complex *if* you're not using a compiler to
generate PER encoding/decoding code.  The problem quickly becomes how
to keep track in one's mind of the message layout.

>>In BER/DER/CER/XML you get a lot of redundancy: tag-length-value, sometimes
>>tag-length-tag-length-value (e.g., when explicit tagging is used).
>
> This is a feature, not a flaw, because it means you can statically type-check
> it.  With BER/DER I can implement a filter that takes as input any encoded
> blob and reports true or false for the question "is this well-formed data".
> With CER (and XML, and PGP, and SSH, and SSL/TLS, and IPsec) I can't.

Not exactly true because most ASN.1 modules use lots of implicit
tagging.  So instead of "tag for integer, length, integer value
octets" you get "context tag something or other, length, value" and
you have to know from context that the value is an integer instead of
something else.

In other words, in ASN.1 as it's used you have to know the schema and
message type in order to do a good job of parsing the message, and
this is true regardless of encoding rules (dunno about XER, that's
probably easier to parse w/o reference to the schema).

>>If you want to prevent new bugs in these areas, let's start with putting the
>>venerable BER/DER/CER to rest in the trash bin.  Legacy will make that a
>>difficult proposition.
>
> BER and DER are actually the safest encodings of the major security protocols
> I work with.  I'd rank them, in terms of danger, as:
>
> SSH
>
> [Long gap]
>
> PGP, SSL/TLS
>
> [Smaller gap]
>
> BER/DER

Given an ASN.1 compiler and BER/DER runtime I totally agree.  But
there's way too much hand-rolled ASN.1/BER/DER code out there, and
there's been plenty of bugs (interop and security both) in that code
(MIT krb5, I'm looking at you).

The real lesson isn't that encoding rules must not be redundant, but
that tools are required.

Another lesson is that avoiding ASN.1 in SSH and TLS didn't exactly
help: every protocol that avoids an off-the-shelf syntax and encoding
rules ends up creating its own syntax and encoding rules, thus leading
to more complexity for implementors who have to implement more than
one of these protocols.

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

Re: [cryptography] Minimally Sufficient Cryptosystem

[Tom Ritter]

> Perhaps anybody else that was there or is familiar with Shamir's work along
> this line might comment.

I was in Boston last Friday as well - Jean-Philippe is correct, the
second half of the talk was on the Even-Mansour system, and Adi talked
about his SLIDEX attack.  He may have expanded on it a little bit, I
think he had some more developments - but I don't recall exactly. I
got more out of the first half of the talk on GOST.

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

Re: [cryptography] Minimally Sufficient Cryptosystem

[Alfonso De Gregorio]

On Tue, Jul 5, 2011 at 3:21 PM, Jean-Philippe Aumasson <
jeanphilippe.aumas...@gmail.com> wrote:

> See the Asiacrypt 2010 rump session talk "An Optimal Attack On
> Cryptosystems With Pre/Post Whitening Keys" by Orr Dunkelman and Adi
> Shamir:
>
>
> http://www.spms.ntu.edu.sg/Asiacrypt2010/Rump%20Session-%207%20Dec%202010/AC2010_rump_Slidex_final.ppt



Of possible interest also is the Orr's presentation on related-key attacks:
http://www.cs.haifa.ac.il/~orrd/RK-Attacks.pdf

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

Re: [cryptography] Minimally Sufficient Cryptosystem

[Jean-Philippe Aumasson]

See the Asiacrypt 2010 rump session talk "An Optimal Attack On
Cryptosystems With Pre/Post Whitening Keys" by Orr Dunkelman and Adi
Shamir:

http://www.spms.ntu.edu.sg/Asiacrypt2010/Rump%20Session-%207%20Dec%202010/AC2010_rump_Slidex_final.ppt


On Tue, Jul 5, 2011 at 3:05 PM, Jonathan Katz  wrote:
> On Tue, 5 Jul 2011, Scott Guthery wrote:
>
>> Adi Shamir gave a talk at MIT last week at which I think he said that the
>> following cryptosystem was minimally sufficient:
>>
>> XOR Key / Permutation / XOR Key
>>
>> He seemed to me to imply that (informally speaking) any additional
>> complexity would be more likely to provide attack opportunities than not.
>>
>> Perhaps anybody else that was there or is familiar with Shamir's work
>> along this line might comment.
>
> Hard to say what he was talking about without some context, but it sounds
> like he might (?) have been referring to DES-X:
>  http://en.wikipedia.org/wiki/DES-X
> ___
> 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] Minimally Sufficient Cryptosystem

[Jonathan Katz]

On Tue, 5 Jul 2011, Scott Guthery wrote:

Adi Shamir gave a talk at MIT last week at which I think he said that the 
following cryptosystem was minimally sufficient:


XOR Key / Permutation / XOR Key

He seemed to me to imply that (informally speaking) any additional complexity 
would be more likely to provide attack opportunities than not.


Perhaps anybody else that was there or is familiar with Shamir's work along 
this line might comment.


Hard to say what he was talking about without some context, but it sounds 
like he might (?) have been referring to DES-X:

  http://en.wikipedia.org/wiki/DES-X
___
cryptography mailing list
cryptography@randombit.net
http://lists.randombit.net/mailman/listinfo/cryptography

Re: [cryptography] preventing protocol failings

[Peter Gutmann]

Nico Williams  writes:

>Why even have a tag??  The ASN.1 Packed Encoding Rules (think ONC XDR with 1-
>byte alignment instead of 4-byte alignment) doesn't use tags at all.

Which makes them impossible to statically check, and leads to hellishly
complex decoders.

>In BER/DER/CER/XML you get a lot of redundancy: tag-length-value, sometimes
>tag-length-tag-length-value (e.g., when explicit tagging is used). 

This is a feature, not a flaw, because it means you can statically type-check
it.  With BER/DER I can implement a filter that takes as input any encoded
blob and reports true or false for the question "is this well-formed data".
With CER (and XML, and PGP, and SSH, and SSL/TLS, and IPsec) I can't.

>If you want to prevent new bugs in these areas, let's start with putting the
>venerable BER/DER/CER to rest in the trash bin.  Legacy will make that a
>difficult proposition.

BER and DER are actually the safest encodings of the major security protocols
I work with.  I'd rank them, in terms of danger, as:

SSH

[Long gap]

PGP, SSL/TLS

[Smaller gap]

BER/DER

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

[cryptography] Minimally Sufficient Cryptosystem

[Scott Guthery]

Adi Shamir gave a talk at MIT last week at which I think he said that the 
following cryptosystem was minimally sufficient:


XOR Key / Permutation / XOR Key

He seemed to me to imply that (informally speaking) any additional 
complexity would be more likely to provide attack opportunities than not.


Perhaps anybody else that was there or is familiar with Shamir's work along 
this line might comment.


Cheers, Scott 


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

Re: [cryptography] Bitcoin observation

[dan]

Jon Callas writes:
-+
 | Did you know that if a Bitcoin is destroyed, then the value of all
 | the other Bitcoins goes up slightly? That's incredible. It's amazing
 | and leads to some emergent properties.
 | 

I suspect that this is true of gold as well -- send it into
space or bury it in dead people's bridgework and the economic
value of the remaining gold surely rises at least insofar as the
recovery of that lost gold, while possible, would require new
work to do so.

In any case, I just finished reading Glieck's _The Information_
and on page 361-362 of the hardcover edition, there is a passage
discussing how Von Neumann got it wrong when he concluded that
"every elementary act of information processing, every choice
between two alternatives" pays an energy price.  This claim was
refuted by Landauer who showed that "most logical operations
have no entropy cost at all.  When a bit flips from zero to one,
or vice versa, the information is preserved.  The process is
reversible.  Entropy is unchanged, no heat needs to be dissipated.
Only an irreversible operation increases entropy."

Landauer was followed by Bennett who "pursued Landauer's principle
by analyzing every kind of computer he could imagine, real and
abstract, from Turing machines and messenger RNA to 'ballistic'
computers, carrying signals via something like billiard balls.
He confirmed that a great deal of computation can be done with
no energy cost at all.  In every case, Bennett found, heat
dissipation occurs only when information is erased.  Erasure is
the irreversible operation.  When the head on a Turing machine
erases one square of the tape, or when an electronic computer
clears a capacitor, a bit is lost and _then_ heat must be
dissipated.  Forgetting takes work."

I may be mulling this over for some time.

--dan

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

Re: [cryptography] Bitcoin observation

[Adam Back]

Maybe one could introduce a way to destroy coins.  eg transfer it to
"/dev/null" by signing a transfer to an obviously non-existant
key-fingerprint like all s or such.  But I guess provable coin
destruction is not a mainstream "feature"!

Adam

On Tue, Jul 05, 2011 at 12:53:32PM +0200, Adam Back wrote:

I dont think you can prove you have destroyed a bitcoin, neither your own
bitcoin, nor someone else's.  To destroy it you would have to prove you
deleted the coin private key, and you could always have an offline backup.

You could uncreate a coin by creating a chain removing it from existance,
by having significantly more compute cycles than the rest of the network
combined.  Even that is dubious - not clear what would happen if the rest of
the network colluded and agreed you did that - could they get together and
reject your undo even though it was a more expensive chain?  Maybe... not
been tested yet.

Adam

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

Re: [cryptography] Bitcoin observation

[Adam Back]

I dont think you can prove you have destroyed a bitcoin, neither your own
bitcoin, nor someone else's.  To destroy it you would have to prove you
deleted the coin private key, and you could always have an offline backup.

You could uncreate a coin by creating a chain removing it from existance,
by having significantly more compute cycles than the rest of the network
combined.  Even that is dubious - not clear what would happen if the rest of
the network colluded and agreed you did that - could they get together and
reject your undo even though it was a more expensive chain?  Maybe... not
been tested yet.

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

Re: [cryptography] preventing protocol failings

[Peter Gutmann]

Jon Callas  writes:

>You're writing an S/MIME system. Do you include RC2/40 or not? Why?

You're missing the point of Grigg's Law.  For the purposes of the law, RC2/40
is secure.  The problem is that you're deploying it into an environment in
which the universal default mechanism isn't secure (SMTP and HTTP).  Because
insecure mode isn't so much a communications option but "the environment", the
defender can't make too much noise for the user if they sense SMTP/HTTP
instead of PGP/SMIME or HTTPS (you'd get endless false positives), and an
attacker can always defeat the security by rolling back to the insecure
default, i.e. running their phishing site over HTTP rather than trying to get
a fake cert for HTTPS.  As Griggs Law says:

  Good Protocols bootstrap into secure mode, immediately. On first time
  starting up, the protocol goes into secure mode.

At the moment the protocols start in insecure mode and almost always run in
insecure mode.   Secure mode (whether it's AES-256 or RC2/40) is a negotiable
option, the vast majority of users don't notice when it's not present, and
apps can't warn because it'd lead to endless false positives.

Peter.

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

Re: [cryptography] Bitcoin observation

[Ian G]

On 5/07/11 4:44 PM, Jon Callas wrote:

Did you know that if a Bitcoin is destroyed, then the value of all the other 
Bitcoins goes up slightly? That's incredible. It's amazing and leads to some 
emergent properties.


This assumes fixed value.  As there is no definition of the value in 
BitCoin, it's hard to sustain that assumption :)


In practice, there will be a number of effects.  If you potlatch your 
own coins, at the margin, others go up in value a little.  And you paid 
a lot for that, so you lose.


If you destroy others' coins, a little value goes up for all, sure.  But 
also currency being money, it loses its "store of value" characteristic, 
and rapidly loses value as people get out.  Demand goes down faster than 
supply, trading price plummets.



If you have a bunch of Bitcoins and you want to increase your worth, you can do 
this by one of three ways:

(1) Create more Bitcoins.
(2) Buy up more Bitcoins, with the end state of that strategy being that you've 
cornered the market.


If you buy all of them ... you also stopped the market :)


(3) Destroy other people's Bitcoins. The end state of that is also that you've 
cornered the market.


Except, reputation effects will cause a run, dumping, loss of value.


I also observe that if the player succeeds at either strategy (2) or (3), then 
Bitcoins are no longer a decentralized currency. They're a centralized 
currency. (And presumably, that player wins the Bitcoin Game.)


Um.  If a player succeeds in isolating all the money to self, it's no 
longer money :)



I'll go further and note that if a self-stable oligarchy manages to buy or 
destroy all the other  Bitcoins, they win as a group, too. With enough value in 
the Bitcoin universe, and properly motivated players, that could easily happen.

I wonder myself when it is more efficient to destroy a Bitcoin than buy or 
create one? Let's call the value of the energy to create one C. We'll call the 
value to buy one B. There must be some constant H where H*C or H*B makes it as 
efficient to destroy one than to buy or create. I suppose there's really two 
separate constants, H_c and H_b.

Nonetheless, I call this H because it's the Highlander Constant. You know -- 
there can only be one! If H is large enough, then you have unrestricted 
economic war that leads to a stable end where a single player or an oligarchy 
holds all the bitcoins.


Ah... there is only one BitCoin, and it is current!

At which point the film ends, and the script writers scratch their heads 
for the sequel :)



So if we consider a universe of N total coins and a total market value of V, 
and a players purse size of P coins, what's the value of H? I think it's an 
interesting question.

I have some other related things to muse over as well, like what it means to 
destroy a bitcoin. If you silently destroy one, the value of the remaining 
coins increases passively through deflation.


The value of the remaining coins might go up because of the "unit of 
exchange" characteristic being in demand, assuming that you don't 
actually hoard it otherwise.


Privately destroyed coins that were otherwise privately hoarded won't 
effect the value.  This is the Fort Knox radiation problem.  Is the gold 
in Fort Knox?  Is it radiated and unusable?  We don't know .. so what's 
it's value?  We don't know.  So it's value to us is zero.



But if you publicly destroy one, you could see an immediate uptick. ...


Yes, I guess an immediate public destruction is new info to the price, 
so the uptick will be expected.  As long as it is "at the margin" this 
will work.



Also, does public destruction actually hurt the market by making people tend to 
not want to put money into Bitcoins? Might this form some sort of negative 
feedback on the value of H, by cheapening Bitcoins as a whole? But is there a 
double-negative feedback through the fact that if people want to sell coins 
cheaply, the big players just buy them cheap and run the market back up that 
way?


It certainly confuses people's sense of what the value is.  Each trade 
(as opposed to a posted price) will reveal information about the value 
at that point.  These value points are ... valuable to the market, to 
excuse the pun.


However, other events are less informative.  Destruction, seizure, 
expiry, loss, theft all result in unclear information.




The end of all this musing, though, is that I believe that a decentralized 
coinage that has the property that destroying a coin has value *inevitably* 
leads to centralization through the Highlander Constant.


Yes, but centralisation is a self-limiting property, because a 
centralised currency isn't a currency.  It has to be current, which is 
to say, it has to be available to a large number of people in order to 
settle "current" debts.


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

Re: [cryptography] preventing protocol failings

[Jon Callas]

On Jul 4, 2011, at 11:35 PM, coderman wrote:

> On Mon, Jul 4, 2011 at 11:11 PM, Jon Callas  wrote:
>> ...
>> Yeah, sure. I agree completely.
> 
> no you don't ;)
> 

Actually I do. I also believe in truth and justice and beauty, too. And 
simplicity. I just value actionable, as well.


> 
>> How can I use this principle as a touchstone to let me know the right thing 
>> to do. I suppose we could consider it a rule of thumb instead, but that 
>> flies in the face of making it "Gospel."
> 
> what are the good reasons for options that don't include:
> - backwards compatibility
> - intentional crippling (export restrictions)
> - patents or other license restrictions
> - interoperability with others
> ?
> 
> there may be a pragmatic need for options dealing with existing
> systems or business requirements, however i have yet to hear a
> convincing argument for why options are necessary in any new system
> where you're able to apply lessons learned from past mistakes.
> 
> 

Pragmatic. That's what I'm talking about pragmatism. It's not pragmatic to go 
write a new protocol all the time. Especially if the time to create one with no 
known flaws is longer than the time to find a flaw.


>> You're writing an S/MIME system...
> 
> well there's your problem right there!
> 

Hey, you mentioned backwards compatibility, yourself.

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

Re: [cryptography] Bitcoin observation

[Jon Callas]

On Jul 5, 2011, at 12:07 AM, coderman wrote:

> On Mon, Jul 4, 2011 at 11:44 PM, Jon Callas  wrote:
>> ...
>> Did you know that if a Bitcoin is destroyed, then the value of all the other 
>> Bitcoins goes up slightly? That's incredible. It's amazing and leads to some 
>> emergent properties.
> 
> this is not completely correct. it is only true if you destroy a
> bitcoin in circulation. (for whatever interpretation of "in
> circulation" is reasonable.)
> 
> for example, there's one guy sitting on a cache of 371,000 bitcoins
> generated when the network was small and computation was minuscule.
> these were never in circulation, and for sake of argument, consider
> the physical media containing the keys for the coins is lost (not
> destroyed).
> 
> how does this affect the value of other coins?

Yeah, whatever.

> 
> 
>> If you have a bunch of Bitcoins and you want to increase your worth, you can 
>> do this by one of three ways:
>> 
>> (1) Create more Bitcoins.
>> (2) Buy up more Bitcoins, with the end state of that strategy being that 
>> you've cornered the market.
>> (3) Destroy other people's Bitcoins. The end state of that is also that 
>> you've cornered the market.
> 
> 0. steal other people's bitcoins. this is currently the most
> productive means for obtaining more bitcoin value, as proven over the
> last few months. 
> 
> 1. is only available while there are coins to be generated. at some
> point all coins will be mined and:
> 
> 4. collecting transaction fees for participating in the network is the
> last option in this list.

Good points. But nonetheless, it's a really, really cool property of the system 
that you can gain by destroying bitcoins. I mean heck -- let's create another 
sub-constant, H_s which is the constant that shows when it better to destroy 
one than steal one. Obviously, if you have zero bitcoins, then stealing them 
has some value. But heck -- what if you're sitting on a cache of 371,000 coins. 
My intuition is that it's going to be better to destroy than steal. If you're 
found with a stolen bitcoin, you have some 'splaining to do. But if you 
silently destroy one -- then you see a market float.


> 
> 
> regarding the remainder of your argument, the ability to divide
> bitcoins into arbitrarily smaller and smaller units implies that such
> an attacker will be chasing an asymptote; never able to reach
> definitive control while leaving a large network trading amongst
> themselves in millionths of a coin…

I think it only changes the value of H. It doesn't invalidate the argument. You 
can subdivide them in to 10^8 pieces, right?

If you think of "naive H" and "complete H", we know that Complete H is at most 
10^8 times the naive value.

> 
> the impacts of a large H are still interesting, even if never leading
> to one player takes all...

Very interesting. I stand by my hypothesis. I think it inevitably leads to 
centralization through coin assassination.

Jon

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

Re: [cryptography] Bitcoin observation

[coderman]

On Mon, Jul 4, 2011 at 11:44 PM, Jon Callas  wrote:
> ...
> Did you know that if a Bitcoin is destroyed, then the value of all the other 
> Bitcoins goes up slightly? That's incredible. It's amazing and leads to some 
> emergent properties.

this is not completely correct. it is only true if you destroy a
bitcoin in circulation. (for whatever interpretation of "in
circulation" is reasonable.)

for example, there's one guy sitting on a cache of 371,000 bitcoins
generated when the network was small and computation was minuscule.
these were never in circulation, and for sake of argument, consider
the physical media containing the keys for the coins is lost (not
destroyed).

how does this affect the value of other coins?


> If you have a bunch of Bitcoins and you want to increase your worth, you can 
> do this by one of three ways:
>
> (1) Create more Bitcoins.
> (2) Buy up more Bitcoins, with the end state of that strategy being that 
> you've cornered the market.
> (3) Destroy other people's Bitcoins. The end state of that is also that 
> you've cornered the market.

0. steal other people's bitcoins. this is currently the most
productive means for obtaining more bitcoin value, as proven over the
last few months. 

1. is only available while there are coins to be generated. at some
point all coins will be mined and:

4. collecting transaction fees for participating in the network is the
last option in this list.


regarding the remainder of your argument, the ability to divide
bitcoins into arbitrarily smaller and smaller units implies that such
an attacker will be chasing an asymptote; never able to reach
definitive control while leaving a large network trading amongst
themselves in millionths of a coin...

the impacts of a large H are still interesting, even if never leading
to one player takes all...
___
cryptography mailing list
cryptography@randombit.net
http://lists.randombit.net/mailman/listinfo/cryptography

Re: [cryptography] preventing protocol failings

[coderman]

On Mon, Jul 4, 2011 at 11:11 PM, Jon Callas  wrote:
> ...
> Yeah, sure. I agree completely.

no you don't ;)


> How can I use this principle as a touchstone to let me know the right thing 
> to do. I suppose we could consider it a rule of thumb instead, but that flies 
> in the face of making it "Gospel."

what are the good reasons for options that don't include:
- backwards compatibility
- intentional crippling (export restrictions)
- patents or other license restrictions
- interoperability with others
?

there may be a pragmatic need for options dealing with existing
systems or business requirements, however i have yet to hear a
convincing argument for why options are necessary in any new system
where you're able to apply lessons learned from past mistakes.


> You're writing an S/MIME system...

well there's your problem right there!


as for formal verification, i agree completely.
___
cryptography mailing list
cryptography@randombit.net
http://lists.randombit.net/mailman/listinfo/cryptography