So I think that, given the lack of physical security of the devices, whatever you do will be only best-effort. You just can't stop someone from stripping the device down, reading the data, modifying it, etc... Let's just take that as a given and move on.
This solution utilizes HMACs. An HMAC takes two inputs, a string and secret, and produces an output string that is cryptographically difficult/impossible to forge without knowing the the secret.
Put on all devices a shared secret (the same one) that is also known by the device administrators (they're the ones who give out authentication information to technicians). As the device is not physically secure, the storage of the secret will be less-than-perfect, but we already agreed that we'd be OK with this.
An admin will give a user a username and a password. The password will be the result of HMAC(secret, username) (possibly truncated to some reasonable length). When the user logs into a device, they will enter their username and password. The device will recalculate the HMAC, truncate it to the appropriate length, and compare it with the user's password.
Depending on your needs, you can make some changes to the system:
- Instead of storing the same secret on every device, you can store different secrets. This will, of course, increase administration costs, but it will add some security. You could give each device its own secret or group devices by geographic location, issue date, or other means.
- Along with the username and password, you could give each user a password expiration date. They would then enter their username, password, and expiration date when logging in. Their password would be
HMAC(secret, username + expiration date). The advantage of this is that passwords naturally timeout so an exposed password won't haunt you forever. The disadvantage is that users will need to continually get new passwords. Unlike more typical password expiry, users will need to contact admins to get their new password. Here too the lack of physical security may allow attackers to reset the date on the device, reactivating an expired password. Again, we agreed that perfect security won't be possible without hardware security.
- Depending on the flexibility of the device, you may be able to move the credentials to a USB drive, SD card, or some other device that can be used for authentication. An encrypted USB key like this one will provide you with 2-factor authentication.
- With each user having a unique login, you can implement some type of auditing.
Notable problems with this system include:
- Inability to disable a password. Even if you use the date extension, you need to wait for the password to expire.
- Unless you use a secure USB key (or similarly secure device) for authentication, it is still open to users creating "passwords.txt" files.
- The lack of hardware security greatly reduces any security efforts.
