I'm assuming that you are working in .net or perhaps lower level like C++. From having recently consumed those APIs here is what I would recommend.
There are 2 Protected Configuration Providers available, DPAPI (more appropriate for client side desktop applications) and the RSA Provider (http://msdn.microsoft.com/en-us/library/system.configuration.rsaprotectedconfigurationprovider.aspx). The latter is more appropriate for encrypting web.configs as this is a public key configuration where only the ASP.NET service has the private key to decrypt the data, this can be scoped at both user and machine, similar to DPAPI.
Here is an old but sound walkthrough of it in ASP.Net:
I apologize if you are not using .Net, it was unclear. Still though I think the RSA provider is the correct way to go here.
With regards to breaking the DPAPI encryption, yes most of the attacks would need to be orchestrated on the target machine, usually involving either an attempt at the password SAM files or password reset scripts targeted at systems admins. Here is a whitepaper on breaking DPAPI offline from BlackHat 2010 - http ://elie.im/publication/reversing-dpapi-and-stealing-windows-secrets-offline. With regards to the encryption schemes used 3DES with CBC(Cipher Block Chaining) and SHA-1 all have their own separate known weaknesses for exploitation.