[tahoe-dev] note about hash-based digital signatures
Zooko O'Whielacronx
zooko at zooko.com
Wed Jun 23 06:47:54 UTC 2010
Last login: Sun Jun 20 16:35:11 on ttys000
Zooko-Ofsimplegeos-MacBook-Pro:~$ mount
/dev/disk0s2 on / (hfs, local, journaled)
devfs on /dev (devfs, local, nobrowse)
map -hosts on /net (autofs, nosuid, automounted, nobrowse)
map auto_home on /home (autofs, automounted, nobrowse)
/dev/disk2s2 on /Volumes/Papers 1.9.4 (hfs, local, nodev, nosuid,
read-only, noowners, quarantine, mounted by zooko)
/dev/disk3s1 on /Volumes/Transcend (msdos, local, nodev, nosuid, noowners)
Zooko-Ofsimplegeos-MacBook-Pro:~$ cd /Volumes/Transcend/
Zooko-Ofsimplegeos-MacBook-Pro:/Volumes/Transcend$ ls
log.txt waronfun
Zooko-Ofsimplegeos-MacBook-Pro:/Volumes/Transcend$ ls -al
total 80
drwxrwxrwx 1 zooko staff 4096 Jun 21 23:37 .
drwxrwxrwt@ 5 root admin 170 Jun 21 23:37 ..
drwxrwxrwx 1 zooko staff 4096 Jun 21 23:37 .Spotlight-V100
drwxrwxrwx@ 1 zooko staff 4096 Jun 21 23:37 .Trashes
-rwxrwxrwx 1 zooko staff 4096 Jun 21 23:37 ._.Trashes
drwxrwxrwx 1 zooko staff 4096 Jun 21 23:37 .fseventsd
-rwxrwxrwx 1 zooko staff 16172 Jun 21 23:34 log.txt
drwxrwxrwx 1 zooko staff 4096 Jun 21 23:35 waronfun
Zooko-Ofsimplegeos-MacBook-Pro:/Volumes/Transcend$ find waronfun/
waronfun/
waronfun//IMGP5090.jpg
waronfun//IMGP5091.jpg
Zooko-Ofsimplegeos-MacBook-Pro:/Volumes/Transcend$ cd
Zooko-Ofsimplegeos-MacBook-Pro:~$ 0i
-bash: 0i: command not found
Zooko-Ofsimplegeos-MacBook-Pro:~$
Zooko-Ofsimplegeos-MacBook-Pro:~$ 7za a /Volumes/Transcend/log.txt
-bash: 7za: command not found
Zooko-Ofsimplegeos-MacBook-Pro:~$ shred
-bash: shred: command not found
Zooko-Ofsimplegeos-MacBook-Pro:~$ jobs
Zooko-Ofsimplegeos-MacBook-Pro:~$ cd
Zooko-Ofsimplegeos-MacBook-Pro:~$ mount
/dev/disk0s2 on / (hfs, local, journaled)
devfs on /dev (devfs, local, nobrowse)
map -hosts on /net (autofs, nosuid, automounted, nobrowse)
map auto_home on /home (autofs, automounted, nobrowse)
/dev/disk2s2 on /Volumes/Papers 1.9.4 (hfs, local, nodev, nosuid,
read-only, noowners, quarantine, mounted by zooko)
Zooko-Ofsimplegeos-MacBook-Pro:~$ grep -i tailor .pwu.txt
tailor: taamecev
Zooko-Ofsimplegeos-MacBook-Pro:~$ python -c 'print u"\u2026"'
…
Zooko-Ofsimplegeos-MacBook-Pro:~$ python -c 'print u"\u2014"'
—
Zooko-Ofsimplegeos-MacBook-Pro:~$ cd
Zooko-Ofsimplegeos-MacBook-Pro:~$ cd playground/
Zooko-Ofsimplegeos-MacBook-Pro:~/playground$ cd penelope/penelope/
.git/ LICENSE.txt build.xml ivy.xml
.gitignore NEWS.txt conf/ lib/
.rat-excludes NOTICE.txt contrib/ src/
CHANGES.txt README.txt debian/ test/
DISCLAIMER.txt bin/ interface/
Zooko-Ofsimplegeos-MacBook-Pro:~/playground$ cd penelope/penelope/
Zooko-Ofsimplegeos-MacBook-Pro:~/playground/penelope/penelope$ git
pull --rebase
remote: Counting objects: 246, done.
remote: Compressing objects: 100% (155/155), done.
remote: Total 211 (delta 95), reused 0 (delta 0)
Receiving objects: 100% (211/211), 306.45 KiB | 398 KiB/s, done.
Resolving deltas: 100% (95/95), completed with 23 local objects.
>From github.com:simplegeo/penelope
558d13d..4a9df39 penelope -> origin/penelope
First, rewinding head to replay your work on top of it...
Fast-forwarded penelope to 4a9df39deb340d40b9eb1ba95cfc8802aa4d60d3.
Zooko-Ofsimplegeos-MacBook-Pro:~/playground/penelope/penelope$
Zooko-Ofsimplegeos-MacBook-Pro:~/playground/penelope/penelope$
Zooko-Ofsimplegeos-MacBook-Pro:~/playground/penelope/penelope$
Zooko-Ofsimplegeos-MacBook-Pro:~/playground/penelope/penelope$ git diff
...skipping...
~
~
~
~
~
~
~
~
~
~
~
~
~
~
~
~
~
~
~
~
~
~
~
~
~
~
~
~
~
~
~
~
~
~
~
~
~
~
~
~
~
~
~
~
~
~
~
~
~
~
~
~
~
~
~
Zooko-Ofsimplegeos-MacBook-Pro:~/playground/penelope/penelope$
Zooko-Ofsimplegeos-MacBook-Pro:~/playground/penelope/penelope$ find .
-iname '*proximi*'
./src/java/com/simplegeo/penelope/db/PenelopeProximityCommand.java
./src/java/com/simplegeo/penelope/db/ProximityPredicate.java
Zooko-Ofsimplegeos-MacBook-Pro:~/playground/penelope/penelope$ python
-c 'print u"\u2708"'
✈
Zooko-Ofsimplegeos-MacBook-Pro:~/playground/penelope/penelope$ python
-c 'print u"\u2026"'
…
Zooko-Ofsimplegeos-MacBook-Pro:~/playground/penelope/penelope$ python
-c 'print u"\u2014"'
—
Zooko-Ofsimplegeos-MacBook-Pro:~/playground/penelope/penelope$ python -i
Python 2.6.1 (r261:67515, Feb 11 2010, 00:51:29)
[GCC 4.2.1 (Apple Inc. build 5646)] on darwin
Type "help", "copyright", "credits" or "license" for more information.
>>> 64*18
1152
>>> 4096*D('6.83')
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
NameError: name 'D' is not defined
>>> from decimal import Decimal as D
>>> 4096*D('6.83')
Decimal('27975.68')
>>> 4096 / 32
128
>>> (D('8.53')*4096) / (4096/32)
Decimal('272.96')
>>> 600 * 13000
7800000
>>> 600 * 10000
6000000
>>> print u"\u00b2"
²
>>> print u"\u00b2\u2075\u2076"
²⁵⁶
>>> from decimal import Decimal as D
>>> D('10') ** -12
Decimal('1E-12')
>>> sqrt(D('10') ** -12)
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
NameError: name 'sqrt' is not defined
>>> import math
>>> math.sqrt(D('10') ** -12)
9.9999999999999995e-07
>>> type(_)_
File "<stdin>", line 1
type(_)_
^
SyntaxError: invalid syntax
>>> type(_)
<type 'float'>
>>> import math
>>> D('10') ** -12
Decimal('1E-12')
>>> x=_
>>> x
Decimal('1E-12')
>>> dir(x)
['__abs__', '__add__', '__class__', '__complex__', '__copy__',
'__deepcopy__', '__delattr__', '__div__', '__divmod__', '__doc__',
'__eq__', '__float__', '__floordiv__', '__format__', '__ge__',
'__getattribute__', '__gt__', '__hash__', '__init__', '__int__',
'__le__', '__long__', '__lt__', '__mod__', '__module__', '__mul__',
'__ne__', '__neg__', '__new__', '__nonzero__', '__pos__', '__pow__',
'__radd__', '__rdiv__', '__rdivmod__', '__reduce__', '__reduce_ex__',
'__repr__', '__rfloordiv__', '__rmod__', '__rmul__', '__rpow__',
'__rsub__', '__rtruediv__', '__setattr__', '__sizeof__', '__slots__',
'__str__', '__sub__', '__subclasshook__', '__truediv__', '__trunc__',
'_check_nans', '_cmp', '_compare_check_nans', '_divide', '_exp',
'_fill_logical', '_fix', '_fix_nan', '_int', '_is_special', '_iseven',
'_isinfinity', '_isinteger', '_islogical', '_isnan', '_ln_exp_bound',
'_log10_exp_bound', '_pick_rounding_function', '_power_exact',
'_power_modulo', '_rescale', '_round', '_round_05up',
'_round_ceiling', '_round_down', '_round_floor', '_round_half_down',
'_round_half_even', '_round_half_up', '_round_up', '_sign',
'adjusted', 'as_tuple', 'canonical', 'compare', 'compare_signal',
'compare_total', 'compare_total_mag', 'conjugate', 'copy_abs',
'copy_negate', 'copy_sign', 'exp', 'fma', 'imag', 'is_canonical',
'is_finite', 'is_infinite', 'is_nan', 'is_normal', 'is_qnan',
'is_signed', 'is_snan', 'is_subnormal', 'is_zero', 'ln', 'log10',
'logb', 'logical_and', 'logical_invert', 'logical_or', 'logical_xor',
'max', 'max_mag', 'min', 'min_mag', 'next_minus', 'next_plus',
'next_toward', 'normalize', 'number_class', 'quantize', 'radix',
'real', 'remainder_near', 'rotate', 'same_quantum', 'scaleb', 'shift',
'sqrt', 'to_eng_string', 'to_integral', 'to_integral_exact',
'to_integral_value']
>>> x.sqrt()
Decimal('0.000001')
>>> (x*2).sqrt()
Decimal('0.000001414213562373095048801688724')
>>> (x*2).sqrt() * (2**80)
Decimal('1709679290002018430.137083076')
>>> (x*2).sqrt() * (2**64)
Decimal('26087635650665.56442469914361')
>>> (x*2).sqrt() * (2**70)
Decimal('1669608681642596.123180745191')
>>> (x*2).sqrt() * (2**72)
Decimal('6678434726570384.492722980764')
>>> (x*2).sqrt() * (2**75)
Decimal('53427477812563075.94178384611')
>>> (x*2).sqrt() * (2**76)
Decimal('106854955625126151.8835676922')
>>> (x*2).sqrt() * (2**76)
On Tue, Jun 22, 2010 at 7:54 PM, Jack Lloyd <lloyd at randombit.net> wrote:
> One other interesting aspect to a hash-based signature is that if you
> are using a tree-like scheme, you could parallelize it quite well,
> making good use of dozens of available cores (and, depending on the
> algorithm, the parallelism avilable in vector units like SSE/AVX,
> AltiVec, or NEON).
Yeah! Also the SIMD part of it hardly even depends on the algorithm,
does it? If you're doing a computation with multiple parallel hash
instances then you should be able to take almost any hash algorithm
and compute it in parallel, right? Thomas Pornin recently did this
with his SHA-3 candidate, Shabal, which doesn't have a structure that
lends itself to SIMD parallelism "internally" in one instance of
Shabal, but he arranged to compute four instances of Shabal in
parallel using SSE2, computing each instance half as fast.
I believe Wei Dai once mentioned the possibility of a similar hack for SHA-256.
> in 20 years things
> like it will be used in your toaster (perhaps doubling as the heating
> element?), and in 100 a chip of these specs will perhaps best be used
> broken into pieces and used for speartips to hunt antelope.
Hee hee!
> BTW, could you post a translation guide for those of us without a
> sufficiently Unicoded MUA? Here is what mutt shows me for the final
> paragraph of your mail:
Hopefully you will use your Sandy Bridge chip to install mutt version
1.4, which was released May 29, 2002 with utf-8 support. Until then,
here is the translation:
> Oh, one more detail: the "giant virtual space of one-time keys" might
> not need to be as large as 2????????. That's because an attacker can't
2^256
> "brute force attack" this space. The resistance against brute force
> attack is provided by other parts of the system. This space needs to
> be large only in order to avoid accidental collision. It could be
> perhaps as small as 2????????, which if I calculate correctly would let you
2^160
> write 10????? times to your file while still incurring less than a 10????????
10^16 10^-15
> chance of an accidental collision which would let people forge new
> writes to your file.
> """
>
> ?????????? yours,
faithfully
Zooko
More information about the tahoe-dev
mailing list