What is the best, most secure, easiest way to:
While that technique may work for you, and will give you reasonable strength (from my quick skim through), the simple problem that at least 95% of the planet would have is:
It's way too complicated
Humans (generally) just won't remember those rules, and they'll lose the piece of paper
So while a quick answer to the specific question may be "it looks okay", its applicability is minimal.
@bstpierre I didn't realise that the validity of a security system involves length of explanation. This is a proposal to address a real world problem as simply and robustly as possible.
The length of explanation for a system to be directly implemented by humans very much does matter. Most people that I know are hardly willing to choose a single good password, never mind manipulating strings the way this proposal does.
But let's be generous and assume that a user can handle the complexity. The scheme still has several problems that keep it from being usable.
First, it generates passwords like -----A1A8+QdjkD(*. What happens when you must have an account with some braindead website that requires a 6-8 character alphanumeric password? (Answer: you'll need either a secondary reconstruction algorithm, or a third salt and an alternate hashing algorithm that generates (possibly short) alphanumeric strings. You'll also need some mechanism for flagging the weak passwords.) You already have to remember 7 chunks of information to reconstruct the password (not counting the algorithm -- I'll assume for the sake of argument you have this automated). And it gets even worse, because after you've solved this problem, you'll come across an even more braindead service that requires a new set of recipes.
Another problem is the step of using the first half of the password "from the next line". If you lose the list, you can reconstruct the "word" pair for each site, but you won't be able to reconstruct the correct password unless you get the order of the sites correct. (IMO this step is an unnecessary obfuscation -- if someone has the list and knows the algorithm then there's no added value for you.)
And then you rely on hashing the "service name". What specific string are you using for this? The server name? What happens when MegaBank is aquired by GigaBank and your accounts move from wwws.mega.example.com to wws1.giga.example.com? I suppose it's easy enough to simply change your passwords when the service name changes, but it's another annoyance.
How do you handle forced password changes? One system I know of appears to remember your last two passwords so you can't reuse them. You could amend your scheme to include an 8th chunk of information -- a "sequence number"; this would be appended (or prepended, or inserted in some arbitrary position -- but this amount of variation amounts to remembering a 9th chunk of information). This becomes a hassle on systems that require you to change your password every 60 or 90 days.
How do you track usernames? Do you memorize them or are they written down?
What if you have multiple accounts with a single service? Your algorithm guarantees (by design) that a given service generates exactly one password. For example, perhaps you have to log into separate accounts at your bank or brokerage.
How are you storing the "very long password" used to generate the hashes? This has to be stored somewhere, separately from the password list.
If you have a more elegant solution that meets the design criteria, please share! I'd love to use it
I don't have another solution to fit your criteria.
At one time I used a reconstruction scheme based on website name and a couple of bits of information. It fell apart fast because of the reasons outlined above and I started using keepassx with a strong master password. Now, on each service I use a unique randomly generated maximum length password with the maximum allowed set of characters.
Your question outlines the risks associated with this system.
Edit: a single point of failure that I missed in my initial analysis is your email account. Unless you're using multiple independent email accounts, with a separate account for each service, your email is a single point of failure for multiple services because of the way most password recovery systems work. If your mail account password is compromised (social engineering, keylogger, etc), many of your services will also be compromised.
As noted this technique is too complicated and requires big amount of time just to enter the password (you need to remember salt, padding, divider and then consequently apply those to hash).
Why not use simple pass-phrases (of course different ones for different services) as suggested by xkcd (see also this question)? They have high entropy, are easy to remember and fast to type.
